Number Theoretic Transform

Question

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 while choosing the modulo prime. But still I think I am missing something as invNTT(NNT(a)) is not coming out as 'a'.

Please have a look at my implementation.

public static long[] invNTT(long[] a){
    long[] ans = NTT(a,true);
    for(int i=0;i<a.length;i++)
        ans[i] = ans[i]/(a.length);
    return ans;
}

public static long modPow(long a,long n,long mod){
    if(n==1)
        return a;
    if(n==0)
        return 1;
    long tempRes = modPow(a,n/2,mod);
    tempRes = (tempRes*tempRes)%mod;
    if(n%2==1)
        tempRes = (tempRes*a)%mod;
    return tempRes;
}


public static long[] NTT(long[] a, boolean inverse){
    if(a.length==1)
        return a;
    int len = a.length, k = len/2;
    long p = (long)Math.pow(2, k)+1;
    print(a);
    System.out.println("p="+p);
    long even[] = new long[k];
    long odd[] = new long[k];
    for(int i=0,j=0;i<k;i++){
        even[i]=a[j++];
        odd[i]=a[j++];
    }
    long[] evenNTT = NTT(even,inverse);
    long[] oddNTT = NTT(odd,inverse);
    long res[] = new long[len];
    for(int i=0;i<k;i++){
        long root1 = inverse?modPowNeg(p,modPow(2,i,p))[2]:modPow(2,i,p);
        long root2 = inverse?modPowNeg(p,modPow(2,i+k,p))[2]:modPow(2,i+k,p);
        System.out.println(i+" and "+(i+k)+" th roots "+root1+" "+root2);
        res[i] = evenNTT[i]+(root1*oddNTT[i]);
        res[k+i] = evenNTT[i]+(root2*oddNTT[i]);
    }
    print(res);
    return res;
}

public static void print(long a[]){
    for(int i=0;i<a.length;i++)
        System.out.print(a[i]+" ");
    System.out.println();
}

}

I recently wrote an [NTT implementation](https://www.nayuki.io/page/number-theoretic-transform-integer-dft). Would you still like an answer to your question now? — Nayuki, Jun 05 '17 at 15:53
After reviewing your code, I can point out several places where the logic is incorrect. But I can't propose all the fixes needed to turn this into a working implementation. — Nayuki, Jun 18 '17 at 03:41
@Nayuki If possible can you provide NlogN solution. I see that your implementatio runs in n^2 time — Vinod Kollipara, Aug 08 '17 at 09:53
Please read the code on my page. It includes both the naive DFT algorithm and the Cooley-Tukey FFT. Sorry I can't give a personalized answer, because it's hard to explain how to fix numerous parts of your code to make it work. See: https://www.nayuki.io/res/number-theoretic-transform-integer-dft/SmallNumberTheoreticTransform.java — Nayuki, Aug 08 '17 at 15:55
If it shares features with FFT then NTT^4 = identity matrix and InvNTT = NTT^3 and InvNTT^4 = identity matrix. So you can find if the error is in NTT or InvNTT code. And if speed is not important just use the working code thrice. InvNTT^3 = NTT as well. — David Jonsson, Dec 06 '19 at 21:17

Number Theoretic Transform

0 Answers0