mersenneforum.org SPRP pseudoprime search.
 Register FAQ Search Today's Posts Mark Forums Read

 2010-07-14, 17:30 #1 3.14159     May 2010 Prime hunting commission. 24·3·5·7 Posts 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
 2010-07-14, 19:01 #2 3.14159     May 2010 Prime hunting commission. 24·3·5·7 Posts I think I'm going to have to lrn2python for this.
 2010-07-14, 19:26 #3 CRGreathouse     Aug 2006 3·1,993 Posts 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
 2010-07-14, 20:26 #4 3.14159     May 2010 Prime hunting commission. 24×3×5×7 Posts 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
 2010-07-14, 21:53 #5 CRGreathouse     Aug 2006 3·1,993 Posts 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.
 2010-07-14, 21:57 #6 3.14159     May 2010 Prime hunting commission. 24×3×5×7 Posts .. 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
 2010-07-14, 23:00 #7 3.14159     May 2010 Prime hunting commission. 24×3×5×7 Posts That is, if my assumption that the syntaxes for Java/C/Python are not similar is correct.

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 0 2017-06-24 12:11 SPWorley Computer Science & Computational Number Theory 11 2012-11-21 20:13 fenderbender Miscellaneous Math 22 2010-11-11 01:04 flouran Math 3 2009-06-01 05:04 amcfarlane Math 35 2006-09-02 23:02

All times are UTC. The time now is 15:46.

Wed Jun 23 15:46:31 UTC 2021 up 26 days, 13:33, 0 users, load averages: 2.63, 2.39, 2.27