23d9984ebbc4aa04eb75dc028a04a6640f2c40f5
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 /*----- Header files ------------------------------------------------------*/
35 #include "field-guts.h"
38 /*----- Polynomial basis --------------------------------------------------*/
40 /* --- Field operations --- */
42 static void fdestroy(field
*ff
) {
43 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
44 gfreduce_destroy(&f
->r
);
48 static mp
*frand(field
*f
, mp
*d
, grand
*r
) {
49 return (mprand(d
, f
->nbits
, r
, 0));
52 static int fzerop(field
*ff
, mp
*x
) { return (MP_ZEROP(x
)); }
54 static mp
*fadd(field
*ff
, mp
*d
, mp
*x
, mp
*y
) { return (gf_add(d
, x
, y
)); }
56 static mp
*fmul(field
*ff
, mp
*d
, mp
*x
, mp
*y
) {
57 fctx_binpoly
*f
= (fctx_binpoly
*)ff
; d
= gf_mul(d
, x
, y
);
58 return (gfreduce_do(&f
->r
, d
, d
));
61 static mp
*fsqr(field
*ff
, mp
*d
, mp
*x
) {
62 fctx_binpoly
*f
= (fctx_binpoly
*)ff
; d
= gf_sqr(d
, x
);
63 return (gfreduce_do(&f
->r
, d
, d
));
66 static mp
*finv(field
*ff
, mp
*d
, mp
*x
) {
67 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
68 d
= gf_modinv(d
, x
, f
->r
.p
);
72 static mp
*freduce(field
*ff
, mp
*d
, mp
*x
) {
73 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
74 return (gfreduce_do(&f
->r
, d
, x
));
77 static mp
*fsqrt(field
*ff
, mp
*d
, mp
*x
) {
78 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
79 return (gfreduce_sqrt(&f
->r
, d
, x
));
82 static mp
*fquadsolve(field
*ff
, mp
*d
, mp
*x
) {
83 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
84 return (gfreduce_quadsolve(&f
->r
, d
, x
));
87 /* --- Field operations table --- */
89 static const field_ops fops
= {
90 FTY_BINARY
, "binpoly",
91 fdestroy
, frand
, field_stdsamep
,
93 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
98 /* --- @field_binpoly@ --- *
100 * Arguments: @mp *p@ = the reduction polynomial
102 * Returns: A pointer to the field.
104 * Use: Creates a field structure for a binary field mod @p@.
107 field
*field_binpoly(mp
*p
)
109 fctx_binpoly
*f
= CREATE(fctx_binpoly
);
113 f
->f
.nbits
= mp_bits(p
) - 1;
114 f
->f
.noctets
= (f
->f
.nbits
+ 7) >> 3;
115 gfreduce_create(&f
->r
, p
);
120 /*----- Normal basis ------------------------------------------------------*/
122 /* --- Field operations --- */
124 static void fndestroy(field
*ff
) {
125 fctx_binnorm
*f
= (fctx_binnorm
*)ff
; gfreduce_destroy(&f
->f
.r
);
126 gfn_destroy(&f
->ntop
); gfn_destroy(&f
->pton
);
130 static int fnsamep(field
*ff
, field
*gg
) {
131 fctx_binnorm
*f
= (fctx_binnorm
*)ff
, *g
= (fctx_binnorm
*)gg
;
132 return (MP_EQ(f
->ntop
.r
[0], g
->ntop
.r
[0]) && field_stdsamep(ff
, gg
));
135 static mp
*fnin(field
*ff
, mp
*d
, mp
*x
) {
136 fctx_binnorm
*f
= (fctx_binnorm
*)ff
;
137 return (gfn_transform(&f
->ntop
, d
, x
));
140 static mp
*fnout(field
*ff
, mp
*d
, mp
*x
) {
141 fctx_binnorm
*f
= (fctx_binnorm
*)ff
;
142 return (gfn_transform(&f
->pton
, d
, x
));
145 /* --- Field operations table --- */
147 static const field_ops fnops
= {
148 FTY_BINARY
, "binnorm",
149 fndestroy
, frand
, fnsamep
,
151 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
156 /* --- @field_binnorm@ --- *
158 * Arguments: @mp *p@ = the reduction polynomial
159 * @mp *beta@ = representation of normal point
161 * Returns: A pointer to the field.
163 * Use: Creates a field structure for a binary field mod @p@ which
164 * uses a normal basis representation externally. Computations
165 * are still done on a polynomial-basis representation.
168 field
*field_binnorm(mp
*p
, mp
*beta
)
170 fctx_binnorm
*f
= CREATE(fctx_binnorm
);
172 f
->f
.f
.zero
= MP_ZERO
;
174 f
->f
.f
.nbits
= mp_bits(p
) - 1;
175 f
->f
.f
.noctets
= (f
->f
.f
.nbits
+ 7) >> 3;
176 gfreduce_create(&f
->f
.r
, p
);
178 gfn_create(p
, beta
, &f
->ntop
, &f
->pton
);
182 /*----- That's all, folks -------------------------------------------------*/