Return to ntt_fft_reduce.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / math / libnttfft

Annotation of embedaddon/strongswan/src/libstrongswan/math/libnttfft/ntt_fft_reduce.h, revision 1.1.1.1

1.1       misho       1: /*
                      2:  * Copyright (C) 2016 Andreas Steffen
                      3:  * HSR Hochschule fuer Technik Rapperswil
                      4:  *
                      5:  * This program is free software; you can redistribute it and/or modify it
                      6:  * under the terms of the GNU General Public License as published by the
                      7:  * Free Software Foundation; either version 2 of the License, or (at your
                      8:  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
                      9:  *
                     10:  * This program is distributed in the hope that it will be useful, but
                     11:  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
                     12:  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
                     13:  * for more details.
                     14:  */
                     15: 
                     16: /**
                     17:  * @defgroup ntt_fft ntt_fft
                     18:  * @{ @ingroup ntt_p
                     19:  */
                     20: 
                     21: #ifndef NTT_REDUCE_H_
                     22: #define NTT_REDUCE_H_
                     23: 
                     24: #include "ntt_fft_params.h"
                     25: 
                     26: /**
                     27:  * Montgomery Reduction
                     28:  *
                     29:  * Montgomery, P. L. Modular multiplication without trial division.
                     30:  * Mathematics of Computation 44, 170 (1985), 519–521.
                     31:  */
                     32: static inline uint32_t ntt_fft_mreduce(uint32_t x, const ntt_fft_params_t *p)
                     33: {
                     34:        uint32_t m, t;
                     35: 
                     36:        m = (x * p->q_inv) & p->rmask;
                     37:        t = (x + m * p->q) >> p->rlog;
                     38: 
                     39:        return (t < p->q) ? t : t - p->q;
                     40: }
                     41: 
                     42: #endif /** NTT_REDUCE_H_ @}*/