| |
| |
| Bignum support (Fast Number Theoretic Transform or FNT): |
| ======================================================== |
| |
| Bignum arithmetic in libmpdec uses the scheme for fast convolution |
| of integer sequences from: |
| |
| J. M. Pollard: The fast Fourier transform in a finite field |
| http://www.ams.org/journals/mcom/1971-25-114/S0025-5718-1971-0301966-0/home.html |
| |
| |
| The transform in a finite field can be used for convolution in the same |
| way as the Fourier Transform. The main advantages of the Number Theoretic |
| Transform are that it is both exact and very memory efficient. |
| |
| |
| Convolution in pseudo-code: |
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| |
| fnt_convolute(a, b): |
| x = fnt(a) # forward transform of a |
| y = fnt(b) # forward transform of b |
| z = pairwise multiply x[i] and y[i] |
| result = inv_fnt(z) # backward transform of z. |
| |
| |
| Extending the maximum transform length (Chinese Remainder Theorem): |
| ------------------------------------------------------------------- |
| |
| The maximum transform length is quite limited when using a single |
| prime field. However, it is possible to use multiple primes and |
| recover the result using the Chinese Remainder Theorem. |
| |
| |
| Multiplication in pseudo-code: |
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| |
| _mpd_fntmul(u, v): |
| c1 = fnt_convolute(u, v, P1) # convolute modulo prime1 |
| c2 = fnt_convolute(u, v, P2) # convolute modulo prime2 |
| c3 = fnt_convolute(u, v, P3) # convolute modulo prime3 |
| result = crt3(c1, c2, c3) # Chinese Remainder Theorem |
| |
| |
| Optimized transform functions: |
| ------------------------------ |
| |
| There are three different fnt() functions: |
| |
| std_fnt: "standard" decimation in frequency transform for array lengths |
| of 2**n. Performs well up to 1024 words. |
| |
| sixstep: Cache-friendly algorithm for array lengths of 2**n. Outperforms |
| std_fnt for large arrays. |
| |
| fourstep: Algorithm for array lengths of 3 * 2**n. Also cache friendly |
| in large parts. |
| |
| |
| List of bignum-only files: |
| -------------------------- |
| |
| Functions from these files are only used in _mpd_fntmul(). |
| |
| umodarith.h -> fast low level routines for unsigned modular arithmetic |
| numbertheory.c -> routines for setting up the FNT |
| difradix2.c -> decimation in frequency transform, used as the |
| "base case" by the following three files: |
| |
| fnt.c -> standard transform for smaller arrays |
| sixstep.c -> transform large arrays of length 2**n |
| fourstep.c -> transform arrays of length 3 * 2**n |
| |
| convolute.c -> do the actual fast convolution, using one of |
| the three transform functions. |
| transpose.c -> transpositions needed for the sixstep algorithm. |
| crt.c -> Chinese Remainder Theorem: use information from three |
| transforms modulo three different primes to get the |
| final result. |
| |
| |
| |
