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