monotone

monotone Mtn Source Tree

Root/botan/barrett.cpp

1/*************************************************
2* Barrett Reducer Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/barrett.h>
7#include <botan/numthry.h>
8#include <botan/mp_core.h>
9#include <botan/bit_ops.h>
10
11namespace Botan {
12
13/*************************************************
14* Precompute values *
15*************************************************/
16BarrettReducer::BarrettReducer(const BigInt& mod) : ModularReducer(mod)
17 {
18 k = modulus.sig_words();
19 mu.set_bit(MP_WORD_BITS * 2 * k);
20 mu /= modulus;
21 max_bits = MP_WORD_BITS * 2 * k;
22
23 if(mu.size() > 8 && !power_of_2(mu.size()))
24 mu.grow_reg((1 << high_bit(mu.size())) - mu.size());
25 }
26
27/*************************************************
28* Barrett Reduction *
29*************************************************/
30BigInt BarrettReducer::reduce(const BigInt& x) const
31 {
32 if(x.is_positive() && x < modulus)
33 return x;
34 if(x.bits() > max_bits)
35 return (x % modulus);
36
37 t1 = x;
38 t1.set_sign(BigInt::Positive);
39
40 t1 >>= (MP_WORD_BITS * (k - 1));
41 t1 *= mu;
42 t1 >>= (MP_WORD_BITS * (k + 1));
43
44 t1 *= modulus;
45 t1.mask_bits(MP_WORD_BITS * (k+1));
46
47 t2 = x;
48 t2.set_sign(BigInt::Positive);
49 t2.mask_bits(MP_WORD_BITS * (k+1));
50
51 t2 -= t1;
52
53 if(t2.is_negative())
54 {
55 BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (k+1));
56 t2 += b_to_k1;
57 }
58 while(t2 >= modulus)
59 t2 -= modulus;
60
61 if(x.is_negative() && t2.is_nonzero())
62 t2 = modulus - t2;
63
64 return t2;
65 }
66
67}

Archive Download this file

Branches

Tags

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