Oblicza iloczyn wielomianów z użyciem FFT w pierścieniu
liczb całkowitych modulo p
Wpisujemy współczynniki wielomianów A i B
Wtedy k =
mink(2k > max(st A, st B)),
n = 2k,
m = 2n, p = 2n+1,
omega = 2,
1/m = 2m-k-1 mod p lub p = 22n+1,
omega = 22,
1/m = 22m-k-1 mod p lub p = 2rn+1,
omega = 2r,
1/m = 2rm-k-1 mod p p dobrać żeby p >
n*max(a0,...,an-1)*max(b0,...,bn-1)
jeśli są współczynniki ujemne, to należy p dobrać tak żeby p >
2*n*max(|a0|,...,|an-1|)*max(|b0|,...,|bn-1|)
oraz w ostatecznym wyniku odjąć od współczynników > p/2 liczbę pGrzegorz Bancerek