5 ms·
Iterating over some huge search space in an essentially sequential manner is generally not going to be nearly performant as simply selecting an odd number at ra
by af3d 2y ago
Iterating over some huge search space in an essentially sequential manner is generally not going to be nearly performant as simply selecting an odd number at random. You could try using a generating polynomial instead such as f(x) = x^2 + x + 41 but even that isn't going to help much in the long run. (There are Diophantine equations which one day may prove useful for generating random primes however AFAICT finding efficient solutions is still currently considered a hard problem.)
- jdewerd 2y agoYes, but the more we mix sieve rejection into candidate selection the more we complicate the rule of thumb. "Reject even numbers as prime candidates" is probably OK to leave as an exercise for the reader, as is the equivalent "round every candidate to odd" optimization. The point about random vs sequential is well taken, though, and it doesn't complicate the rule of thumb, so I changed it.
- kevin_thibedeau 2y agoIncrementing a bignum is faster than another PRNG cycle.
- loeg 2y agoNeither is a significant amount of the time required to reject a candidate factor. The cheapest rejection test is "Bignum Division by 3" and something like 2/3 candidates will need more expensive further tests. https://news.ycombinator.com/item?id=40093136 https://news.ycombinator.com/item?id=40093136