3 * Binary fields with polynomial basis representation
5 * (c) 2004 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
33 #include "field-guts.h"
36 /*----- Polynomial basis --------------------------------------------------*/
38 /* --- Field operations --- */
40 static void fdestroy(field
*ff
) {
41 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
42 gfreduce_destroy(&f
->r
); MP_DROP(f
->f
.q
);
46 static mp
*frand(field
*f
, mp
*d
, grand
*r
) {
47 return (mprand(d
, f
->nbits
, r
, 0));
50 static int fzerop(field
*ff
, mp
*x
) { return (MP_ZEROP(x
)); }
52 static mp
*fadd(field
*ff
, mp
*d
, mp
*x
, mp
*y
) { return (gf_add(d
, x
, y
)); }
54 static mp
*fmul(field
*ff
, mp
*d
, mp
*x
, mp
*y
) {
55 fctx_binpoly
*f
= (fctx_binpoly
*)ff
; d
= gf_mul(d
, x
, y
);
56 return (gfreduce_do(&f
->r
, d
, d
));
59 static mp
*fsqr(field
*ff
, mp
*d
, mp
*x
) {
60 fctx_binpoly
*f
= (fctx_binpoly
*)ff
; d
= gf_sqr(d
, x
);
61 return (gfreduce_do(&f
->r
, d
, d
));
64 static mp
*finv(field
*ff
, mp
*d
, mp
*x
) {
65 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
66 d
= gf_modinv(d
, x
, f
->r
.p
);
70 static mp
*freduce(field
*ff
, mp
*d
, mp
*x
) {
71 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
72 return (gfreduce_do(&f
->r
, d
, x
));
75 static mp
*fsqrt(field
*ff
, mp
*d
, mp
*x
) {
76 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
77 return (gfreduce_sqrt(&f
->r
, d
, x
));
80 static mp
*fquadsolve(field
*ff
, mp
*d
, mp
*x
) {
81 fctx_binpoly
*f
= (fctx_binpoly
*)ff
;
82 return (gfreduce_quadsolve(&f
->r
, d
, x
));
85 /* --- Field operations table --- */
87 static const field_ops fops
= {
88 FTY_BINARY
, "binpoly",
89 fdestroy
, frand
, field_stdsamep
,
91 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
96 /* --- @field_binpoly@ --- *
98 * Arguments: @mp *p@ = the reduction polynomial
100 * Returns: A pointer to the field.
102 * Use: Creates a field structure for a binary field mod @p@.
105 field
*field_binpoly(mp
*p
)
107 fctx_binpoly
*f
= CREATE(fctx_binpoly
);
111 f
->f
.nbits
= mp_bits(p
) - 1;
112 f
->f
.noctets
= (f
->f
.nbits
+ 7) >> 3;
113 gfreduce_create(&f
->r
, p
);
115 f
->f
.q
= mp_lsl(MP_NEW
, MP_ONE
, f
->f
.nbits
);
119 /*----- Normal basis ------------------------------------------------------*/
121 /* --- Field operations --- */
123 static void fndestroy(field
*ff
) {
124 fctx_binnorm
*f
= (fctx_binnorm
*)ff
; gfreduce_destroy(&f
->f
.r
);
125 gfn_destroy(&f
->ntop
); gfn_destroy(&f
->pton
); MP_DROP(f
->f
.f
.q
);
129 static int fnsamep(field
*ff
, field
*gg
) {
130 fctx_binnorm
*f
= (fctx_binnorm
*)ff
, *g
= (fctx_binnorm
*)gg
;
131 return (MP_EQ(f
->ntop
.r
[0], g
->ntop
.r
[0]) && field_stdsamep(ff
, gg
));
134 static mp
*fnin(field
*ff
, mp
*d
, mp
*x
) {
135 fctx_binnorm
*f
= (fctx_binnorm
*)ff
;
136 return (gfn_transform(&f
->ntop
, d
, x
));
139 static mp
*fnout(field
*ff
, mp
*d
, mp
*x
) {
140 fctx_binnorm
*f
= (fctx_binnorm
*)ff
;
141 return (gfn_transform(&f
->pton
, d
, x
));
144 /* --- Field operations table --- */
146 static const field_ops fnops
= {
147 FTY_BINARY
, "binnorm",
148 fndestroy
, frand
, fnsamep
,
150 fzerop
, field_id
, fadd
, fadd
, fmul
, fsqr
, finv
, freduce
, fsqrt
,
155 /* --- @field_binnorm@ --- *
157 * Arguments: @mp *p@ = the reduction polynomial
158 * @mp *beta@ = representation of normal point
160 * Returns: A pointer to the field.
162 * Use: Creates a field structure for a binary field mod @p@ which
163 * uses a normal basis representation externally. Computations
164 * are still done on a polynomial-basis representation.
167 field
*field_binnorm(mp
*p
, mp
*beta
)
169 fctx_binnorm
*f
= CREATE(fctx_binnorm
);
171 f
->f
.f
.zero
= MP_ZERO
;
173 f
->f
.f
.nbits
= mp_bits(p
) - 1;
174 f
->f
.f
.noctets
= (f
->f
.f
.nbits
+ 7) >> 3;
175 gfreduce_create(&f
->f
.r
, p
);
177 f
->f
.f
.q
= mp_lsl(MP_NEW
, MP_ONE
, f
->f
.f
.nbits
);
178 gfn_create(p
, beta
, &f
->ntop
, &f
->pton
);
182 /*----- That's all, folks -------------------------------------------------*/