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