monotone

monotone Mtn Source Tree

Root/botan/pow_mod.cpp

1/*************************************************
2* Modular Exponentiation Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/numthry.h>
7#include <vector>
8
9namespace Botan {
10
11namespace {
12
13/*************************************************
14* Exponentiation Window Size *
15*************************************************/
16u32bit window_size(u32bit exp_bits)
17 {
18 struct mapping { u32bit bits; u32bit window_size; };
19
20 static const mapping wsize[] = {
21 { 2048, 7 },
22 { 1024, 6 },
23 { 256, 5 },
24 { 128, 4 },
25 { 64, 3 },
26 { 0, 0 }
27 };
28
29 for(u32bit j = 0; wsize[j].bits; j++)
30 {
31 if(exp_bits >= wsize[j].bits)
32 return wsize[j].window_size;
33 }
34 return 1;
35 }
36
37/*************************************************
38* Left-to-Right Binary Modular Exponentiation *
39*************************************************/
40BigInt power_mod_l2r(const BigInt& basex, const BigInt& exp,
41 ModularReducer* reducer)
42 {
43 const BigInt base = reducer->convert_in(basex);
44 const u32bit exp_bits = exp.bits();
45
46 BigInt x = reducer->convert_in(1);
47 for(u32bit j = exp_bits; j > 0; j--)
48 {
49 x = reducer->square(x);
50 if(exp.get_bit(j-1))
51 x = reducer->multiply(x, base);
52 }
53 return reducer->convert_out(x);
54 }
55
56/*************************************************
57* Modular Exponentiation with g = 2 *
58*************************************************/
59BigInt power_mod_g2(const BigInt& exp, ModularReducer* reducer)
60 {
61 if(reducer->must_convert())
62 throw Internal_Error("power_mod_g2: Can't use this reducer");
63
64 const u32bit exp_bits = exp.bits();
65 BigInt x = 1;
66 for(u32bit j = exp_bits; j > 0; j--)
67 {
68 x = reducer->square(x);
69 if(exp.get_bit(j-1))
70 {
71 x <<= 1;
72 x = reducer->reduce(x);
73 }
74 }
75 return x;
76 }
77
78/*************************************************
79* Window Modular Exponentiation *
80*************************************************/
81BigInt power_mod_window(const BigInt& base, const BigInt& exp,
82 ModularReducer* reducer, u32bit window_bits)
83 {
84 if(window_bits < 2)
85 throw Internal_Error("power_mod_window: Window size too small");
86
87 std::vector<BigInt> g((1 << window_bits) - 1);
88
89 g[0] = reducer->convert_in(base);
90 for(u32bit j = 1; j != g.size(); j++)
91 g[j] = reducer->multiply(g[j-1], g[0]);
92
93 const u32bit exp_nibbles = (exp.bits() + window_bits - 1) / window_bits;
94
95 BigInt x = reducer->convert_in(1);
96 for(u32bit j = exp_nibbles; j > 0; j--)
97 {
98 for(u32bit k = 0; k != window_bits; k++)
99 x = reducer->square(x);
100 u32bit nibble = exp.get_nibble(j-1, window_bits);
101 if(nibble)
102 x = reducer->multiply(x, g[nibble-1]);
103 }
104 return reducer->convert_out(x);
105 }
106
107}
108
109/*************************************************
110* Modular Exponentiation *
111*************************************************/
112BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
113 {
114 ModularReducer* reducer = get_reducer(mod);
115 BigInt x = power_mod(base, exp, reducer);
116 delete reducer;
117 return x;
118 }
119
120/*************************************************
121* Modular Exponentiation Algorithm Dispatch *
122*************************************************/
123BigInt power_mod(const BigInt& base, const BigInt& exp,
124 ModularReducer* reducer)
125 {
126 if(base.is_negative())
127 throw Invalid_Argument("power_mod: base must be positive");
128 if(exp.is_negative())
129 throw Invalid_Argument("power_mod: exponent must be positive");
130 if(exp.is_zero())
131 return 1;
132
133 const u32bit window_bits = window_size(exp.bits());
134
135 if(base == 2 && !reducer->must_convert())
136 return power_mod_g2(exp, reducer);
137 if(window_bits > 1)
138 return power_mod_window(base, exp, reducer, window_bits);
139 return power_mod_l2r(base, exp, reducer);
140 }
141
142}

Archive Download this file

Branches

Tags

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