mersenneforum.org Miller-Rabin Strong Probable Prime Test (SPRP)
 Register FAQ Search Today's Posts Mark Forums Read

 2010-11-09, 01:21 #1 fenderbender     Jul 2007 1710 Posts Miller-Rabin 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. n-1=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 35-SPRP. 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?
2010-11-09, 01:58   #2
Mini-Geek
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:
 Finally, Worley (on-web, unpublished) suggests the following, If n < 170,584,961 is a 350 and 3958281543-SPRP, then n is prime. If n < 75,792,980,677 is a 2, 379215, and 457083754-SPRP, then n is prime. If n < 21,652,684,502,221 is a 2, 1215, 34862, and 574237825-SPRP, then n is prime.
Note that nearly all of those bases are composite.

Last fiddled with by Mini-Geek on 2010-11-09 at 02:20

 2010-11-09, 03:05 #3 CRGreathouse     Aug 2006 3·1,993 Posts Generally, you want to choose bases between 2 and p-2, inclusive. You won't run into trouble in this range.
 2010-11-09, 05:44 #4 fenderbender     Jul 2007 1116 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 a-SPRP" is undefined if n < a+2? Or just say that all values n <=a are an a-SPRP. Both definitions preserve the useful fact that if n is not an a-SPRP, it is composite.
2010-11-09, 12:36   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by fenderbender 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.
Caldwell's page is wrong. Well, at least incomplete. It needs to
specify (a,p) = 1.

2010-11-09, 13:13   #6
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts

Quote:
 Originally Posted by R.D. Silverman Caldwell's page is wrong. Well, at least incomplete. It needs to specify (a,p) = 1.
To be more specific, is that function supposed to be GCD or the Legendre symbol or what?

Last fiddled with by Mini-Geek on 2010-11-09 at 13:27

2010-11-09, 13:35   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Mini-Geek To be more specific, is that function supposed to be GCD or the Legendre symbol or what?

Standard number theoretic usage.

2010-11-09, 14:41   #8
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts

Quote:
 Originally Posted by R.D. Silverman Standard number theoretic usage.
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 Mini-Geek on 2010-11-09 at 14:41

2010-11-09, 14:48   #9
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by Mini-Geek 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?
See, for example, Hardy & Wright. Introduction to the Theory of
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.

2010-11-09, 15:11   #10
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by Mini-Geek That doesn't help me. Will you please tell me what it is?
It's an old notation for the gcd.

2010-11-09, 15:26   #11
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 Originally Posted by R.D. Silverman See, for example, Hardy & Wright. Introduction to the Theory of 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.
I've requested that my local public library get it. If it looks like it'd be good to have around for reference, I might buy a copy for myself.
Quote:
 Originally Posted by CRGreathouse It's an old notation for the gcd.
Thanks.

 Similar Threads Thread Thread Starter Forum Replies Last Post mathPuzzles Math 14 2017-03-27 04:00 mohdosa Information & Answers 22 2014-10-10 11:34 firejuggler Miscellaneous Math 6 2011-12-22 05:57 ATH Math 0 2011-07-30 16:42 Axel Fox Math 13 2004-06-28 16:07

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

Wed Jun 23 14:30:35 UTC 2021 up 26 days, 12:17, 0 users, load averages: 1.29, 1.32, 1.50