3 * Normal-basis translation for binary fields
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 /*----- Main code ---------------------------------------------------------*/
35 /* --- @gfn_copy@ --- *
37 * Arguments: @gfn *d@ = where to put the copy
38 * @const gfn *s@ = where the source is
42 * Use: Makes a copy of a translation matrix.
45 void gfn_copy(gfn
*d
, const gfn
*s
)
50 d
->r
= xmalloc(s
->n
* sizeof(mp
*));
51 for (i
= 0; i
< s
->n
; i
++)
52 d
->r
[i
] = MP_COPY(s
->r
[i
]);
55 /* --- @gfn_destroy@ --- *
57 * Arguments: @gfn *m@ = a transformation matrix to free
61 * Use: Frees up a transformation matrix when it's no longer wanted.
64 void gfn_destroy(gfn
*m
)
65 { size_t i
; for (i
= 0; i
< m
->n
; i
++) MP_DROP(m
->r
[i
]); xfree(m
->r
); }
67 /* --- @gfn_identity@ --- *
69 * Arguments: @gfn *m@ = where to put the matrix
70 * @size_t n@ = size of the matrix
74 * Use: Fills @m@ with an identity matrix.
77 void gfn_identity(gfn
*m
, size_t n
)
82 m
->r
= xmalloc(n
* sizeof(mp
*));
84 for (i
= 1; i
< n
; i
++)
85 m
->r
[i
] = mp_lsl(MP_NEW
, m
->r
[i
- 1], 1);
88 /* --- @gfn_invert@ --- *
90 * Arguments: @gfn *m@ = a transformation matrix
92 * Returns: Zero if successful, nonzero if the matrix was singular.
94 * Use: Inverts a transformation matrix.
97 int gfn_invert(gfn
*m
)
105 gfn_identity(m
, mm
.n
);
106 for (i
= 0; i
< mm
.n
; i
++) {
107 if (!mp_testbit(mm
.r
[i
], i
)) {
108 for (j
= i
+ 1; j
< mm
.n
; j
++) {
109 if (mp_testbit(mm
.r
[j
], i
))
114 t
= mm
.r
[i
]; mm
.r
[i
] = mm
.r
[j
]; mm
.r
[j
] = t
;
115 t
= m
->r
[i
]; m
->r
[i
] = m
->r
[j
]; m
->r
[j
] = t
;
117 for (j
= 0; j
< mm
.n
; j
++) {
118 if (j
== i
) continue;
119 if (mp_testbit(mm
.r
[j
], i
)) {
120 mm
.r
[j
] = mp_xor(mm
.r
[j
], mm
.r
[j
], mm
.r
[i
]);
121 m
->r
[j
] = mp_xor(m
->r
[j
], m
->r
[j
], m
->r
[i
]);
131 /* --- @gfn_transform@ --- *
133 * Arguments: @gfn *m@ = conversion matrix to apply
134 * @mp *d@ = destination pointer
135 * @mp *x@ = input value
137 * Returns: The transformed element.
139 * Use: Transforms a field element according to the given matrix.
142 mp
*gfn_transform(gfn
*m
, mp
*d
, mp
*x
)
148 for (i
= 0, mp_scan(&sc
, x
); i
< m
->n
&& mp_step(&sc
); i
++)
149 if (mp_bit(&sc
)) y
= mp_xor(y
, y
, m
->r
[i
]);
154 /* --- @gfn_create@ --- *
156 * Arguments: @mp *p@ = modulus for polynomial basis
157 * @mp *beta@ = the generator of the normal basis, expressed
158 * relative to the polynomial basis
159 * @gfn *ntop@ = output normal-to-polynomail conversion matrix
160 * @gfn *pton@ = output polynomial-to-normal conversion matrix
162 * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$%
163 * doesn't generate a proper basis).
165 * Use: Constructs conversion matrices between polynomial and normal
166 * basis representations of binary field elements.
169 int gfn_create(mp
*p
, mp
*beta
, gfn
*ntop
, gfn
*pton
)
171 size_t m
= mp_bits(p
) - 1;
176 /* --- We start by building the the @ntop@ matrix --- *
178 * For mad reasons, the string representation of normal-basis elements is
182 gfreduce_create(&gr
, p
);
183 np
= ntop ? ntop
: &tmp
;
185 np
->r
= xmalloc(m
* sizeof(mp
*));
186 np
->r
[m
- 1] = MP_COPY(beta
);
187 for (i
= m
- 1; i
--; ) {
188 mp
*x
= gf_sqr(MP_NEW
, np
->r
[i
+ 1]);
189 np
->r
[i
] = gfreduce_do(&gr
, x
, x
);
191 gfreduce_destroy(&gr
);
193 /* --- That was easy -- now invert it --- */
196 if (ntop
) gfn_copy(pton
, np
); else *pton
= *np
;
197 if (gfn_invert(pton
)) {
199 if (ntop
) gfn_destroy(ntop
);
204 /* --- And we're done --- */
209 /*----- Test rig ----------------------------------------------------------*/
213 static int check(dstr
*v
)
215 mp
*p
= *(mp
**)v
[0].buf
;
216 mp
*beta
= *(mp
**)v
[1].buf
;
217 mp
*xp
= *(mp
**)v
[2].buf
;
218 mp
*xn
= *(mp
**)v
[3].buf
;
224 gfn_create(p
, beta
, &ntop
, &pton
);
225 gfn_identity(&ii
, pton
.n
);
226 for (i
= 0; i
< pton
.n
; i
++) {
227 y
= gfn_transform(&ntop
, y
, pton
.r
[i
]);
228 if (!MP_EQ(y
, ii
.r
[i
])) {
230 fprintf(stderr
, "*** inverse pton->ntop check failed (row %lu)\n",
232 MP_EPRINTX("*** p", p
); MP_EPRINTX("*** beta", beta
);
233 MP_EPRINTX("*** computed", y
);
237 y
= gfn_transform(&pton
, y
, xp
);
240 fprintf(stderr
, "*** pton failed\n");
241 MP_EPRINTX("*** p", p
); MP_EPRINTX("*** beta", beta
);
242 MP_EPRINTX("*** xp", xp
); MP_EPRINTX("*** xn", xn
);
243 MP_EPRINTX("*** computed", y
);
245 y
= gfn_transform(&ntop
, y
, xn
);
248 fprintf(stderr
, "*** ntop failed\n");
249 MP_EPRINTX("*** p", p
); MP_EPRINTX("*** beta", beta
);
250 MP_EPRINTX("*** xp", xp
); MP_EPRINTX("*** xn", xn
);
251 MP_EPRINTX("*** computed", y
);
253 gfn_destroy(&pton
); gfn_destroy(&ntop
);
254 mp_drop(p
); mp_drop(beta
); mp_drop(xp
); mp_drop(xn
); mp_drop(y
);
255 assert(mparena_count(MPARENA_GLOBAL
) == 0);
259 static test_chunk tests
[] = {
260 { "gfn", check
, { &type_mp
, &type_mp
, &type_mp
, &type_mp
} },
264 int main(int argc
, char *argv
[])
266 test_run(argc
, argv
, tests
, SRCDIR
"/t/gfn");
272 /*----- That's all, folks -------------------------------------------------*/