# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Compute the number-theoretic transform of a list of integers

Contributed by:
Andrew Ortegaray

ResourceFunction["NumberTheoreticTransform"][{ finds the number-theoretic transform of the integer list | |

ResourceFunction["NumberTheoreticTransform"][{ finds the number-theoretic transform of the integer list | |

ResourceFunction["NumberTheoreticTransform"][{ finds the number-theoretic transform of the integer list |

The number-theoretic transform (NTT) *F*_{j} of an integer list *f*_{i} 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 *f*_{i} 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 *n*^{th} root of unity modulo *m*.

For a NTT of a list *f*_{i} 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 *n*^{th} root of unity modulus *m*,
(3) (*r*^{m}-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 2^{12}, however, all lists of length 2^{12} or greater must be a power of two, due to practical speed constraints.

If only the modulus is given in addition to *f*_{i}, 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.

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]:= |

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]:= |

Out[2]= |

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

In[3]:= |

Out[3]= |

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]:= |

Out[4]= |

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

In[5]:= |

Out[13]= |

In[14]:= |

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]:= |

Out[15]= |

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

In[16]:= |

Out[16]= |

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

In[17]:= |

Out[17]= |

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

In[18]:= |

Out[18]= |

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

In[19]:= |

Out[19]= |

- 1.0.0 – 10 February 2021

This work is licensed under a Creative Commons Attribution 4.0 International License