1 files changed, 83 insertions, 0 deletions
diff --git a/Modules/_decimal/libmpdec/literature/bignum.txt b/Modules/_decimal/libmpdec/literature/bignum.txt
new file mode 100644
index 0000000..8a8731d
--- /dev/null
+++ b/Modules/_decimal/libmpdec/literature/bignum.txt
@@ -0,0 +1,83 @@
+
+
+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.
+
+
+