0
$\begingroup$

Im doing a problem for al algorithms class to multiply 2 polynomials using FFT, and am confused as to why they picked 9 in step 3 in this document: http://www.cc.gatech.edu/~venkat/6505/notes/fftex.pdf

Which means the last piece of the puzzle im missing is how i can find the principal N-th root of unity for any 2 arbitrarily chosen polynomials. (in my case, they are 1+x+2x^2 and 2+3x)

1 Answers 1

2

They are working in the field of integers modulo 41.

We have $9^2 = 81 = 40 \bmod 41 = -1 \bmod 41$ and so $9^4=(9^2)^2=1\bmod 41$.

They could have picked 32 as well.

All you need to do is find an integer that when raised to the $N$th power modulo your prime $p$ gives 1, but when raised to any smaller (positive) power does not give 1 mod $p$.