Diskuse:Millerův–Rabinův test prvočíselnosti

Nejsem si úplně jist, ale v modulární aritmetice nám rychlá Fourierova transformace násobení příliš neurychlí. Problém je v závěrečné operaci modulo N. Na druhou stranu při klasickém násobení můžeme modulo nahradit odčítáním, kdykoli překročíme N. Bojím se, že v obou případech končíme se složitostí O(n^2), kde n je počet cifer čísla N. Hippo.69 (diskuse) 5. 3. 2013, 20:47 (UTC)

Nechápu, v čem má spočívat rozdíl a obavy. Viz en:Computational complexity of mathematical operations. Samozřejmě, pokročilejší metody se uplatní až od velkých číslel (včetně velkého modula). Ale to neznamená, že se neuplatní. A nahrazovat modulo odčítáním bude obecně poměrně dost neefektivní (nespletl jste si násobení se sčítáním?). --Tchoř (diskuse) 5. 3. 2013, 22:54 (UTC)

OK beru zpět, vypadá to, že závěrečné modulo není až tak velký problém. Zvláště pokud použijeme Barrettovu redukci. Vracím článek k předchozí verzi.Hippo.69 (diskuse) 7. 3. 2013, 22:57 (UTC)