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
); MP_DROP(f
->f
.q
);
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
);
117 f
->f
.q
= mp_lsl(MP_NEW
, MP_ONE
, f
->f
.nbits
);
121 /*----- Normal basis ------------------------------------------------------*/
123 /* --- Field operations --- */
125 static void fndestroy(field
*ff
) {
126 fctx_binnorm
*f
= (fctx_binnorm
*)ff
; gfreduce_destroy(&f
->f
.r
);
127 gfn_destroy(&f
->ntop
); gfn_destroy(&f
->pton
); MP_DROP(f
->f
.f
.q
);
131 static int fnsamep(field
*ff
, field
*gg
) {
132 fctx_binnorm
*f
= (fctx_binnorm
*)ff
, *g
= (fctx_binnorm
*)gg
;
133 return (MP_EQ(f
->ntop
.r
[0], g
->ntop
.r
[0]) && field_stdsamep(ff
, gg
));
136 static mp
*fnin(field
*ff
, mp
*d
, mp
*x
) {
137 fctx_binnorm
*f
= (fctx_binnorm
*)ff
;
138 return (gfn_transform(&f
->ntop
, d
, x
));
141 static mp
*fnout(field
*ff
, mp
*d
, mp
*x
) {
142 fctx_binnorm
*f
= (fctx_binnorm
*)ff
;
143 return (gfn_transform(&f
->pton
, d
, x
));
146 /* --- Field operations table --- */
148 static const field_ops fnops
= {
149 FTY_BINARY
, "binnorm",
150 fndestroy
, frand
, fnsamep
,
152 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
157 /* --- @field_binnorm@ --- *
159 * Arguments: @mp *p@ = the reduction polynomial
160 * @mp *beta@ = representation of normal point
162 * Returns: A pointer to the field.
164 * Use: Creates a field structure for a binary field mod @p@ which
165 * uses a normal basis representation externally. Computations
166 * are still done on a polynomial-basis representation.
169 field
*field_binnorm(mp
*p
, mp
*beta
)
171 fctx_binnorm
*f
= CREATE(fctx_binnorm
);
173 f
->f
.f
.zero
= MP_ZERO
;
175 f
->f
.f
.nbits
= mp_bits(p
) - 1;
176 f
->f
.f
.noctets
= (f
->f
.f
.nbits
+ 7) >> 3;
177 gfreduce_create(&f
->f
.r
, p
);
179 f
->f
.f
.q
= mp_lsl(MP_NEW
, MP_ONE
, f
->f
.f
.nbits
);
180 gfn_create(p
, beta
, &f
->ntop
, &f
->pton
);
184 /*----- That's all, folks -------------------------------------------------*/