Commit | Line | Data |
---|---|---|
21a7c4b1 | 1 | /* -*-c-*- |
21a7c4b1 | 2 | * |
3 | * Barrett modular reduction | |
4 | * | |
5 | * (c) 1999 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
21a7c4b1 | 9 | * |
10 | * This file is part of Catacomb. | |
11 | * | |
12 | * Catacomb is free software; you can redistribute it and/or modify | |
13 | * it under the terms of the GNU Library General Public License as | |
14 | * published by the Free Software Foundation; either version 2 of the | |
15 | * License, or (at your option) any later version. | |
45c0fd36 | 16 | * |
21a7c4b1 | 17 | * Catacomb is distributed in the hope that it will be useful, |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
20 | * GNU Library General Public License for more details. | |
45c0fd36 | 21 | * |
21a7c4b1 | 22 | * You should have received a copy of the GNU Library General Public |
23 | * License along with Catacomb; if not, write to the Free | |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
25 | * MA 02111-1307, USA. | |
26 | */ | |
27 | ||
21a7c4b1 | 28 | /*----- Notes on Barrett reduction ----------------------------------------* |
29 | * | |
30 | * Barrett reduction is a technique for computing modular residues. Unlike | |
31 | * Montgomery reduction, it doesn't have restrictions on the modulus (except | |
32 | * that it be positive) and doesn't confuse matters by putting an extra | |
33 | * factor all the way through your computation. | |
34 | * | |
35 | * It's useful for slightly less heavy-duty work than Montgomery reduction | |
36 | * because the precomputation phase is rather simpler, involving a single | |
37 | * division operation. | |
38 | * | |
39 | * Sometimes it's useful to exponentiate modulo an even number, so there's a | |
40 | * modexp routine provided which uses Barrett reduction rather than | |
41 | * Montgomery reduction. This is handy when you're working on indices in an | |
42 | * even-order cyclic group or something. | |
fa17e5dc MW |
43 | * |
44 | * In more detail: suppose that %$b^{k-1} \le m < b^k$%. Let %$\mu = {}$% | |
45 | * %$\lfloor b^{2k}/m \rfloor$%; %$\mu$% is a scaled approximation to the | |
46 | * reciprocal %$1/m$%. Now, suppose we're given some %$a$% with | |
47 | * %$0 \le a < b^{2k}$%. The first step is to calculate an approximation | |
48 | * %$q = \lfloor \mu \lfloor a/b^{k-1} \rfloor/b^{k+1} \rfloor$% to the | |
49 | * quotient %$a/m$%. Then we have: | |
50 | * | |
51 | * %$\lfloor a/m - a/b^{2k} - b^{k-1}/m + 1/b^{k+1} \rfloor \le {}$% | |
52 | * %$q \le \lfloor a/m \rfloor | |
53 | * | |
54 | * But by assumption %$a < b^{2k}$% and %$2^{k-1} \le m$% so | |
55 | * | |
56 | * %$\lfloor a/m \rfloor - 2 \le q \le \lfloor a/m \rfloor$% | |
57 | * | |
58 | * Now we approximate the remainder by calculating %$r = a - q m$%. | |
59 | * Certainly %$r \equiv a \pmod{m}$%; and | |
60 | * | |
61 | * %$0 \le r \le (a - m \lfloor a/m \rfloor) + 2 m < 3 m$%. | |
62 | * | |
63 | * So the remainder can be fixed up with at most two conditional | |
64 | * subtractions. | |
21a7c4b1 | 65 | */ |
66 | ||
67 | #ifndef CATACOMB_MPBARRETT_H | |
68 | #define CATACOMB_MPBARRETT_H | |
69 | ||
70 | #ifdef __cplusplus | |
71 | extern "C" { | |
72 | #endif | |
73 | ||
74 | /*----- Header files ------------------------------------------------------*/ | |
75 | ||
76 | #ifndef CATACOMB_MP_H | |
77 | # include "mp.h" | |
78 | #endif | |
79 | ||
80 | /*----- Data structures ---------------------------------------------------*/ | |
81 | ||
82 | typedef struct mpbarrett { | |
83 | mp *m; | |
84 | mp *mu; | |
85 | size_t k; | |
86 | } mpbarrett; | |
87 | ||
88 | /*----- Functions provided ------------------------------------------------*/ | |
89 | ||
90 | /* --- @mpbarrett_create@ --- * | |
91 | * | |
92 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
93 | * @mp *m@ = modulus to work to | |
94 | * | |
f4535c64 | 95 | * Returns: Zero on success, nonzero on error. |
21a7c4b1 | 96 | * |
97 | * Use: Initializes a Barrett reduction context ready for use. | |
98 | */ | |
99 | ||
f4535c64 | 100 | extern int mpbarrett_create(mpbarrett */*mb*/, mp */*m*/); |
21a7c4b1 | 101 | |
102 | /* --- @mpbarrett_destroy@ --- * | |
103 | * | |
104 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
105 | * | |
106 | * Returns: --- | |
107 | * | |
108 | * Use: Destroys a Barrett reduction context releasing any resources | |
109 | * claimed. | |
110 | */ | |
111 | ||
112 | extern void mpbarrett_destroy(mpbarrett */*mb*/); | |
113 | ||
114 | /* --- @mpbarrett_reduce@ --- * | |
115 | * | |
116 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
117 | * @mp *d@ = destination for result | |
118 | * @mp *m@ = number to reduce | |
119 | * | |
120 | * Returns: The residue of @m@ modulo the number in the reduction | |
121 | * context. | |
122 | * | |
30cbe7a7 | 123 | * Use: Performs an efficient modular reduction. |
21a7c4b1 | 124 | */ |
125 | ||
126 | extern mp *mpbarrett_reduce(mpbarrett */*mb*/, mp */*d*/, mp */*m*/); | |
127 | ||
128 | /* --- @mpbarrett_exp@ --- * | |
129 | * | |
130 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
45c0fd36 MW |
131 | * @mp *d@ = fake destination |
132 | * @mp *a@ = base | |
133 | * @mp *e@ = exponent | |
21a7c4b1 | 134 | * |
45c0fd36 | 135 | * Returns: Result, %$a^e \bmod m$%. |
21a7c4b1 | 136 | */ |
137 | ||
138 | extern mp *mpbarrett_exp(mpbarrett */*mb*/, mp */*d*/, mp */*a*/, mp */*e*/); | |
139 | ||
ab0350a6 | 140 | /* --- @mpbarrett_mexp@ --- * |
141 | * | |
142 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
143 | * @mp *d@ = fake destination | |
34e4f738 | 144 | * @const mp_expfactor *f@ = pointer to array of factors |
ab0350a6 | 145 | * @size_t n@ = number of factors supplied |
146 | * | |
147 | * Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the | |
148 | * exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result | |
149 | * is: | |
150 | * | |
151 | * %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$% | |
152 | */ | |
153 | ||
154 | extern mp *mpbarrett_mexp(mpbarrett */*mb*/, mp */*d*/, | |
34e4f738 | 155 | const mp_expfactor */*f*/, size_t /*n*/); |
ab0350a6 | 156 | |
21a7c4b1 | 157 | /*----- That's all, folks -------------------------------------------------*/ |
158 | ||
159 | #ifdef __cplusplus | |
160 | } | |
161 | #endif | |
162 | ||
163 | #endif |