Miller-Rabin Strong Probable Prime Test (SPRP)

fenderbender · 2010-11-09, 01:21

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?

Mini-Geek · 2010-11-09, 01:58

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.

CRGreathouse · 2010-11-09, 03:05

Generally, you want to choose bases between 2 and p-2, inclusive. You won't run into trouble in this range.

fenderbender · 2010-11-09, 05:44

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.

R.D. Silverman · 2010-11-09, 12:36

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.

Mini-Geek · 2010-11-09, 13:13

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?

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

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.

Mini-Geek · 2010-11-09, 14:41

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?

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

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.

CRGreathouse · 2010-11-09, 15:11

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.

Mini-Geek · 2010-11-09, 15:26

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.

2010-11-09, 01:21	#1
fenderbender Jul 2007 17 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Probabilistic primality tests faster than Miller Rabin?	mathPuzzles	Math	14	2017-03-27 04:00
Hi, how can I test my probable prime number?	mohdosa	Information & Answers	22	2014-10-10 11:34
Miller-Rabin test questions	firejuggler	Miscellaneous Math	6	2011-12-22 05:57
Number of Rabin-Miller Non-Witnesses	ATH	Math	0	2011-07-30 16:42
Why no Rabin-Miller Tests ?	Axel Fox	Math	13	2004-06-28 16:07

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 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 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.