Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 NumberTheoreticTransform

Source Notebook

Compute the number-theoretic transform of a list of integers

Contributed by: Andrew Ortegaray

ResourceFunction["NumberTheoreticTransform"][{f1,f2,…},r,m]

finds the number-theoretic transform of the integer list fi with the given root r and modulus m.

ResourceFunction["NumberTheoreticTransform"][{f1,f2,…},m]

finds the number-theoretic transform of the integer list fi with given modulus prime m and automatically chosen root r.

ResourceFunction["NumberTheoreticTransform"][{f1,f2,…}]

finds the number-theoretic transform of the integer list fi with automatically chosen root r and modulus m.

Details

The number-theoretic transform (NTT) Fj of an integer list fi of length n with root r and modulus m is defined to be .
ResourceFunction["NumberTheoreticTransform"] to a list of integers is analogous to Fourier for a list of reals.
For a NTT of a list fi of length n to support convolution with prime modulus m, the m must be of the form kn+1 for some integer k. The root r must then be chosen to be an nth root of unity modulo m.
For a NTT of a list fi of length n to support convolution with composite modulus m in general: (1) n must possess a ModularInverse modulo m, (2) r must be an nth root of unity modulus m, (3) (rm-1) is relatively prime to m for all integers m from 1 to m-1.
There are other equivalent conditions that can be chosen to establish the convolution property of an NTT.
ResourceFunction["NumberTheoreticTransform"][] is compatible with lists of any length less than 212, however, all lists of length 212 or greater must be a power of two, due to practical speed constraints.
If only the modulus is given in addition to fi, then it must be chosen to be prime and of the form kn+1.
The initial use of ResourceFunction["NumberTheoreticTransform"] may be slow due to one-time compilation of functions. Subsequent uses will execute quickly.

Examples

Basic Examples (3) 

The number-theoretic transform of the list {1,2,3} can be computed with modulus 7 = 2 × 3 + 1 and root PrimitiveRoot[7]2:

In[1]:=
ResourceFunction["NumberTheoreticTransform"][ {1, 2, 3}, PrimitiveRoot[7]^2 , 7]
Out[1]=

The number-theoretic transform of the list Range[10] can be computed with modulus 31 = 10 × 3 + 1 and root PrimitiveRoot[31]10:

In[2]:=
ResourceFunction["NumberTheoreticTransform"][ Range[10], PrimitiveRoot[31]^10 , 31]
Out[2]=

The number-theoretic transform of the list Range[16] can be computed with modulus 4129 and root 1163:

In[3]:=
ResourceFunction["NumberTheoreticTransform"][Range[16]]
Out[3]=

Properties and Relations (4) 

The Inverse of a number-theoretic transform is a transform with the same modulus m, but with root ModularInverse[r,m] and prefactor ModularInverse[n,m]:

In[4]:=
a = Range[5]; A = ResourceFunction["NumberTheoreticTransform"][a, 53, 131]; invr = ModularInverse[53, 131]; invn = ModularInverse[5, 131]; a == ResourceFunction["NumberTheoreticTransform"][ invn A, invr, 131]
Out[4]=

Number-theoretic transforms can be used immediately to compute exact convolutions of non-negative integer lists:

In[5]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/f2e3a668-5d0b-4340-b879-86c34ab04470"]
Out[13]=
In[14]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/f77a3190-0845-48d2-ad67-63572ffe58de"]
Out[14]=

Number-theoretic transforms can be used to compute exact convolutions of general integer lists, including negative integers. However, an offset correction needs to be computed first:

In[15]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/826404b3-e94f-47e4-a05e-cf4d2f53002e"]
Out[15]=

Number-theoretic transforms can be computed much faster on lists with lengths that are powers of two:

In[16]:=
t1 = First@ RepeatedTiming@ ResourceFunction["NumberTheoreticTransform"][ ConstantArray[1, 2^10], 10302, 12289]; t2 = First@ RepeatedTiming@ ResourceFunction["NumberTheoreticTransform"][ ConstantArray[1, 2^10 - 1], 10302, 12289]; N[t2 /t1]
Out[16]=

Possible Issues (2) 

If the chosen modulus m is too small, then overflow may cause the number-theoretic transform to have no inverse:

In[17]:=
a = 5^Range[5]; A = ResourceFunction["NumberTheoreticTransform"][a, 53, 131]; invr = ModularInverse[53, 131]; invn = ModularInverse[5, 131]; a == ResourceFunction["NumberTheoreticTransform"][ invn A, invr, 131]
Out[17]=

If the chosen modulus m is too small, then overflow may cause the number-theoretic transform to not support convolutions:

In[18]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/5687e31c-8601-4a6d-8fe4-0e2b1572bbe7"]
Out[18]=

Neat Examples (1) 

Using convolution with padding, number-theoretic transforms can compute polynomial multiplications:

In[19]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/b01bf4c9-6e4f-4664-a38e-d72c5de6d962"]
Out[19]=

Publisher

Wolfram Summer School

Version History

  • 1.0.0 – 10 February 2021

Source Metadata

  • Citation:
    • Nussbaumer, Henri J., "Number Theoretic Transforms." Fast Fourier Transform and Convolution Algorithms, Springer: Berlin, Heidelberg, 211-240, 1981.

Related Resources

License Information