Timeline for At what point does Miller-Rabin become faster than trial division?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2013 at 13:26 | answer | added | Aaron Meyerowitz | timeline score: 2 | |
| Apr 3, 2013 at 13:17 | comment | added | Emil Jeřábek | Note that they also do not divide $N$ itself by each small prime individually, but take the primes in batches whose product fits into the machine word, compute $N$ modulo this product, and try dividing the remainder by the primes. This reduces the number of operations performed on the full $\log N$-bit integers. | |
| Apr 3, 2013 at 13:05 | comment | added | Emil Jeřábek | @Gerry: GMP (github.com/AlexeiSheplyakov/gmp.pkg/blob/master/mpz/pprime_p.c) tests primes up to $\log_2N$. The comment in the code suggests that this is not necessarily optimal, but I suppose the rationale is that one iteration of MR takes about $O(\log N)$ arithmetical operations (on numbers of $O(\log N)$ bits), so trial division by primes up to $O(\log N)$ takes still less time. On the other hand, if the input is random, it catches all but a fraction $1/\log\log N$ of composites, and this will not get substantially smaller by increasing the limit. | |
| Apr 3, 2013 at 12:52 | comment | added | James Cranch | From memory, I think Henri Cohen's book ("A Course in Computational Algebraic Number Theory") suggests precomputing primes up to 65536 and trial dividing up to there. I hope I am not libelling Cohen here: please treat this comment with the doubt it deserves. | |
| Apr 3, 2013 at 12:15 | comment | added | Gerry Myerson | @Emil, how many primes in a handful? | |
| Apr 3, 2013 at 11:53 | comment | added | user9072 | Is there a reason you insist to comparing to Miller--Rabin or does it stand for 'some better algorithm'. (AFAIK, in fact in practise other things are used.) | |
| Apr 3, 2013 at 10:40 | comment | added | Emil Jeřábek | Surely this depends heavily on the implementation and on the desired accuracy (i.e., how many iterations of Miller–Rabin you run for the given $N$). I’d guess Miller–Rabin might become faster already for numbers of the order of millions, but any realistic implementation will start with trial division by a handful of small primes anyway. | |
| Apr 3, 2013 at 10:04 | comment | added | joro | I mean trial division to some small bound. | |
| Apr 3, 2013 at 10:03 | comment | added | joro | When hunting for very large primes, trial division is the first thing to try. It doesn't imply primality, but may show N is composite, saving a lot of time. | |
| Apr 3, 2013 at 10:00 | history | asked | langos | CC BY-SA 3.0 |