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 import botan.math.bigint.bigint;
19 import std.traits : isPointer;
20 
21 /**
22 * Modular Reducer (using Barrett's technique)
23 */
24 struct ModularReducer
25 {
26 public:
27     ref const(BigInt) getModulus() const { return m_modulus; }
28 
29     /*
30     * Barrett Reduction
31     */
32     BigInt reduce(BigInt x) const
33     {
34         if (m_mod_words == 0)
35             throw new InvalidState("ModularReducer: Never initalized");
36         if (x.cmp(m_modulus, false) < 0)
37         {
38             if (x.isNegative())
39                 return x + m_modulus; // make positive
40             return x.move;
41         }
42         else if (x.cmp(m_modulus_2, false) < 0)
43         {
44             BigInt t1 = x.dup;
45             t1.setSign(BigInt.Positive);
46             t1 >>= (MP_WORD_BITS * (m_mod_words - 1));
47             t1 *= m_mu;
48             
49             t1 >>= (MP_WORD_BITS * (m_mod_words + 1));
50             t1 *= m_modulus;
51             
52             t1.maskBits(MP_WORD_BITS * (m_mod_words + 1));
53             
54             BigInt t2 = x.move;
55             t2.setSign(BigInt.Positive);
56             t2.maskBits(MP_WORD_BITS * (m_mod_words + 1));
57             
58             t2 -= t1;
59             
60             if (t2.isNegative())
61             {
62                 t2 += BigInt.powerOf2(MP_WORD_BITS * (m_mod_words + 1));
63             }
64             while (t2 >= m_modulus)
65                 t2 -= m_modulus;            
66 
67             if (x.isPositive())
68                 return t2.move();
69             else
70                 return m_modulus - t2;
71         }
72         else
73         {
74             // too big, fall back to normal division
75             return (x % m_modulus);
76         }
77     }
78 
79     /**
80     * Multiply mod p
81     * Params:
82     *  x = integer
83     *  y = integer
84     * Returns: (x * y) % p
85     */
86     BigInt multiply(const(BigInt)* x, const(BigInt)* y) const
87     { 
88         return reduce((*x) * y);
89     }
90 
91     /**
92     * Square mod p
93     * Params:
94     *  x = integer
95     * Returns: (x * x) % p
96     */
97     BigInt square()(const(BigInt)* x) const
98     {
99         return reduce(x.square());
100     }
101 
102     /**
103     * Cube mod p
104     * Params:
105     *  x = integer
106     * Returns: (x * x * x) % p
107     */
108     BigInt cube()(const(BigInt)* x) const
109     { return multiply(x, this.square(x)); }
110 
111     bool initialized() const { return (m_mod_words != 0); }
112     /*
113     * ModularReducer Constructor
114     */
115     this(const ref BigInt mod)
116     {
117         if (mod <= 0)
118             throw new InvalidArgument("ModularReducer: modulus must be positive");
119         m_modulus = mod.dup;
120         m_mod_words = m_modulus.sigWords();
121         m_modulus_2 = .square(&m_modulus);
122 		auto po2 = BigInt.powerOf2(2 * MP_WORD_BITS * m_mod_words);
123         m_mu = po2 / m_modulus;
124     }
125 
126     @property ModularReducer dup() const {
127         return ModularReducer(m_modulus);
128     }
129 
130 private:
131     BigInt m_modulus, m_modulus_2, m_mu;
132     size_t m_mod_words;
133 }