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. | |
43 | */ | |
44 | ||
45 | #ifndef CATACOMB_MPBARRETT_H | |
46 | #define CATACOMB_MPBARRETT_H | |
47 | ||
48 | #ifdef __cplusplus | |
49 | extern "C" { | |
50 | #endif | |
51 | ||
52 | /*----- Header files ------------------------------------------------------*/ | |
53 | ||
54 | #ifndef CATACOMB_MP_H | |
55 | # include "mp.h" | |
56 | #endif | |
57 | ||
58 | /*----- Data structures ---------------------------------------------------*/ | |
59 | ||
60 | typedef struct mpbarrett { | |
61 | mp *m; | |
62 | mp *mu; | |
63 | size_t k; | |
64 | } mpbarrett; | |
65 | ||
66 | /*----- Functions provided ------------------------------------------------*/ | |
67 | ||
68 | /* --- @mpbarrett_create@ --- * | |
69 | * | |
70 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
71 | * @mp *m@ = modulus to work to | |
72 | * | |
f4535c64 | 73 | * Returns: Zero on success, nonzero on error. |
21a7c4b1 | 74 | * |
75 | * Use: Initializes a Barrett reduction context ready for use. | |
76 | */ | |
77 | ||
f4535c64 | 78 | extern int mpbarrett_create(mpbarrett */*mb*/, mp */*m*/); |
21a7c4b1 | 79 | |
80 | /* --- @mpbarrett_destroy@ --- * | |
81 | * | |
82 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
83 | * | |
84 | * Returns: --- | |
85 | * | |
86 | * Use: Destroys a Barrett reduction context releasing any resources | |
87 | * claimed. | |
88 | */ | |
89 | ||
90 | extern void mpbarrett_destroy(mpbarrett */*mb*/); | |
91 | ||
92 | /* --- @mpbarrett_reduce@ --- * | |
93 | * | |
94 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
95 | * @mp *d@ = destination for result | |
96 | * @mp *m@ = number to reduce | |
97 | * | |
98 | * Returns: The residue of @m@ modulo the number in the reduction | |
99 | * context. | |
100 | * | |
30cbe7a7 | 101 | * Use: Performs an efficient modular reduction. |
21a7c4b1 | 102 | */ |
103 | ||
104 | extern mp *mpbarrett_reduce(mpbarrett */*mb*/, mp */*d*/, mp */*m*/); | |
105 | ||
106 | /* --- @mpbarrett_exp@ --- * | |
107 | * | |
108 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
45c0fd36 MW |
109 | * @mp *d@ = fake destination |
110 | * @mp *a@ = base | |
111 | * @mp *e@ = exponent | |
21a7c4b1 | 112 | * |
45c0fd36 | 113 | * Returns: Result, %$a^e \bmod m$%. |
21a7c4b1 | 114 | */ |
115 | ||
116 | extern mp *mpbarrett_exp(mpbarrett */*mb*/, mp */*d*/, mp */*a*/, mp */*e*/); | |
117 | ||
ab0350a6 | 118 | /* --- @mpbarrett_mexp@ --- * |
119 | * | |
120 | * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context | |
121 | * @mp *d@ = fake destination | |
34e4f738 | 122 | * @const mp_expfactor *f@ = pointer to array of factors |
ab0350a6 | 123 | * @size_t n@ = number of factors supplied |
124 | * | |
125 | * Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the | |
126 | * exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result | |
127 | * is: | |
128 | * | |
129 | * %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$% | |
130 | */ | |
131 | ||
132 | extern mp *mpbarrett_mexp(mpbarrett */*mb*/, mp */*d*/, | |
34e4f738 | 133 | const mp_expfactor */*f*/, size_t /*n*/); |
ab0350a6 | 134 | |
21a7c4b1 | 135 | /*----- That's all, folks -------------------------------------------------*/ |
136 | ||
137 | #ifdef __cplusplus | |
138 | } | |
139 | #endif | |
140 | ||
141 | #endif |