monotone

monotone Mtn Source Tree

Root/botan/powm_fw.cpp

1/*************************************************
2* Fixed Window Exponentiation Source File *
3* (C) 1999-2006 The Botan Project *
4*************************************************/
5
6#include <botan/def_powm.h>
7#include <botan/numthry.h>
8#include <vector>
9
10namespace Botan {
11
12namespace {
13
14/*************************************************
15* Try to choose a good window size *
16*************************************************/
17u32bit choose_window_bits(u32bit exp_bits, u32bit,
18 Power_Mod::Usage_Hints hints)
19 {
20 static const u32bit wsize[][2] = {
21 { 2048, 7 }, { 1024, 6 }, { 256, 5 }, { 128, 4 }, { 64, 3 }, { 0, 0 }
22 };
23
24 u32bit window_bits = 3;
25
26 if(exp_bits)
27 {
28 for(u32bit j = 0; wsize[j][0]; ++j)
29 {
30 if(exp_bits >= wsize[j][0])
31 {
32 window_bits += wsize[j][1];
33 break;
34 }
35 }
36 }
37
38 if(hints & Power_Mod::EXP_IS_FIXED)
39 window_bits += 2;
40 if(hints & Power_Mod::EXP_IS_LARGE)
41 window_bits += 2;
42 if(hints & Power_Mod::BASE_IS_FIXED)
43 ++window_bits;
44
45 return window_bits;
46 }
47
48}
49
50/*************************************************
51* Set the exponent *
52*************************************************/
53void Fixed_Window_Exponentiator::set_exponent(const BigInt& e)
54 {
55 exp = e;
56 }
57
58/*************************************************
59* Set the base *
60*************************************************/
61void Fixed_Window_Exponentiator::set_base(const BigInt& base)
62 {
63 window_bits = choose_window_bits(exp.bits(), base.bits(), hints);
64
65 g.resize((1 << window_bits) - 1);
66 g[0] = base;
67 for(u32bit j = 1; j != g.size(); ++j)
68 g[j] = reducer.multiply(g[j-1], g[0]);
69 }
70
71/*************************************************
72* Compute the result *
73*************************************************/
74BigInt Fixed_Window_Exponentiator::execute() const
75 {
76 const u32bit exp_nibbles = (exp.bits() + window_bits - 1) / window_bits;
77
78 BigInt x = 1;
79 for(u32bit j = exp_nibbles; j > 0; --j)
80 {
81 for(u32bit k = 0; k != window_bits; ++k)
82 x = reducer.square(x);
83
84 u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits);
85 if(nibble)
86 x = reducer.multiply(x, g[nibble-1]);
87 }
88 return x;
89 }
90
91/*************************************************
92* Fixed_Window_Exponentiator Constructor *
93*************************************************/
94Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(const BigInt& n,
95 Power_Mod::Usage_Hints hints)
96 {
97 reducer = Modular_Reducer(n);
98 this->hints = hints;
99 window_bits = 0;
100 }
101
102}

Archive Download this file

Branches

Tags

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