3 ms·
But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.
by e-khadem 2y ago
But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.
- xphos 2y agoHad no clue what NTT was but found this as a reference https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Number%20Theoretic%20Transform),calculations%20are%20done%20in%20integers https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Numbe....
- programjames 2y agoI prefer this reference: https://cp-algorithms.com/algebra/fft.html#number-theoretic-transform https://cp-algorithms.com/algebra/fft.html#number-theoretic-...
- dataflow 2y agoSee chapter 26 of the "FXT book". I just shared it here: https://news.ycombinator.com/item?id=40841355 https://news.ycombinator.com/item?id=40841355
- programjames 2y agoIs there a way to find groups with easy generators/primitive roots? I imagine you'd want a small root of unity, but also be able to choose a bigger modulus for extra big multiplications. Also, afaik it's discrete-logarithm level of difficulty to even find a generator if you choose a random modulus, though I don't know if it's easier to find a modulus after you choose the generator.
- adgjlsfhk1 2y agosince the groups you're looking at are is size log(n), you can do a lot of work without issue. as long as you do experimental it less work, it doesn't affect the runtime.
- archgoon 2y ago> though I don't know if it's easier to find a modulus after you choose the generator. Sure, pick a large prime. Double it and add 1 (and call it n). If it's still prime, then you know the prime factorization of n-1. Pick your generator, and check if it raised to the p is 1, or if squaring it is one. If not, it's a generator of the multiplicative group mod n.