20100714, 17:30  #1 
May 2010
Prime hunting commission.
2^{4}·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 20100714 at 17:32 
20100714, 19:01  #2 
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
I think I'm going to have to lrn2python for this.

20100714, 19:26  #3 
Aug 2006
3·1,993 Posts 
It's pretty easy in Pari:
Code:
isSPRP(n,b=2)={ my(s=valuation(n1,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))) Code:
1373653 1530787 1987021 2284453 3116107 5173601 6787327 Last fiddled with by CRGreathouse on 20100714 at 19:27 
20100714, 20:26  #4 
May 2010
Prime hunting commission.
2^{4}×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 20100714 at 21:23 
20100714, 21:53  #5 
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.

20100714, 21:57  #6 
May 2010
Prime hunting commission.
2^{4}×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)) 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 20100714 at 22:07 
20100714, 23:00  #7 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
That is, if my assumption that the syntaxes for Java/C/Python are not similar is correct.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modified Fermat pseudoprime  devarajkandadai  Number Theory Discussion Group  0  20170624 12:11 
Using CUDA to find better SPRP classifiers  SPWorley  Computer Science & Computational Number Theory  11  20121121 20:13 
MillerRabin Strong Probable Prime Test (SPRP)  fenderbender  Miscellaneous Math  22  20101111 01:04 
Strong Pseudoprime Distribution  flouran  Math  3  20090601 05:04 
Strong Pseudoprime Question  amcfarlane  Math  35  20060902 23:02 