Dunjeon_Master's blog

FFT
By Dunjeon_Master, history, 5 years ago, In English

Is there any prime number larger than 998244353 which is such that we can apply NTT on arrays of size up to 2^19 and the prime number is greater than 1e11

  • Vote: I like it
  • -35
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, hide # |
← Rev. 3  
Vote: I like it +10 Vote: I do not like it

Any prime that is greater than $$$10^{11}$$$ and is in the form of $$$k \times 2^{19}+1$$$, where $$$k$$$ is an integer, should fit your requirements.

Note that $$$998244353 = 119 \times 2^{23}+1$$$.

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Why did gray guy need FFT? Go learn bubble sort

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

$$$100000595969$$$ is the smallest prime $$$p$$$ above $$$10^{11}$$$ with $$$p \equiv 1 \pmod{2^{19}}$$$ (found with a simple python3 session). The smallest primitive root is $$$3$$$.

→ Reply