manjunath1996's blog

Doubt Regarding NTT
By manjunath1996, history, 8 years ago, In English

I have a doubt about how devide polynomial in NTT.Specifically in this problem link :https://www.codechef.com/JULY16/problems/POLYEVAL/ In editorial and many solution,they are deviding polynomial into 3 polynomials as A(x^3)+xA(x^3)+x^2A(x^3). I didn't understand why it is needed to devide the polynomial into 3 polynomial first and then apply NTT. Can we take whole polynomial into single array and do it's NTT.Please Clarify my doubt.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +86 Vote: I do not like it

Only LiTi understood FFT and NTT. Ask him.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +53 Vote: I do not like it

LiTi Can you please explain it??

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

mod = 3*2^18+1 . its convenient to divide it into three portions so that size of each portion is a power of 2 . you can even initially form three polynomials each of size 2^18 and perform NTT on all three of them so that they finally produce values for 3*2^18 distinct points.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Why is it needed to decompose in 3 polynomials ?? Can we concat 2^18 zeroes so that final polynomial becomes of 2^20 ie 4*(2^18) numbers which is perfect square and do NTT??

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because the mod is 3*2^18+1 so you can't find a primitive root that gives a cycle of size 2^20, the limit is 2^18

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +93 Vote: I do not like it

    Wondering if LiTi will approve this.

    → Reply
»
8 years ago, # |
  Vote: I like it +46 Vote: I do not like it

So maybe on his birthday, LiTi will be willing to explain NTT? Happy birthday, LiTi :)

PS: We are waiting for you :D

→ Reply