f46efa79 |
1 | /* -*-c-*- |
2 | * |
f4535c64 |
3 | * $Id$ |
f46efa79 |
4 | * |
5 | * Efficient reduction modulo nice primes |
6 | * |
7 | * (c) 2004 Straylight/Edgeware |
8 | */ |
9 | |
10 | /*----- Licensing notice --------------------------------------------------* |
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. |
18 | * |
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. |
23 | * |
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 | |
f46efa79 |
30 | #ifndef CATACOMB_MPREDUCE_H |
31 | #define CATACOMB_MPREDUCE_H |
32 | |
33 | #ifdef __cplusplus |
34 | extern "C" { |
35 | #endif |
36 | |
37 | /*----- Header files ------------------------------------------------------*/ |
38 | |
39 | /*----- Data structures ---------------------------------------------------*/ |
40 | |
41 | typedef struct mpreduce_instr { |
42 | unsigned op; /* Instruction opcode */ |
43 | size_t argx, argy; /* Immediate arguments */ |
44 | } mpreduce_instr; |
45 | |
46 | enum { |
47 | MPRI_ADD, /* Add @p@ offset by @x@ words */ |
48 | MPRI_ADDLSL, /* Add @p << y@ offset by @x@ */ |
49 | MPRI_SUB, /* Sub @p@ offset by @x@ words */ |
50 | MPRI_SUBLSL, /* Sub @p << y@ offset by @x@ */ |
51 | MPRI_MAX |
52 | }; |
53 | |
54 | typedef struct mpreduce { |
55 | size_t lim; /* Word containing top bit */ |
56 | unsigned s; /* Shift for top word */ |
57 | mp *p; /* Copy of the modulus */ |
58 | size_t in; /* Number of instruction words */ |
59 | mpreduce_instr *iv; /* Vector of instructions */ |
60 | } mpreduce; |
61 | |
62 | /*----- Functions provided ------------------------------------------------*/ |
63 | |
64 | /* --- @mpreduce_create@ --- * |
65 | * |
66 | * Arguments: @gfreduce *r@ = structure to fill in |
67 | * @mp *x@ = an integer |
68 | * |
f4535c64 |
69 | * Returns: Zero for success, nonzero on error. |
f46efa79 |
70 | * |
71 | * Use: Initializes a context structure for reduction. |
72 | */ |
73 | |
f4535c64 |
74 | extern int mpreduce_create(mpreduce */*r*/, mp */*p*/); |
f46efa79 |
75 | |
76 | /* --- @mpreduce_destroy@ --- * |
77 | * |
78 | * Arguments: @mpreduce *r@ = structure to free |
79 | * |
80 | * Returns: --- |
81 | * |
82 | * Use: Reclaims the resources from a reduction context. |
83 | */ |
84 | |
85 | extern void mpreduce_destroy(mpreduce */*r*/); |
86 | |
87 | /* --- @mpreduce_dump@ --- * |
88 | * |
89 | * Arguments: @mpreduce *r@ = structure to dump |
90 | * @FILE *fp@ = file to dump on |
91 | * |
92 | * Returns: --- |
93 | * |
94 | * Use: Dumps a reduction context. |
95 | */ |
96 | |
97 | extern void mpreduce_dump(mpreduce */*r*/, FILE */*fp*/); |
98 | |
99 | /* --- @mpreduce_do@ --- * |
100 | * |
101 | * Arguments: @mpreduce *r@ = reduction context |
102 | * @mp *d@ = destination |
103 | * @mp *x@ = source |
104 | * |
105 | * Returns: Destination, @x@ reduced modulo the reduction poly. |
106 | */ |
107 | |
108 | extern mp *mpreduce_do(mpreduce */*r*/, mp */*d*/, mp */*x*/); |
109 | |
110 | /* --- @mpreduce_exp@ --- * |
111 | * |
112 | * Arguments: @mpreduce *mr@ = pointer to reduction context |
113 | * @mp *d@ = fake destination |
114 | * @mp *a@ = base |
115 | * @mp *e@ = exponent |
116 | * |
117 | * Returns: Result, %$a^e \bmod m$%. |
118 | */ |
119 | |
120 | extern mp *mpreduce_exp(mpreduce */*mr*/, mp */*d*/, mp */*a*/, mp */*e*/); |
121 | |
122 | /*----- That's all, folks -------------------------------------------------*/ |
123 | |
124 | #ifdef __cplusplus |
125 | } |
126 | #endif |
127 | |
128 | #endif |