Diskuse:Millerův–Rabinův test prvočíselnosti
Přidat témaVzhled
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)
Zahajte diskusi ke stránce Millerův–Rabinův test prvočíselnosti
Diskusní stránky jsou místa, kde lidé diskutují o tom, jak vytvořit co nejlepší Wikipedii. Tuto diskusní stránku můžete použít k zahájení diskuse s ostatními o tom, jak zlepšit stránku Millerův–Rabinův test prvočíselnosti.