20101109, 01:21  #1 
Jul 2007
11_{16} Posts 
MillerRabin Strong Probable Prime Test (SPRP)
From Chris Caldwell's Prime pages (1) (2) , there's a definition of Strong Probable Primes. It matches Wikipedia and a few other googled sources.
But this test doesn't seem to work. Let's test n=7 with the SPRP base a=35. n1=6, so d=3, s=1. 35^3 mod 7 = 0. This isn't 1, so it fails the first test. (35^3)^2 mod 7 =0. This isn't 1, so it fails the second test. Therefore 7 is not an 35SPRP. So 7 is not prime. What's the flaw in the logic above? My bad math? Is it just a bad definition which should add some restriction that composite base values a are not allowed? Or another unlisted requirement that a mod n cannot be 0? 
20101109, 01:58  #2  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
35 is a multiple of 7. So of course 35^3 = 0 mod 7, along with any powers of 35^3. Maybe there's a condition that isn't being made clear, that a and p must be coprime, or at least that a can't be a multiple of p.
Composite bases are allowed, though: Quote:
Last fiddled with by MiniGeek on 20101109 at 02:20 

20101109, 03:05  #3 
Aug 2006
1011101011011_{2} Posts 
Generally, you want to choose bases between 2 and p2, inclusive. You won't run into trouble in this range.

20101109, 05:44  #4 
Jul 2007
17 Posts 
Thanks for verifying my math!
So the question is actually whether the definition of an SPRP is wrong and needs a special caveat for these cases, or whether it's OK for primes to fail the SPRP test. Should we just say that "n is an aSPRP" is undefined if n < a+2? Or just say that all values n <=a are an aSPRP. Both definitions preserve the useful fact that if n is not an aSPRP, it is composite. 
20101109, 12:36  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:
specify (a,p) = 1. 

20101109, 13:13  #6  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Quote:
Last fiddled with by MiniGeek on 20101109 at 13:27 

20101109, 13:35  #7  
Nov 2003
1D24_{16} Posts 
Quote:
Standard number theoretic usage. 

20101109, 14:41  #8 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
That doesn't help me. Will you please tell me what it is? Or perhaps, is there a resource that would help me understand standard number theoretic usages when it's not spelled out?
If not, will someone else tell me what he means? Last fiddled with by MiniGeek on 20101109 at 14:41 
20101109, 14:48  #9  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Numbers. Or any other text on elementary number theory. I can recommend several others if Hardy & Wright is not to your liking. As to why I won't just *give* the answer: Give a man a fish and he eats for a day. Teach a man to fish and he eats for a lifetime. 

20101109, 15:11  #10 
Aug 2006
13533_{8} Posts 

20101109, 15:26  #11  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Quote:
Thanks. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Probabilistic primality tests faster than Miller Rabin?  mathPuzzles  Math  14  20170327 04:00 
Hi, how can I test my probable prime number?  mohdosa  Information & Answers  22  20141010 11:34 
MillerRabin test questions  firejuggler  Miscellaneous Math  6  20111222 05:57 
Number of RabinMiller NonWitnesses  ATH  Math  0  20110730 16:42 
Why no RabinMiller Tests ?  Axel Fox  Math  13  20040628 16:07 