/usr/include/FLINT/ZmodF_mul.h is in libflint-dev 1.011-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 ****************************************************************
|