3 * $Id: f-binpoly.c,v 1.7 2004/04/01 21:28:41 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.7 2004/04/01 21:28:41 mdw
34 * Normal basis support (translates to poly basis internally). Rewrite
35 * EC and prime group table generators in awk, so that they can reuse data
36 * for repeated constants.
38 * Revision 1.6 2004/04/01 12:50:09 mdw
39 * Add cyclic group abstraction, with test code. Separate off exponentation
40 * functions for better static linking. Fix a buttload of bugs on the way.
41 * Generally ensure that negative exponents do inversion correctly. Add
42 * table of standard prime-field subgroups. (Binary field subgroups are
43 * currently unimplemented but easy to add if anyone ever finds a good one.)
45 * Revision 1.5 2004/03/27 17:54:11 mdw
46 * Standard curves and curve checking.
48 * Revision 1.4 2004/03/23 15:19:32 mdw
49 * Test elliptic curves more thoroughly.
51 * Revision 1.3 2004/03/23 12:08:26 mdw
52 * Random field-element selection.
54 * Revision 1.2 2004/03/21 22:52:06 mdw
55 * Merge and close elliptic curve branch.
57 * Revision 1.1.2.1 2004/03/21 22:39:46 mdw
58 * Elliptic curves on binary fields work.
62 /*----- Header files ------------------------------------------------------*/
72 /*----- Polynomial basis --------------------------------------------------*/
79 /* --- Field operations --- */
81 static void fdestroy(field
*ff
)
82 { fctx
*f
= (fctx
*)ff
; gfreduce_destroy(&f
->r
); DESTROY(f
); }
84 static mp
*frand(field
*f
, mp
*d
, grand
*r
)
85 { return (mprand(d
, f
->nbits
, r
, 0)); }
87 static int fzerop(field
*ff
, mp
*x
) { return (!MP_LEN(x
)); }
89 static mp
*fadd(field
*ff
, mp
*d
, mp
*x
, mp
*y
) { return (gf_add(d
, x
, y
)); }
91 static mp
*fmul(field
*ff
, mp
*d
, mp
*x
, mp
*y
) {
92 fctx
*f
= (fctx
*)ff
; d
= gf_mul(d
, x
, y
);
93 return (gfreduce_do(&f
->r
, d
, d
));
96 static mp
*fsqr(field
*ff
, mp
*d
, mp
*x
) {
97 fctx
*f
= (fctx
*)ff
; d
= gf_sqr(d
, x
);
98 return (gfreduce_do(&f
->r
, d
, d
));
101 static mp
*finv(field
*ff
, mp
*d
, mp
*x
)
102 { fctx
*f
= (fctx
*)ff
; gf_gcd(0, 0, &d
, f
->r
.p
, x
); return (d
); }
104 static mp
*freduce(field
*ff
, mp
*d
, mp
*x
)
105 { fctx
*f
= (fctx
*)ff
; return (gfreduce_do(&f
->r
, d
, x
)); }
107 static mp
*fsqrt(field
*ff
, mp
*d
, mp
*x
)
108 { fctx
*f
= (fctx
*)ff
; return (gfreduce_sqrt(&f
->r
, d
, x
)); }
110 static mp
*fquadsolve(field
*ff
, mp
*d
, mp
*x
)
111 { fctx
*f
= (fctx
*)ff
; return (gfreduce_quadsolve(&f
->r
, d
, x
)); }
113 /* --- Field operations table --- */
115 static field_ops fops
= {
116 FTY_BINARY
, "binpoly",
117 fdestroy
, frand
, field_stdsamep
,
119 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
124 /* --- @field_binpoly@ --- *
126 * Arguments: @mp *p@ = the reduction polynomial
128 * Returns: A pointer to the field.
130 * Use: Creates a field structure for a binary field mod @p@.
133 field
*field_binpoly(mp
*p
)
135 fctx
*f
= CREATE(fctx
);
139 f
->f
.nbits
= mp_bits(p
) - 1;
140 f
->f
.noctets
= (f
->f
.nbits
+ 7) >> 3;
141 gfreduce_create(&f
->r
, p
);
146 /*----- Normal basis ------------------------------------------------------*/
148 typedef struct fnctx
{
153 /* --- Field operations --- */
155 static void fndestroy(field
*ff
) {
156 fnctx
*f
= (fnctx
*)ff
; gfreduce_destroy(&f
->f
.r
);
157 gfn_destroy(&f
->ntop
); gfn_destroy(&f
->pton
);
161 static int fnsamep(field
*ff
, field
*gg
) {
162 fnctx
*f
= (fnctx
*)ff
, *g
= (fnctx
*)gg
;
163 return (MP_EQ(f
->ntop
.r
[0], g
->ntop
.r
[0]) && field_stdsamep(ff
, gg
));
166 static mp
*fnin(field
*ff
, mp
*d
, mp
*x
)
167 { fnctx
*f
= (fnctx
*)ff
; return (gfn_transform(&f
->ntop
, d
, x
)); }
169 static mp
*fnout(field
*ff
, mp
*d
, mp
*x
)
170 { fnctx
*f
= (fnctx
*)ff
; return (gfn_transform(&f
->pton
, d
, x
)); }
172 /* --- Field operations table --- */
174 static field_ops fnops
= {
175 FTY_BINARY
, "binnorm",
176 fndestroy
, frand
, fnsamep
,
178 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
183 /* --- @field_binnorm@ --- *
185 * Arguments: @mp *p@ = the reduction polynomial
186 * @mp *beta@ = representation of normal point
188 * Returns: A pointer to the field.
190 * Use: Creates a field structure for a binary field mod @p@ which
191 * uses a normal basis representation externally. Computations
192 * are still done on a polynomial-basis representation.
195 field
*field_binnorm(mp
*p
, mp
*beta
)
197 fnctx
*f
= CREATE(fnctx
);
199 f
->f
.f
.zero
= MP_ZERO
;
201 f
->f
.f
.nbits
= mp_bits(p
) - 1;
202 f
->f
.f
.noctets
= (f
->f
.f
.nbits
+ 7) >> 3;
203 gfreduce_create(&f
->f
.r
, p
);
205 gfn_create(p
, beta
, &f
->ntop
, &f
->pton
);
209 /*----- That's all, folks -------------------------------------------------*/