fft function -- p,g or w provided?

[Lilian]

David,

Will we be given the values for p and g or omega for fft? The assignment
says that p and g will be provided for fftMult, but is not clear for fft and
ift

[David Zhao]

Yes, you will. Sample values are on the website.

What happens precisely is that you are given values for p and omega for fft and
ift. Then from those, you can easily derive correct values for p and omega for
fftMult.

David

Post by Lilian
David,
Will we be given the values for p and g or omega for fft? The assignment
says that p and g will be provided for fftMult, but is not clear for fft and
ift

[Lilian]

I'm still confused about the values p and w that will be given to fftMult.
Which one of the following case is right?

1. When fftMult is called, the p and w values passed to it will be p = kn +
1 and w = the principal nth root of unity modulo p. Then p and w will be
used by ift and fft in computing fftMult.

2. When fftMult is called, the p and w values passed to it will be p = 2kn +
1 and w = the principal 2nth root of unity modulo p. Then p' = kn + 1 and w
' = the principal nth root of unity modulo p can be derived, for use by ift
and fft in computing fftMult.

Post by David Zhao
Yes, you will. Sample values are on the website.
What happens precisely is that you are given values for p and omega for
fft and ift. Then from those, you can easily derive correct values for p
and omega for fftMult.
David

Post by Lilian
David,
Will we be given the values for p and g or omega for fft? The assignment
says that p and g will be provided for fftMult, but is not clear for fft and
ift

[David Zhao]

The second case is partially correct.

Remember that n denotes the lengths of the two polynomials/powerlists. The
convolution theorem states that we must pad the polynomials to length 2n before
applying fft and ift. Hence, p = 2kn+1 and w is a principal 2nth root of unity
mod p.

Think of it this way. Let n'=2n. Then w is a principal n'th root of unity
modulo p. Now we work with powerlists of length n' from this point on.

You should not use p' or w'. The algorithm is correct when using p and w in fft
and ift.

David

Post by Lilian
I'm still confused about the values p and w that will be given to fftMult.
Which one of the following case is right?
1. When fftMult is called, the p and w values passed to it will be p = kn +
1 and w = the principal nth root of unity modulo p. Then p and w will be
used by ift and fft in computing fftMult.
2. When fftMult is called, the p and w values passed to it will be p = 2kn +
1 and w = the principal 2nth root of unity modulo p. Then p' = kn + 1 and w
' = the principal nth root of unity modulo p can be derived, for use by ift
and fft in computing fftMult.