I'm looking for an algorithm or three to use in testing for prime numbers. I'm most concerned about those representable as ints or longs (that is, less than 2^63). In that range, what tests are efficient?(adsbygoogle = window.adsbygoogle || []).push({});

At the moment, I'm using a combination of:

* The naive division algorithm with a precomputed list of primes (the empyrically-derived cutoff is 5,500,000, checking primes up to 2341).

* Strong n-probable prime tests, plus bounds due to Jaeschke that turn this into a determanistic test. (2- and 3- SPrPs below 1,373,653 are prime; 2-, 3-, and 5- SPrPs below 25,326,001 are prime; 2-, 3-, 5- and 7- SPrPs below 118,670,087,467 are either 3,215,031,751 or prime; etc.)

The problem is that I don't know how to extend the latter test beyond 341,550,071,728,321 (testing all the primes up to 17), and I don't know if there's a faster method at some cutoff. Any help here?

Edit: Bleichenbacher has numbers that extend this test to 10^16, but I'd still like to go higher. Any thoughts?

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Finding small primes (fast determanistic tests)

Loading...

Similar Threads for Finding small primes | Date |
---|---|

I How to find admissible functions for a domain? | Jan 31, 2018 |

I How to find the matrix of the derivative endomorphism? | Oct 22, 2017 |

I Finding the Kernel of a Matrix Map | Sep 15, 2017 |

A How can I find the collision time of 2 ellipsoids that rotate | May 22, 2017 |

Principal component analysis (PCA) with small number of observations | May 13, 2013 |

**Physics Forums - The Fusion of Science and Community**