mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-11-09, 01:21   #1
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default 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?
fenderbender is offline   Reply With Quote
Old 2010-11-09, 01:58   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2010-11-09, 03:05   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·3·977 Posts
Default

Generally, you want to choose bases between 2 and p-2, inclusive. You won't run into trouble in this range.
CRGreathouse is offline   Reply With Quote
Old 2010-11-09, 05:44   #4
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default

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.
fenderbender is offline   Reply With Quote
Old 2010-11-09, 12:36   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2·3·11·113 Posts
Default

Quote:
Originally Posted by fenderbender View Post
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.
R.D. Silverman is online now   Reply With Quote
Old 2010-11-09, 13:13   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
Mini-Geek is offline   Reply With Quote
Old 2010-11-09, 13:35   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2·3·11·113 Posts
Default

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

Standard number theoretic usage.
R.D. Silverman is online now   Reply With Quote
Old 2010-11-09, 14:41   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
Mini-Geek is offline   Reply With Quote
Old 2010-11-09, 14:48   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2×3×11×113 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
R.D. Silverman is online now   Reply With Quote
Old 2010-11-09, 15:11   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·3·977 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
That doesn't help me. Will you please tell me what it is?
It's an old notation for the gcd.
CRGreathouse is offline   Reply With Quote
Old 2010-11-09, 15:26   #11
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 View Post
It's an old notation for the gcd.
Thanks.
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 12:58.

Tue Jul 14 12:58:56 UTC 2020 up 111 days, 10:32, 1 user, load averages: 1.77, 1.60, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.