Commit | Line | Data |
---|---|---|
b0ab12e6 | 1 | /* -*-c-*- |
b0ab12e6 | 2 | * |
3 | * Prime fields with Montgomery arithmetic | |
4 | * | |
5 | * (c) 2001 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
b0ab12e6 | 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 | * |
b0ab12e6 | 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 | * |
b0ab12e6 | 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 | ||
b0ab12e6 | 28 | /*----- Header files ------------------------------------------------------*/ |
29 | ||
30 | #include <mLib/sub.h> | |
31 | ||
32 | #include "field.h" | |
9b8b6877 | 33 | #include "mprand.h" |
f94b972d | 34 | #include "field-guts.h" |
b0ab12e6 | 35 | |
4edc47b8 | 36 | /*----- Main code ---------------------------------------------------------*/ |
b0ab12e6 | 37 | |
b0ab12e6 | 38 | /* --- Field operations --- */ |
39 | ||
f94b972d | 40 | static void fdestroy(field *ff) { |
41 | fctx_prime *f = (fctx_prime *)ff; | |
42 | mpmont_destroy(&f->mm); | |
43 | DESTROY(f); | |
44 | } | |
b0ab12e6 | 45 | |
f94b972d | 46 | static mp *frand(field *ff, mp *d, grand *r) { |
47 | fctx_prime *f = (fctx_prime *)ff; | |
48 | return (mprand_range(d, f->mm.m, r, 0)); | |
49 | } | |
9b8b6877 | 50 | |
4edc47b8 | 51 | static mp *fin(field *ff, mp *d, mp *x) { |
f94b972d | 52 | fctx_prime *f = (fctx_prime *)ff; |
dbfee00a | 53 | mp_div(0, &d, x, f->mm.m); |
54 | return (mpmont_mul(&f->mm, d, d, f->mm.r2)); | |
b0ab12e6 | 55 | } |
56 | ||
f94b972d | 57 | static mp *fout(field *ff, mp *d, mp *x) { |
58 | fctx_prime *f = (fctx_prime *)ff; | |
59 | return (mpmont_reduce(&f->mm, d, x)); | |
60 | } | |
b0ab12e6 | 61 | |
a69a3efd | 62 | static int fzerop(field *ff, mp *x) { return (MP_ZEROP(x)); } |
8823192f | 63 | |
f94b972d | 64 | static mp *fneg(field *ff, mp *d, mp *x) { |
65 | fctx_prime *f = (fctx_prime *)ff; | |
fac18421 MW |
66 | if (MP_ZEROP(x)) { if (d != x) mp_drop(d); return (MP_COPY(x)); } |
67 | else return (mp_sub(d, f->mm.m, x)); | |
f94b972d | 68 | } |
b085fd91 | 69 | |
4edc47b8 | 70 | static mp *fadd(field *ff, mp *d, mp *x, mp *y) { |
f94b972d | 71 | fctx_prime *f = (fctx_prime *)ff; d = mp_add(d, x, y); |
a69a3efd | 72 | if (MP_NEGP(d)) d = mp_add(d, d, f->mm.m); |
fac18421 | 73 | else if (MP_CMP(d, >=, f->mm.m)) d = mp_sub(d, d, f->mm.m); |
dbfee00a | 74 | return (d); |
b0ab12e6 | 75 | } |
76 | ||
4edc47b8 | 77 | static mp *fsub(field *ff, mp *d, mp *x, mp *y) { |
f94b972d | 78 | fctx_prime *f = (fctx_prime *)ff; d = mp_sub(d, x, y); |
a69a3efd | 79 | if (MP_NEGP(d)) d = mp_add(d, d, f->mm.m); |
fac18421 | 80 | else if (MP_CMP(d, >=, f->mm.m)) d = mp_sub(d, d, f->mm.m); |
dbfee00a | 81 | return (d); |
b0ab12e6 | 82 | } |
83 | ||
f94b972d | 84 | static mp *fmul(field *ff, mp *d, mp *x, mp *y) { |
85 | fctx_prime *f = (fctx_prime *)ff; | |
86 | return (mpmont_mul(&f->mm, d, x, y)); | |
87 | } | |
b0ab12e6 | 88 | |
4edc47b8 | 89 | static mp *fsqr(field *ff, mp *d, mp *x) { |
f94b972d | 90 | fctx_prime *f = (fctx_prime *)ff; d = mp_sqr(d, x); |
b0ab12e6 | 91 | return (mpmont_reduce(&f->mm, d, d)); |
92 | } | |
93 | ||
4edc47b8 | 94 | static mp *finv(field *ff, mp *d, mp *x) { |
f94b972d | 95 | fctx_prime *f = (fctx_prime *)ff; d = mpmont_reduce(&f->mm, d, x); |
b817bfc6 | 96 | d = mp_modinv(d, d, f->mm.m); return (mpmont_mul(&f->mm, d, d, f->mm.r2)); |
b0ab12e6 | 97 | } |
98 | ||
f94b972d | 99 | static mp *freduce(field *ff, mp *d, mp *x) { |
100 | fctx_prime *f = (fctx_prime *)ff; | |
101 | mp_div(0, &d, x, f->mm.m); | |
102 | return (d); | |
103 | } | |
b0ab12e6 | 104 | |
4edc47b8 | 105 | static mp *fsqrt(field *ff, mp *d, mp *x) { |
f94b972d | 106 | fctx_prime *f = (fctx_prime *)ff; d = mpmont_reduce(&f->mm, d, x); |
4edc47b8 | 107 | d = mp_modsqrt(d, d, f->mm.m); if (!d) return (d); |
ceb3f0c0 | 108 | return (mpmont_mul(&f->mm, d, d, f->mm.r2)); |
109 | } | |
110 | ||
4edc47b8 | 111 | static mp *fdbl(field *ff, mp *d, mp *x) { |
f94b972d | 112 | fctx_prime *f = (fctx_prime *)ff; d = mp_lsl(d, x, 1); |
d2f1ffa0 | 113 | if (MP_CMP(d, >=, f->mm.m)) d = mp_sub(d, d, f->mm.m); |
dbfee00a | 114 | return (d); |
b0ab12e6 | 115 | } |
116 | ||
4edc47b8 | 117 | static mp *ftpl(field *ff, mp *d, mp *x) { |
f94b972d | 118 | fctx_prime *f = (fctx_prime *)ff; MP_DEST(d, MP_LEN(x) + 1, x->f); |
d2f1ffa0 | 119 | MPX_UMULN(d->v, d->vl, x->v, x->vl, 3); d->f &= ~MP_UNDEF; |
120 | while (MP_CMP(d, >=, f->mm.m)) d = mp_sub(d, d, f->mm.m); | |
b0ab12e6 | 121 | return (d); |
122 | } | |
123 | ||
4edc47b8 | 124 | static mp *fqdl(field *ff, mp *d, mp *x) { |
f94b972d | 125 | fctx_prime *f = (fctx_prime *)ff; d = mp_lsl(d, x, 2); |
d2f1ffa0 | 126 | while (MP_CMP(d, >=, f->mm.m)) d = mp_sub(d, d, f->mm.m); |
8823192f | 127 | return (d); |
128 | } | |
129 | ||
4edc47b8 | 130 | static mp *fhlv(field *ff, mp *d, mp *x) { |
f94b972d | 131 | fctx_prime *f = (fctx_prime *)ff; |
a69a3efd | 132 | if (MP_ZEROP(x)) { MP_COPY(x); MP_DROP(d); return (x); } |
4edc47b8 | 133 | if (x->v[0] & 1) { d = mp_add(d, x, f->mm.m); x = d; } |
8823192f | 134 | return (mp_lsr(d, x, 1)); |
b0ab12e6 | 135 | } |
136 | ||
137 | /* --- Field operations table --- */ | |
138 | ||
4e66da02 | 139 | static const field_ops fops = { |
bc985cef | 140 | FTY_PRIME, "prime", |
34e4f738 | 141 | fdestroy, frand, field_stdsamep, |
b0ab12e6 | 142 | fin, fout, |
ceb3f0c0 | 143 | fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt, |
144 | 0, | |
145 | fdbl, ftpl, fqdl, fhlv | |
b0ab12e6 | 146 | }; |
147 | ||
148 | /* --- @field_prime@ --- * | |
149 | * | |
150 | * Arguments: @mp *p@ = the characteristic of the field | |
151 | * | |
02d7884d | 152 | * Returns: A pointer to the field or null. |
b0ab12e6 | 153 | * |
154 | * Use: Creates a field structure for a prime field of size %$p$%, | |
155 | * using Montgomery reduction for arithmetic. | |
156 | */ | |
157 | ||
158 | field *field_prime(mp *p) | |
159 | { | |
f94b972d | 160 | fctx_prime *f; |
02d7884d | 161 | |
f94b972d | 162 | f = CREATE(fctx_prime); |
b0ab12e6 | 163 | f->f.ops = &fops; |
f4535c64 | 164 | if (mpmont_create(&f->mm, p)) { |
165 | DESTROY(f); | |
166 | return (0); | |
167 | } | |
41cb1beb | 168 | f->f.zero = MP_ZERO; |
169 | f->f.one = f->mm.r; | |
432c4e18 | 170 | f->f.m = f->mm.m; |
171 | f->f.nbits = mp_bits(p); | |
172 | f->f.noctets = (f->f.nbits + 7) >> 3; | |
1d7857e7 | 173 | f->f.q = f->mm.m; |
b0ab12e6 | 174 | return (&f->f); |
175 | } | |
176 | ||
177 | /*----- That's all, folks -------------------------------------------------*/ |