Stack Overflow
Stack Overflow

Questions tagged [ntt]

Number Theoretic Transform - form of discrete Fourier transform on finite fields

Number Theoretic Transform

  • it is a form of discrete Fourier transform on finite fields
  • has the same properties and usage as DFT
  • mostly used for polynomial convolution
  • and fast bigint multiplications like Schönhage-Strassen multiplication
  • it is computed on integers so no rounding error occurs
  • but it can overflow if too big numbers or dataset is used in comparison to modulo prime
13 questions
18
votes
1 answer

Modular arithmetics and NTT (finite field DFT) optimizations

I wanted to use NTT for fast squaring (see Fast bignum square computation), but the result is slow even for really big numbers .. more than 12000 bits. So my question is: Is there a way to optimize my NTT transform? I did not mean to speed it by…
Spektre
  • 49,595
  • 11
  • 110
  • 380
9
votes
1 answer

Implementing FFT over finite fields

I would like to implement multiplication of polynomials using NTT. I followed Number-theoretic transform (integer DFT) and it seems to work. Now I would like to implement multiplication of polynomials over finite fields Z_p[x] where p is arbitrary…
minmax
  • 493
  • 3
  • 10
3
votes
0 answers

Number Theoretic Transform

I am having tough time while implementing NTT. After reading lot of tutorials on FFT and NTT from http://www.apfloat.org/ntt.html, http://codeforces.com/blog/entry/43499 and some others, I have implemented NTT taking advantage of Fermats theory…
Vinod Kollipara
  • 61
  • 7
3
votes
3 answers

Translation from Complex-FFT to Finite-Field-FFT

Good afternoon! I am trying to develop an NTT algorithm based on the naive recursive FFT implementation I already have. Consider the following code (coefficients' length, let it be m, is an exact power of two): /// /// Calculates the…
wh1t3cat1k
  • 3,146
  • 6
  • 32
  • 38
1
vote
1 answer

pattern of recursively splitting an array to odd and even elements

I am looking to find a pattern to recursively split an array to odd and even elements. I will try to describe the problem in the following: suppose we have an array of length 16 as: a=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] First iteration:…
elec_hi
  • 106
  • 1
  • 7
1
vote
1 answer

Is this template idea in C++ possible?

I'm trying to learn to implement template in C++. When I am changing my NTT (Number theoretic transform) code into one that uses template, which looks like this: template struct NTT{ int x = 0; NTT(){ long long p =…
Michael Ta
  • 13
  • 2
0
votes
1 answer

Circular convolution of binary vectors (mod 2) using NTT

Let x, y be vectors of length n, with entries either 1 or 0. I want to efficiently compute the circular convolution (x * y) mod 2 Where each component of the result is taken mod 2. I know how to do it using a Fast Fourier Transform (multiply Fourier…
Adomas Baliuka
  • 1,384
  • 2
  • 14
  • 29
0
votes
0 answers

Difference of Cooley Tukey-Gentleman Sande and DIT-DIF

Newbie here. I want to ask for NTT Implementation. We know there are several options like Cooley-Tukey, Gentleman-Sande, and Stockholm. Also, there's something called Decimation in Time (DIT) and Decimation in Frequency (DIF). As long as I know, the…
noc
  • 1
  • 1
0
votes
0 answers

Trying to parallelize NTT with cpp threads

it's my first time asking questions here so sorry if something is wrong. I'm trying to parallelize NTT using cpp threads but I'm simply lost here. I based the code on an article explaining the CUDA parallelization of NTT and adapted it so it made…
4rthb
  • 1
  • 1
0
votes
0 answers

Number theoretic transform multiplication is shifted

I've been working on code to multiply polynomials using NTT (FFT), and I made 2 different implementations, and used existing ones to validate, for example: https://www.nayuki.io/page/number-theoretic-transform-integer-dft,…
Robert Bräutigam
  • 7,514
  • 1
  • 20
  • 38
0
votes
1 answer

Multiple where condition in ntt framework mvc

Multiple where condition in following code result in only first row displaying, public bill_transaction Getbill_transaction(int id) { bill_transaction bill_transaction = db.bill_transaction.Where(m => m.Cust_Id == id &&…
Vikram M
  • 1
  • 2
0
votes
1 answer

Is there a best-known implementation for a Number Theoretic Transform on the 257 (2^8 + 1) finite field?

I'm a bit of a novice when it comes to implementing FFTs in general, but I have most of the basic ideas down I think. In this specific case, I've an implementation of the number theoretic transform on the 257 finite field. It's basically your…
MNagy
  • 423
  • 7
  • 20
0
votes
0 answers

Calculating W for NTT (Integer Fast Fourier Transform)

I'm attempting to implement an NTT (Number Theoretic Transform) in Objective C, however the abstract mathematical documents posted online are missing crucial details. I've found the following existing Question on Stack Overflow which purports to…
JasonA
  • 36
  • 2