Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to do trial division $p \pmod {\ell }$ for all $\ell $ belonging to the set of all primes between $2$ and $q$, and if $p \not\equiv 0 \pmod{\ell}$, check that $2^{p-1} \equiv 1 \pmod{p}$. If so, declare that $p$ might be prime. There is obviously no point in computing $2^{p-1} \pmod{p}$ if $3 \mid p$. Competing with the time it takes to run Mathematica's PrimeQ[ ], in Python 2.73 I wrote something like:

from numpy import *
def trialdivandfermat(p):                   
    for q in range(0,9999):
        if p%int(primes[z])==0:
            if z==9999:
                if pow(2,p-1,p)==1:
                    return p

for p in range(1+10**1000,10**10000,2):

Specifically searching for primes of the form $p = m^n \cdot h \pm 1$, $m$ odd, $h < m^n$ even, I have written that into my function trialdivandfermat(p).

Question: Are there faster ways to search for prime candidates of this form? How much trial division should I do if this is even the correct approach?

share|cite|improve this question
Hey thanks Austin. It did though. for p in range(1+101000,1010000,2): trialdivandfermat(p) goes at the end. – Samuel Hambleton Sep 28 '12 at 5:40
I can recommend some books to look at. Hans Riesel, Prime Numbers and Computer Methods for Factorization; Knuth, The Art of Computer Programming; Crandall and Pomerance, Prime Numbers, a Computational Perspective. – Gerry Myerson Sep 28 '12 at 5:50
Thank you Gerry. – Samuel Hambleton Sep 28 '12 at 5:59
And I can recommend a program called OpenPFGW which implements pretty well optimized versions of some of the algorithms for checking and proving primality of big numbers. – Peter Košinár Jun 20 '13 at 21:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.