chiark / gitweb /
math/mpx-mul4-amd64-sse2.S: SSE2 multipliers for AMD64.
[catacomb] / math / f-binpoly.c
CommitLineData
ceb3f0c0 1/* -*-c-*-
ceb3f0c0 2 *
3 * Binary fields with polynomial basis representation
4 *
5 * (c) 2004 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
ceb3f0c0 9 *
10 * This file is part of Catacomb.
11 *
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.
45c0fd36 16 *
ceb3f0c0 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.
45c0fd36 21 *
ceb3f0c0 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,
25 * MA 02111-1307, USA.
26 */
27
ceb3f0c0 28/*----- Header files ------------------------------------------------------*/
29
30#include <mLib/sub.h>
31
32#include "field.h"
f94b972d 33#include "field-guts.h"
9b8b6877 34#include "mprand.h"
ceb3f0c0 35
4edc47b8 36/*----- Polynomial basis --------------------------------------------------*/
ceb3f0c0 37
ceb3f0c0 38/* --- Field operations --- */
39
f94b972d 40static void fdestroy(field *ff) {
41 fctx_binpoly *f = (fctx_binpoly *)ff;
1d7857e7 42 gfreduce_destroy(&f->r); MP_DROP(f->f.q);
f94b972d 43 DESTROY(f);
44}
ceb3f0c0 45
f94b972d 46static mp *frand(field *f, mp *d, grand *r) {
47 return (mprand(d, f->nbits, r, 0));
48}
9b8b6877 49
a69a3efd 50static int fzerop(field *ff, mp *x) { return (MP_ZEROP(x)); }
ceb3f0c0 51
4edc47b8 52static mp *fadd(field *ff, mp *d, mp *x, mp *y) { return (gf_add(d, x, y)); }
ceb3f0c0 53
4edc47b8 54static mp *fmul(field *ff, mp *d, mp *x, mp *y) {
f94b972d 55 fctx_binpoly *f = (fctx_binpoly *)ff; d = gf_mul(d, x, y);
ceb3f0c0 56 return (gfreduce_do(&f->r, d, d));
57}
58
4edc47b8 59static mp *fsqr(field *ff, mp *d, mp *x) {
f94b972d 60 fctx_binpoly *f = (fctx_binpoly *)ff; d = gf_sqr(d, x);
ceb3f0c0 61 return (gfreduce_do(&f->r, d, d));
62}
63
f94b972d 64static mp *finv(field *ff, mp *d, mp *x) {
65 fctx_binpoly *f = (fctx_binpoly *)ff;
66 d = gf_modinv(d, x, f->r.p);
67 return (d);
68}
ceb3f0c0 69
f94b972d 70static mp *freduce(field *ff, mp *d, mp *x) {
71 fctx_binpoly *f = (fctx_binpoly *)ff;
72 return (gfreduce_do(&f->r, d, x));
73}
ceb3f0c0 74
f94b972d 75static mp *fsqrt(field *ff, mp *d, mp *x) {
76 fctx_binpoly *f = (fctx_binpoly *)ff;
77 return (gfreduce_sqrt(&f->r, d, x));
78}
ceb3f0c0 79
f94b972d 80static mp *fquadsolve(field *ff, mp *d, mp *x) {
81 fctx_binpoly *f = (fctx_binpoly *)ff;
82 return (gfreduce_quadsolve(&f->r, d, x));
83}
ceb3f0c0 84
85/* --- Field operations table --- */
86
4e66da02 87static const field_ops fops = {
bc985cef 88 FTY_BINARY, "binpoly",
34e4f738 89 fdestroy, frand, field_stdsamep,
ceb3f0c0 90 freduce, field_id,
91 fzerop, field_id, fadd, fadd, fmul, fsqr, finv, freduce, fsqrt,
92 fquadsolve,
93 0, 0, 0, 0
94};
95
96/* --- @field_binpoly@ --- *
97 *
98 * Arguments: @mp *p@ = the reduction polynomial
99 *
100 * Returns: A pointer to the field.
101 *
102 * Use: Creates a field structure for a binary field mod @p@.
103 */
104
105field *field_binpoly(mp *p)
106{
f94b972d 107 fctx_binpoly *f = CREATE(fctx_binpoly);
ceb3f0c0 108 f->f.ops = &fops;
109 f->f.zero = MP_ZERO;
110 f->f.one = MP_ONE;
432c4e18 111 f->f.nbits = mp_bits(p) - 1;
112 f->f.noctets = (f->f.nbits + 7) >> 3;
ceb3f0c0 113 gfreduce_create(&f->r, p);
432c4e18 114 f->f.m = f->r.p;
1d7857e7 115 f->f.q = mp_lsl(MP_NEW, MP_ONE, f->f.nbits);
ceb3f0c0 116 return (&f->f);
117}
118
4edc47b8 119/*----- Normal basis ------------------------------------------------------*/
120
4edc47b8 121/* --- Field operations --- */
122
123static void fndestroy(field *ff) {
f94b972d 124 fctx_binnorm *f = (fctx_binnorm *)ff; gfreduce_destroy(&f->f.r);
1d7857e7 125 gfn_destroy(&f->ntop); gfn_destroy(&f->pton); MP_DROP(f->f.f.q);
4edc47b8 126 DESTROY(f);
127}
128
129static int fnsamep(field *ff, field *gg) {
f94b972d 130 fctx_binnorm *f = (fctx_binnorm *)ff, *g = (fctx_binnorm *)gg;
4edc47b8 131 return (MP_EQ(f->ntop.r[0], g->ntop.r[0]) && field_stdsamep(ff, gg));
132}
133
f94b972d 134static mp *fnin(field *ff, mp *d, mp *x) {
135 fctx_binnorm *f = (fctx_binnorm *)ff;
136 return (gfn_transform(&f->ntop, d, x));
137}
4edc47b8 138
f94b972d 139static mp *fnout(field *ff, mp *d, mp *x) {
140 fctx_binnorm *f = (fctx_binnorm *)ff;
141 return (gfn_transform(&f->pton, d, x));
142}
4edc47b8 143
144/* --- Field operations table --- */
145
4e66da02 146static const field_ops fnops = {
4edc47b8 147 FTY_BINARY, "binnorm",
148 fndestroy, frand, fnsamep,
149 fnin, fnout,
150 fzerop, field_id, fadd, fadd, fmul, fsqr, finv, freduce, fsqrt,
151 fquadsolve,
152 0, 0, 0, 0
153};
154
155/* --- @field_binnorm@ --- *
156 *
157 * Arguments: @mp *p@ = the reduction polynomial
158 * @mp *beta@ = representation of normal point
159 *
160 * Returns: A pointer to the field.
161 *
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.
165 */
166
167field *field_binnorm(mp *p, mp *beta)
168{
f94b972d 169 fctx_binnorm *f = CREATE(fctx_binnorm);
4edc47b8 170 f->f.f.ops = &fnops;
171 f->f.f.zero = MP_ZERO;
172 f->f.f.one = MP_ONE;
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);
176 f->f.f.m = f->f.r.p;
1d7857e7 177 f->f.f.q = mp_lsl(MP_NEW, MP_ONE, f->f.f.nbits);
4edc47b8 178 gfn_create(p, beta, &f->ntop, &f->pton);
179 return (&f->f.f);
180}
181
ceb3f0c0 182/*----- That's all, folks -------------------------------------------------*/