botan.math.numbertheory.reducer source code

1 /**
2 * Modular Reducer
3 * 
4 * Copyright:
5 * (C) 1999-2010 Jack Lloyd
6 * (C) 2014-2015 Etienne Cimon
7 *
8 * License:
9 * Botan is released under the Simplified BSD License (see LICENSE.md)
10 */
11 module botan.math.numbertheory.reducer;
12 
13 import botan.constants;
14 static if (BOTAN_HAS_PUBLIC_KEY_CRYPTO):
15 
16 import botan.math.numbertheory.numthry;
17 import botan.math.mp.mp_core;
18 
19 /**
20 * Modular Reducer (using Barrett's technique)
21 */
22 struct ModularReducer
23 {
24 public:
25     ref const(BigInt) getModulus() const { return m_modulus; }
26 
27     /*
28     * Barrett Reduction
29     */
30     BigInt reduce(BigInt x) const
31     {
32         if (m_mod_words == 0)
33             throw new InvalidState("ModularReducer: Never initalized");
34         if (x.cmp(m_modulus, false) < 0)
35         {
36             if (x.isNegative())
37                 return x + m_modulus; // make positive
38             return x.move;
39         }
40         else if (x.cmp(m_modulus_2, false) < 0)
41         {
42             BigInt t1 = x.dup;
43             t1.setSign(BigInt.Positive);
44             t1 >>= (MP_WORD_BITS * (m_mod_words - 1));
45             t1 *= m_mu;
46             
47             t1 >>= (MP_WORD_BITS * (m_mod_words + 1));
48             t1 *= m_modulus;
49             
50             t1.maskBits(MP_WORD_BITS * (m_mod_words + 1));
51             
52             BigInt t2 = x.move;
53             t2.setSign(BigInt.Positive);
54             t2.maskBits(MP_WORD_BITS * (m_mod_words + 1));
55             
56             t2 -= t1;
57             
58             if (t2.isNegative())
59             {
60                 t2 += BigInt.powerOf2(MP_WORD_BITS * (m_mod_words + 1));
61             }
62             while (t2 >= m_modulus)
63                 t2 -= m_modulus;            
64 
65             if (x.isPositive())
66                 return t2.move();
67             else
68                 return m_modulus - t2;
69         }
70         else
71         {
72             // too big, fall back to normal division
73             return (x % m_modulus);
74         }
75     }
76 
77     /**
78     * Multiply mod p
79     * Params:
80     *  x = integer
81     *  y = integer
82     * Returns: (x * y) % p
83     */
84     BigInt multiply()(auto const ref BigInt x, auto const ref BigInt y) const
85     { 
86         return reduce(x * y);
87     }
88 
89     /**
90     * Square mod p
91     * Params:
92     *  x = integer
93     * Returns: (x * x) % p
94     */
95     BigInt square()(auto const ref BigInt x) const
96     {
97         return reduce(x.square());
98     }
99 
100     /**
101     * Cube mod p
102     * Params:
103     *  x = integer
104     * Returns: (x * x * x) % p
105     */
106     BigInt cube()(auto const ref BigInt x) const
107     { return multiply(x, this.square(x)); }
108 
109     bool initialized() const { return (m_mod_words != 0); }
110     /*
111     * ModularReducer Constructor
112     */
113     this(const ref BigInt mod)
114     {
115         if (mod <= 0)
116             throw new InvalidArgument("ModularReducer: modulus must be positive");
117         m_modulus = mod.dup;
118         m_mod_words = m_modulus.sigWords();
119         m_modulus_2 = .square(m_modulus);
120 		auto po2 = BigInt.powerOf2(2 * MP_WORD_BITS * m_mod_words);
121         m_mu = po2 / m_modulus;
122     }
123 
124     @property ModularReducer dup() const {
125         return ModularReducer(m_modulus);
126     }
127 
128 private:
129     BigInt m_modulus, m_modulus_2, m_mu;
130     size_t m_mod_words;
131 }