mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-07-14, 17:30   #1
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

110100100002 Posts
Default SPRP pseudoprime search.

I managed to find three additional base 2, 3 SPRP pseudoprimes, besides 1373653:
They are 1987021, 2284453, and 3116107. Their factorizations are as follows:
1987021 = 997 * 1993
2284453 = 1069 * 2137
3116107 = 883 * 3529

Also: Is there any program that can look for SPRP pseudoprimes? It would make things far easier if there were indeed such a program. At the moment, all I do have is an indirect pseudoprime generator, based on the Fermat test. Albeit it does give SPRP pseudoprimes, it also gives Carmichael pseudoprimes, which are undesirable in this case. Or is there at least some pseudocode available for such?

Last fiddled with by 3.14159 on 2010-07-14 at 17:32
3.14159 is offline   Reply With Quote
Old 2010-07-14, 19:01   #2
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

I think I'm going to have to lrn2python for this.
3.14159 is offline   Reply With Quote
Old 2010-07-14, 19:26   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

It's pretty easy in Pari:
Code:
isSPRP(n,b=2)={
	my(s=valuation(n-1,2),d=n>>s);
	n = Mod(b, n)^d;
	if (n == 1, return(1));
	while(s--,
		if (n == -1, return(1));
		n = n^2;
	);
	n == -1
};

pseudo(n)=!isprime(n)&isSPRP(n,2)&isSPRP(n,3)

forstep(n=3,1e7,2,if(pseudo(n),print(n)))
gives
Code:
1373653
1530787
1987021
2284453
3116107
5173601
6787327
in about 1 minute. (Of course this can be improved; I just wrote the programs on the spot.)

Last fiddled with by CRGreathouse on 2010-07-14 at 19:27
CRGreathouse is offline   Reply With Quote
Old 2010-07-14, 20:26   #4
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

168010 Posts
Default

How would that be written in Python syntax? Learning to write in Python isn't going to be as easy as I thought it would be.

Last fiddled with by 3.14159 on 2010-07-14 at 21:23
3.14159 is offline   Reply With Quote
Old 2010-07-14, 21:53   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111001102 Posts
Default

You won't be able to do it directly like I did in Python since that doesn't have number theory libraries installed like Pari does. You'd need to write your own modular exponentiation routine. It's not too hard, though -- Google "exponentiation by squaring" or similar.
CRGreathouse is offline   Reply With Quote
Old 2010-07-14, 21:57   #6
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

.. I first need to start with the basics: Writing my own trial division program. I'd need to be able to write the simplest program before getting into anything more complex.
Here's an example of a trial division program someone wrote: Also: Your post number is divisible by three consecutive primes: 7, 11, 13.
Code:
# yields 2, 3, 5 and all numbers coprime to 2, 3 and 5 (except 1)
def trialdivisors():

    yield 2
    yield 3
    yield 5
    yield 7
    yield 11
    yield 13
    yield 17
    yield 19
    yield 23
    yield 29

    n = 31
    ds = [6, 4, 2, 4, 2, 4, 6, 2]

    while 1:
        for d in ds:
            yield n
            n += d

sorry = "(last factor may be composite " \
    + "but has no divisors less than 100000000)"

# apply trial division and print out factors
def factor(n):
    print "Prime factorisation of %d is:" % n
    ts = trialdivisors()
    t = ts.next()
    while t * t <= n:
        if n % t:
            t = ts.next()
            if t > 100000000:
                print n
                print sorry
                return
        else:
            print t,
            n //= t
    print n

factor(int(n))
Also: Yes, but most of the implementations are in Java or C, not Python.
It's kind of difficult to do whenever you have to search for hours for the proper syntax.

Last fiddled with by 3.14159 on 2010-07-14 at 22:07
3.14159 is offline   Reply With Quote
Old 2010-07-14, 23:00   #7
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

That is, if my assumption that the syntaxes for Java/C/Python are not similar is correct.
3.14159 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modified Fermat pseudoprime devarajkandadai Number Theory Discussion Group 0 2017-06-24 12:11
Using CUDA to find better SPRP classifiers SPWorley Computer Science & Computational Number Theory 11 2012-11-21 20:13
Miller-Rabin Strong Probable Prime Test (SPRP) fenderbender Miscellaneous Math 22 2010-11-11 01:04
Strong Pseudoprime Distribution flouran Math 3 2009-06-01 05:04
Strong Pseudoprime Question amcfarlane Math 35 2006-09-02 23:02

All times are UTC. The time now is 14:18.

Tue Jul 14 14:18:05 UTC 2020 up 111 days, 11:51, 1 user, load averages: 1.46, 1.55, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.