3 * $Id: gfn.c,v 1.2 2004/04/08 01:36:15 mdw Exp $
5 * Normal-basis translation for binary fields
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 /*----- Main code ---------------------------------------------------------*/
37 /* --- @gfn_copy@ --- *
39 * Arguments: @gfn *d@ = where to put the copy
40 * @const gfn *s@ = where the source is
44 * Use: Makes a copy of a translation matrix.
47 void gfn_copy(gfn
*d
, const gfn
*s
)
52 d
->r
= xmalloc(s
->n
* sizeof(mp
*));
53 for (i
= 0; i
< s
->n
; i
++)
54 d
->r
[i
] = MP_COPY(s
->r
[i
]);
57 /* --- @gfn_destroy@ --- *
59 * Arguments: @gfn *m@ = a transformation matrix to free
63 * Use: Frees up a transformation matrix when it's no longer wanted.
66 void gfn_destroy(gfn
*m
)
67 { size_t i
; for (i
= 0; i
< m
->n
; i
++) MP_DROP(m
->r
[i
]); xfree(m
->r
); }
69 /* --- @gfn_identity@ --- *
71 * Arguments: @gfn *m@ = where to put the matrix
72 * @size_t n@ = size of the matrix
76 * Use: Fills @m@ with an identity matrix.
79 void gfn_identity(gfn
*m
, size_t n
)
84 m
->r
= xmalloc(n
* sizeof(mp
*));
86 for (i
= 1; i
< n
; i
++)
87 m
->r
[i
] = mp_lsl(MP_NEW
, m
->r
[i
- 1], 1);
90 /* --- @gfn_invert@ --- *
92 * Arguments: @gfn *m@ = a transformation matrix
94 * Returns: Zero if successful, nonzero if the matrix was singular.
96 * Use: Inverts a transformation matrix.
99 int gfn_invert(gfn
*m
)
107 gfn_identity(m
, mm
.n
);
108 for (i
= 0; i
< mm
.n
; i
++) {
109 if (!mp_testbit(mm
.r
[i
], i
)) {
110 for (j
= i
+ 1; j
< mm
.n
; j
++) {
111 if (mp_testbit(mm
.r
[j
], i
))
116 t
= mm
.r
[i
]; mm
.r
[i
] = mm
.r
[j
]; mm
.r
[j
] = t
;
117 t
= m
->r
[i
]; m
->r
[i
] = m
->r
[j
]; m
->r
[j
] = t
;
119 for (j
= 0; j
< mm
.n
; j
++) {
120 if (j
== i
) continue;
121 if (mp_testbit(mm
.r
[j
], i
)) {
122 mm
.r
[j
] = mp_xor(mm
.r
[j
], mm
.r
[j
], mm
.r
[i
]);
123 m
->r
[j
] = mp_xor(m
->r
[j
], m
->r
[j
], m
->r
[i
]);
133 /* --- @gfn_transform@ --- *
135 * Arguments: @gfn *m@ = conversion matrix to apply
136 * @mp *d@ = destination pointer
137 * @mp *x@ = input value
139 * Returns: The transformed element.
141 * Use: Transforms a field element according to the given matrix.
144 mp
*gfn_transform(gfn
*m
, mp
*d
, mp
*x
)
150 for (i
= 0, mp_scan(&sc
, x
); i
< m
->n
&& mp_step(&sc
); i
++)
151 if (mp_bit(&sc
)) y
= mp_xor(y
, y
, m
->r
[i
]);
156 /* --- @gfn_create@ --- *
158 * Arguments: @mp *p@ = modulus for polynomial basis
159 * @mp *beta@ = the generator of the normal basis, expressed
160 * relative to the polynomial basis
161 * @gfn *ntop@ = output normal-to-polynomail conversion matrix
162 * @gfn *pton@ = output polynomial-to-normal conversion matrix
164 * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$%
165 * doesn't generate a proper basis).
167 * Use: Constructs conversion matrices between polynomial and normal
168 * basis representations of binary field elements.
171 int gfn_create(mp
*p
, mp
*beta
, gfn
*ntop
, gfn
*pton
)
173 size_t m
= mp_bits(p
) - 1;
178 /* --- We start by building the the @ntop@ matrix --- *
180 * For mad reasons, the string representation of normal-basis elements is
184 gfreduce_create(&gr
, p
);
185 np
= ntop ? ntop
: &tmp
;
187 np
->r
= xmalloc(m
* sizeof(mp
*));
188 np
->r
[m
- 1] = MP_COPY(beta
);
189 for (i
= m
- 1; i
--; ) {
190 mp
*x
= gf_sqr(MP_NEW
, np
->r
[i
+ 1]);
191 np
->r
[i
] = gfreduce_do(&gr
, x
, x
);
193 gfreduce_destroy(&gr
);
195 /* --- That was easy -- now invert it --- */
198 if (ntop
) gfn_copy(pton
, np
); else *pton
= *np
;
199 if (gfn_invert(pton
)) {
201 if (ntop
) gfn_destroy(ntop
);
206 /* --- And we're done --- */
211 /*----- Test rig ----------------------------------------------------------*/
215 static int check(dstr
*v
)
217 mp
*p
= *(mp
**)v
[0].buf
;
218 mp
*beta
= *(mp
**)v
[1].buf
;
219 mp
*xp
= *(mp
**)v
[2].buf
;
220 mp
*xn
= *(mp
**)v
[3].buf
;
226 gfn_create(p
, beta
, &ntop
, &pton
);
227 gfn_identity(&ii
, pton
.n
);
228 for (i
= 0; i
< pton
.n
; i
++) {
229 y
= gfn_transform(&ntop
, y
, pton
.r
[i
]);
230 if (!MP_EQ(y
, ii
.r
[i
])) {
232 fprintf(stderr
, "*** inverse pton->ntop check failed (row %lu)\n",
234 MP_EPRINTX("*** p", p
); MP_EPRINTX("*** beta", beta
);
235 MP_EPRINTX("*** computed", y
);
239 y
= gfn_transform(&pton
, y
, xp
);
242 fprintf(stderr
, "*** pton failed\n");
243 MP_EPRINTX("*** p", p
); MP_EPRINTX("*** beta", beta
);
244 MP_EPRINTX("*** xp", xp
); MP_EPRINTX("*** xn", xn
);
245 MP_EPRINTX("*** computed", y
);
247 y
= gfn_transform(&ntop
, y
, xn
);
250 fprintf(stderr
, "*** ntop failed\n");
251 MP_EPRINTX("*** p", p
); MP_EPRINTX("*** beta", beta
);
252 MP_EPRINTX("*** xp", xp
); MP_EPRINTX("*** xn", xn
);
253 MP_EPRINTX("*** computed", y
);
255 gfn_destroy(&pton
); gfn_destroy(&ntop
);
256 mp_drop(p
); mp_drop(beta
); mp_drop(xp
); mp_drop(xn
); mp_drop(y
);
257 assert(mparena_count(MPARENA_GLOBAL
) == 0);
261 static test_chunk tests
[] = {
262 { "gfn", check
, { &type_mp
, &type_mp
, &type_mp
, &type_mp
} },
266 int main(int argc
, char *argv
[])
268 test_run(argc
, argv
, tests
, SRCDIR
"/tests/gfn");
274 /*----- That's all, folks -------------------------------------------------*/