Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 *
primes=array([2,3,...,104729])
def trialdivandfermat(p):                   
    z=0                                                                    
    for q in range(0,9999):
        if p%int(primes[z])==0:
            break
        else:
            z=z+1
            if z==9999:
                if pow(2,p-1,p)==1:
                    return p
                break 

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

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|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
4  
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

 
discard

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

Browse other questions tagged or ask your own question.