monotone

monotone Mtn Source Tree

Root/botan/reducer.cpp

1/*************************************************
2* Modular Reducer Source File *
3* (C) 1999-2006 The Botan Project *
4*************************************************/
5
6#include <botan/reducer.h>
7#include <botan/bit_ops.h>
8#include <botan/numthry.h>
9#include <botan/mp_core.h>
10
11namespace Botan {
12
13/*************************************************
14* Modular_Reducer Constructor *
15*************************************************/
16Modular_Reducer::Modular_Reducer(const BigInt& mod)
17 {
18 if(mod <= 0)
19 throw Invalid_Argument("Modular_Reducer: modulus must be positive");
20
21 modulus = mod;
22 mod_words = modulus.sig_words();
23
24 modulus_2 = Botan::square(modulus);
25 mod2_words = modulus_2.sig_words();
26
27 mu = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * mod_words) / modulus;
28 mu_words = mu.sig_words();
29 }
30
31/*************************************************
32* Barrett Reduction *
33*************************************************/
34BigInt Modular_Reducer::reduce(const BigInt& x) const
35 {
36 if(mod_words == 0)
37 throw Invalid_State("Modular_Reducer: Never initalized");
38
39 BigInt t1 = x;
40 t1.set_sign(BigInt::Positive);
41
42 if(t1 < modulus)
43 {
44 if(x.is_negative() && t1.is_nonzero())
45 return modulus - t1;
46 return x;
47 }
48
49 if(t1 >= modulus_2)
50 return (x % modulus);
51
52 t1 >>= (MP_WORD_BITS * (mod_words - 1));
53 t1 *= mu;
54 t1 >>= (MP_WORD_BITS * (mod_words + 1));
55
56 t1 *= modulus;
57 t1.mask_bits(MP_WORD_BITS * (mod_words+1));
58
59 BigInt t2 = x;
60 t2.set_sign(BigInt::Positive);
61 t2.mask_bits(MP_WORD_BITS * (mod_words+1));
62
63 t1 = t2 - t1;
64
65 if(t1.is_negative())
66 {
67 BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (mod_words+1));
68 t1 += b_to_k1;
69 }
70
71 while(t1 >= modulus)
72 t1 -= modulus;
73
74 if(x.is_negative() && t1.is_nonzero())
75 t1 = modulus - t1;
76
77 return t1;
78 }
79
80/*************************************************
81* Multiply, followed by a reduction *
82*************************************************/
83BigInt Modular_Reducer::multiply(const BigInt& x, const BigInt& y) const
84 {
85 return reduce(x * y);
86 }
87
88/*************************************************
89* Square, followed by a reduction *
90*************************************************/
91BigInt Modular_Reducer::square(const BigInt& x) const
92 {
93 return reduce(Botan::square(x));
94 }
95
96}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status