3 * $Id: f-binpoly.c,v 1.8 2004/04/02 01:03:49 mdw Exp $
5 * Binary fields with polynomial basis representation
7 * (c) 2004 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
32 * $Log: f-binpoly.c,v $
33 * Revision 1.8 2004/04/02 01:03:49 mdw
34 * Miscellaneous constification.
36 * Revision 1.7 2004/04/01 21:28:41 mdw
37 * Normal basis support (translates to poly basis internally). Rewrite
38 * EC and prime group table generators in awk, so that they can reuse data
39 * for repeated constants.
41 * Revision 1.6 2004/04/01 12:50:09 mdw
42 * Add cyclic group abstraction, with test code. Separate off exponentation
43 * functions for better static linking. Fix a buttload of bugs on the way.
44 * Generally ensure that negative exponents do inversion correctly. Add
45 * table of standard prime-field subgroups. (Binary field subgroups are
46 * currently unimplemented but easy to add if anyone ever finds a good one.)
48 * Revision 1.5 2004/03/27 17:54:11 mdw
49 * Standard curves and curve checking.
51 * Revision 1.4 2004/03/23 15:19:32 mdw
52 * Test elliptic curves more thoroughly.
54 * Revision 1.3 2004/03/23 12:08:26 mdw
55 * Random field-element selection.
57 * Revision 1.2 2004/03/21 22:52:06 mdw
58 * Merge and close elliptic curve branch.
60 * Revision 1.1.2.1 2004/03/21 22:39:46 mdw
61 * Elliptic curves on binary fields work.
65 /*----- Header files ------------------------------------------------------*/
75 /*----- Polynomial basis --------------------------------------------------*/
82 /* --- Field operations --- */
84 static void fdestroy(field
*ff
)
85 { fctx
*f
= (fctx
*)ff
; gfreduce_destroy(&f
->r
); DESTROY(f
); }
87 static mp
*frand(field
*f
, mp
*d
, grand
*r
)
88 { return (mprand(d
, f
->nbits
, r
, 0)); }
90 static int fzerop(field
*ff
, mp
*x
) { return (!MP_LEN(x
)); }
92 static mp
*fadd(field
*ff
, mp
*d
, mp
*x
, mp
*y
) { return (gf_add(d
, x
, y
)); }
94 static mp
*fmul(field
*ff
, mp
*d
, mp
*x
, mp
*y
) {
95 fctx
*f
= (fctx
*)ff
; d
= gf_mul(d
, x
, y
);
96 return (gfreduce_do(&f
->r
, d
, d
));
99 static mp
*fsqr(field
*ff
, mp
*d
, mp
*x
) {
100 fctx
*f
= (fctx
*)ff
; d
= gf_sqr(d
, x
);
101 return (gfreduce_do(&f
->r
, d
, d
));
104 static mp
*finv(field
*ff
, mp
*d
, mp
*x
)
105 { fctx
*f
= (fctx
*)ff
; gf_gcd(0, 0, &d
, f
->r
.p
, x
); return (d
); }
107 static mp
*freduce(field
*ff
, mp
*d
, mp
*x
)
108 { fctx
*f
= (fctx
*)ff
; return (gfreduce_do(&f
->r
, d
, x
)); }
110 static mp
*fsqrt(field
*ff
, mp
*d
, mp
*x
)
111 { fctx
*f
= (fctx
*)ff
; return (gfreduce_sqrt(&f
->r
, d
, x
)); }
113 static mp
*fquadsolve(field
*ff
, mp
*d
, mp
*x
)
114 { fctx
*f
= (fctx
*)ff
; return (gfreduce_quadsolve(&f
->r
, d
, x
)); }
116 /* --- Field operations table --- */
118 static const field_ops fops
= {
119 FTY_BINARY
, "binpoly",
120 fdestroy
, frand
, field_stdsamep
,
122 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
127 /* --- @field_binpoly@ --- *
129 * Arguments: @mp *p@ = the reduction polynomial
131 * Returns: A pointer to the field.
133 * Use: Creates a field structure for a binary field mod @p@.
136 field
*field_binpoly(mp
*p
)
138 fctx
*f
= CREATE(fctx
);
142 f
->f
.nbits
= mp_bits(p
) - 1;
143 f
->f
.noctets
= (f
->f
.nbits
+ 7) >> 3;
144 gfreduce_create(&f
->r
, p
);
149 /*----- Normal basis ------------------------------------------------------*/
151 typedef struct fnctx
{
156 /* --- Field operations --- */
158 static void fndestroy(field
*ff
) {
159 fnctx
*f
= (fnctx
*)ff
; gfreduce_destroy(&f
->f
.r
);
160 gfn_destroy(&f
->ntop
); gfn_destroy(&f
->pton
);
164 static int fnsamep(field
*ff
, field
*gg
) {
165 fnctx
*f
= (fnctx
*)ff
, *g
= (fnctx
*)gg
;
166 return (MP_EQ(f
->ntop
.r
[0], g
->ntop
.r
[0]) && field_stdsamep(ff
, gg
));
169 static mp
*fnin(field
*ff
, mp
*d
, mp
*x
)
170 { fnctx
*f
= (fnctx
*)ff
; return (gfn_transform(&f
->ntop
, d
, x
)); }
172 static mp
*fnout(field
*ff
, mp
*d
, mp
*x
)
173 { fnctx
*f
= (fnctx
*)ff
; return (gfn_transform(&f
->pton
, d
, x
)); }
175 /* --- Field operations table --- */
177 static const field_ops fnops
= {
178 FTY_BINARY
, "binnorm",
179 fndestroy
, frand
, fnsamep
,
181 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
186 /* --- @field_binnorm@ --- *
188 * Arguments: @mp *p@ = the reduction polynomial
189 * @mp *beta@ = representation of normal point
191 * Returns: A pointer to the field.
193 * Use: Creates a field structure for a binary field mod @p@ which
194 * uses a normal basis representation externally. Computations
195 * are still done on a polynomial-basis representation.
198 field
*field_binnorm(mp
*p
, mp
*beta
)
200 fnctx
*f
= CREATE(fnctx
);
202 f
->f
.f
.zero
= MP_ZERO
;
204 f
->f
.f
.nbits
= mp_bits(p
) - 1;
205 f
->f
.f
.noctets
= (f
->f
.f
.nbits
+ 7) >> 3;
206 gfreduce_create(&f
->f
.r
, p
);
208 gfn_create(p
, beta
, &f
->ntop
, &f
->pton
);
212 /*----- That's all, folks -------------------------------------------------*/