-
Notifications
You must be signed in to change notification settings - Fork 0
/
ZmodF_mul.h
194 lines (132 loc) · 6.13 KB
/
ZmodF_mul.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
/*============================================================================
This file is part of FLINT.
FLINT is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
FLINT is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with FLINT; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
===============================================================================*/
/******************************************************************************
ZmodF_mul.h
Copyright (C) 2007, David Harvey and William Hart
Routines for multiplication of elements of Z/pZ where p = B^n + 1,
B = 2^FLINT_BITS.
******************************************************************************/
#ifndef FLINT_ZMODF_MUL_H
#define FLINT_ZMODF_MUL_H
#ifdef __cplusplus
extern "C" {
#endif
#include <stdlib.h>
#include "gmp.h"
#include "mpn_extras.h"
#include "ZmodF_poly.h"
/*
Several algorithms for multiplication mod p:
ZMODF_MUL_PLAIN: use mpn_mul_n and then reduce mod p
ZMODF_MUL_THREEWAY: if n = 3m, do multiplication mod B^m + 1 and mod
B^2m - B^m + 1 separately, combine using CRT to get answer mod B^n + 1.
ZMODF_MUL_FFT: split into polynomial of length 2^depth with coefficients
mod (B^m + 1)*B^k, where k = 0, 1, or 2. Do negacyclic convolution mod
B^m + 1 using FFT; do convolution mod B^k using naive algorithm; combine
results by CRT.
*/
#define ZMODF_MUL_ALGO_PLAIN 0
#define ZMODF_MUL_ALGO_THREEWAY 1
#define ZMODF_MUL_ALGO_FFT 2
/*
This struct manages temporary allocation and tuning parameters for a
specific n.
*/
typedef struct
{
unsigned long n;
// possible values for algo are the ZMOD_MUL_ALGO_xyz constants above
int algo;
// this flag indicates that this struct is being used for squaring, in
// which case less memory will be allocated in the init routines
int squaring;
// scratch buffer:
// of length 2n (for ZMODF_MUL_ALGO_PLAIN)
// or length 3n+1 (for ZMODF_MUL_ALGO_THREEWAY)
// or length 3*k*2^depth (for ZMODF_MUL_ALGO_FFT)
// or NULL if not allocated
mp_limb_t* scratch;
// for ZMODF_MUL_ALGO_THREEWAY, m = n/3.
// for ZMODF_MUL_ALGO_FFT, the FFT operates mod B^m + 1, and the naive
// algorithm works mod B^k
unsigned long m, k;
// used only for ZMODF_MUL_ALGO_FFT
// (if squaring == 1, only the first one is init'd)
ZmodF_poly_t polys[2];
} ZmodF_mul_info_struct;
// ZmodF_mul_info_t allows reference-like semantics for
// ZmodF_mul_info_struct:
typedef ZmodF_mul_info_struct ZmodF_mul_info_t[1];
/*
Initialises ZmodF_mul_info_t for a given n. This function automatically
selects the best underlying multiplication algorithm for the given n.
The squaring flag is 1 if you intend to use this object for squaring. The
object will then use up less memory. If squaring == 0, it's still possible
to use this object for squaring, but if squaring == 1, you can't use it for
arbitrary multiplication.
WARNING: the multiplication time does NOT increase monotonically with n.
* If n is divisible by 3, the "threeway" algorithm is available, which is
faster than the "plain" algorithm for n >= 24 (on our opteron test
machine).
* For large n, the "fft" algorithm is available, but there are conditions on
the 2-divisibility of n (not very onerous though).
NOTE: this function uses stack based memory management.
*/
void ZmodF_mul_info_init(ZmodF_mul_info_t info, unsigned long n, int squaring);
// the following functions initialise with a specific algorithm:
void ZmodF_mul_info_init_plain(ZmodF_mul_info_t info, unsigned long n,
int squaring);
void ZmodF_mul_info_init_threeway(ZmodF_mul_info_t info, unsigned long n,
int squaring);
void ZmodF_mul_info_init_fft(ZmodF_mul_info_t info, unsigned long n,
unsigned long depth, unsigned long m,
unsigned long k, int squaring);
// releases resources
void ZmodF_mul_info_clear(ZmodF_mul_info_t info);
// sets res := a * b using the given ZmodF_mul_info_t object
void ZmodF_mul_info_mul(ZmodF_mul_info_t, ZmodF_t res, ZmodF_t a, ZmodF_t b);
// the following functions are for standalone multiplying/squaring, without
// the use of the precomputation stuff above:
/*
res := a * b
PRECONDITIONS:
Any combination of aliasing among res, a, b is allowed.
scratch must be a buffer of length 2*n, and must NOT alias a, b, res.
*/
void ZmodF_mul(ZmodF_t res, ZmodF_t a, ZmodF_t b, mp_limb_t* scratch,
unsigned long n);
/*
res := a * a
PRECONDITIONS:
a may alias res.
scratch must be a buffer of length 2*n, and must NOT overlap a or res.
*/
void ZmodF_sqr(ZmodF_t res, ZmodF_t a, mp_limb_t* scratch, unsigned long n);
// ============================================================================
// the following functions are exported for testing purposes:
void _ZmodF_mul_fft_split(ZmodF_poly_t poly, ZmodF_t x, unsigned long n);
void _ZmodF_mul_fft_combine(ZmodF_t x, ZmodF_poly_t poly,
unsigned long m, unsigned long k, unsigned long n);
void _ZmodF_mul_fft_convolve_modB(
mp_limb_t* out, mp_limb_t* in1, mp_limb_t* in2, unsigned long len);
void _ZmodF_mul_fft_convolve_modB2(
mp_limb_t* out, mp_limb_t* in1, mp_limb_t* in2, unsigned long len);
void _ZmodF_mul_threeway_reduce1(ZmodF_t res, ZmodF_t a, unsigned long m);
void _ZmodF_mul_threeway_reduce2(mp_limb_t* res, ZmodF_t a, unsigned long m);
#ifdef __cplusplus
}
#endif
#endif
// end of file ****************************************************************