- p je vzdy rovno 2^27*15 + 1
- dostanes dve N bitova cisla, N <= 2^27.
- najdes nejvetsi B, aby B^2 * ((N/log_{2}B)+1) < p.
Kvuli vykonu je lepsi zvolit B mocninu dvojky.
Pak muzes /B pocitat jako shift doprava
a "%B" pocitat jako and. Navic rychle najdes
B ve formatu 2^neco, protoze staci vyzkouset
par moznosti.
- zapises ta cisla v bazi B a tim ziskas polynomy
- nad polynomy provedes FFT, ktere je nad konecnym telesem Z_p.
Mas 2^27-primitivni odmocninu omega=440564289. Pokud
poustis FFT na mensi delce [treba 2^10], spravnou
omegu spoctes jako omega^(27-10).
- vynasobis polynomy po koeficientech
- provedes FFT nazpet
- do vysledneho polyhomu dosadis B [zase pouze shifty]
- a je to :)