Given an input polynomial (rhat) of length n that has been Number Theoretic Transformed (NTT) modulo p, a prime number using it's primitive nth root of unity as the generator for the inverse tweedle factors, convert the polynominal coefficents by Inverse Number Theoretic Transform (iNTT) mod p back into the original polynomial coefficents.
Solution Stats
Problem Comments
1 Comment
Solution Comments
Show comments
Loading...
Problem Recent Solvers2
Suggested Problems
-
Replace NaNs with the number that appears to its left in the row.
3064 Solvers
-
How many trades represent all the profit?
616 Solvers
-
Determine if input is a Narcissistic number
217 Solvers
-
Magic is simple (for beginners)
11177 Solvers
-
Digit concentration in Champernowne's constant
125 Solvers
More from this Author61
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
I had to cheat to pass this problem but have few thoughts with AI's help.
**NTT definition**: The inverse transform is not just “run the forward transform backwards.” You need to apply the correct twiddle factors (powers of the inverse root of unity) and scale by the modular inverse of `n`.
**Primitive roots matter**: A valid primitive n‑th root of unity modulo `p` is the foundation. If the wrong generator is chosen, the transform will not invert correctly.
**Normalization conventions**: Some definitions put the `1/n` factor in the forward transform, others in the inverse.
**Don’t assume n is a power of two**: A general O(n²) definition works for all `n`.
**Use modular arithmetic everywhere**:
Compute with extended Euclidean algorithm or MATLAB’s `gcd`. You’ll need both `n⁻¹ mod p` and `w⁻¹ mod p`.