- #1

Milkman

- 5

- 0

Hello everyone, I'm new to this forum, and I've registered to seek advice on this topic. What I'm attempting to do is multiply two very large numbers together, represented as polynomials, by the use of the number theory transform (ntt). I've done much research on this topic and I've had some success, but I have run into problems as well.

So far, I've coded a (hopefully) working ntt algorithm in c++ which is based off of some of the code found in the apfloat package (http://www.apfloat.org/apfloat/) . With this algorithm, I can successfully ntt a polynomial (represented as an array of numbers), and then inverse ntt the polynomial back to its original state.

Seeing as I could do that, I proceded to the next step in my project. I ntt'd a polynomial, squared each value, and then inverse ntt'd the new polynomial. This should yield a polynomial that represents the square of the original number, as this method works with a fast Fourier transform. Here's where my trouble lies. For some reason, sometimes I do get the correct polynomial as a result, and sometimes I don't. There seems to be no real pattern in the results that I get. If I use a different base for the polynomial, sometimes certain numbers will work when they didn't in another base, but no one base always yields correct results. I would like to know if the error lies in my ntt algorithm, or elsewhere in my method. I was attempting this with a modulus of 5, a length of 4, and a primitive root of 2 for the ntt, but i get similar results for a modulus of 17, a length of 16, and a primitive root of 3 as well.

As I said before, I know that with the fast Fourier transform, you can fft a polynomial, square each value, and inverse fft the new polynomial to get the square of the original number. My whole project relies on the premise that this also works for the number theory transform, which I believe it should, shouldn't it? Below is the code for my number theory transform. Any help with figuring out what is wrong would be much appreciated.

Thank you,

Mike

(tested and compiles with dev c++)

So far, I've coded a (hopefully) working ntt algorithm in c++ which is based off of some of the code found in the apfloat package (http://www.apfloat.org/apfloat/) . With this algorithm, I can successfully ntt a polynomial (represented as an array of numbers), and then inverse ntt the polynomial back to its original state.

Seeing as I could do that, I proceded to the next step in my project. I ntt'd a polynomial, squared each value, and then inverse ntt'd the new polynomial. This should yield a polynomial that represents the square of the original number, as this method works with a fast Fourier transform. Here's where my trouble lies. For some reason, sometimes I do get the correct polynomial as a result, and sometimes I don't. There seems to be no real pattern in the results that I get. If I use a different base for the polynomial, sometimes certain numbers will work when they didn't in another base, but no one base always yields correct results. I would like to know if the error lies in my ntt algorithm, or elsewhere in my method. I was attempting this with a modulus of 5, a length of 4, and a primitive root of 2 for the ntt, but i get similar results for a modulus of 17, a length of 16, and a primitive root of 3 as well.

As I said before, I know that with the fast Fourier transform, you can fft a polynomial, square each value, and inverse fft the new polynomial to get the square of the original number. My whole project relies on the premise that this also works for the number theory transform, which I believe it should, shouldn't it? Below is the code for my number theory transform. Any help with figuring out what is wrong would be much appreciated.

Thank you,

Mike

(tested and compiles with dev c++)

Code:

```
#include <iostream>
using namespace std;
// evaluates exponents, with a modulus
long power(long base,long power,long mod)
{
long final=1;
for (int i=0; i<power; i++)
{
final = ((final%mod) * (base%mod)) % mod;
}
return final;
}
// prints an array
void print(long x[],int N)
{
for (int i=0; i<N; i++)
{
cout<<x[i]<<endl;
}
cout<<endl;
}
// number theory transform algorithm
void ntt(long data[],long N,long mod,long pri)
{
long k;
long j;
long w;
long wj=1;
long wk=1;
long temp[N];
w = power(pri,((mod - 1)/N) % mod,mod) % mod;
for (j=0; j<N; j++)
{
temp[j]=0;
wk=1;
for (k=0; k<N; k++)
{
temp[j] = ((temp[j]%mod) + ((wk%mod)*(data[k]%mod))%mod) % mod;
wk = ((wk%mod)*(wj%mod)) % mod;
}
wj = ((wj%mod)*(w%mod)) % mod;
}
for (k=0; k<N; k++)
{
data[k] = temp[k] % mod;
}
}
// inverse number theory transform algorithm
void intt(long data[],long N,long mod,long pri)
{
long k;
long j;
long w;
long wk=1;
long wj=1;
long temp[N];
long rN;
w = power(pri,(mod-1-((mod-1)/N)) % mod,mod) % mod;
rN = power(N,(mod-2)%mod,mod) % mod;
for (j=0; j<N; j++)
{
temp[j]=0;
wk=1;
for (k=0; k<N; k++)
{
temp[j] = ((temp[j]%mod) + ((wk%mod)*(data[k]%mod))%mod) % mod;
wk = ((wk%mod)*(wj%mod)) % mod;
}
wj = ((wj%mod)*(w%mod)) % mod;
}
for (k=0; k<N; k++)
{
data[k]=((temp[k]%mod)*(rN%mod)) % mod;
}
}
// main
int main()
{
long N=16;
long mod=17;
long pri=3;
long data[N];
data[0]=3;
data[1]=1;
data[2]=0;
data[3]=0;
for (int i=4; i<N; i++)
{
data[i]=0;
}
print(data,N);
ntt(data,N,mod,pri);
print(data,N);
for (int i=0; i<N; i++)
{
data[i]=data[i]*data[i];
}
print(data,N);
intt(data,N,mod,pri);
print(data,N);
cout<<endl<<endl<<endl;
system("PAUSE");
return 0;
}
```

Last edited by a moderator: