mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-06-24, 21:50   #1
Axel Fox
 
Axel Fox's Avatar
 
May 2003

6016 Posts
Default Why no Rabin-Miller Tests ?

I recently studied some stuff relating to Rabin-Miller tests and I know that they don't prove a number being prime, but they do prove a number being composite.

So why don't we (before running the LL Test) run a few of these tests ?

It seems that if the number is composite, there's only a 1/4 chance that the number passes even one of these tests, so wouldn't it be quicker to run a few of these and statistically eliminate a whole bunch of numbers before starting the LL test on them ?

Possible answers I thought of myself, but that I am not sure of, so I would like someone to confer one of these or give another reason :
1) the Rabin-Miller test takes longer than the LL Test
2) Mersenne numbers are strong pseudo-primes for most bases (although that it shouldn't be for at least 3/4 of the bases)

Greetings,
Axel Fox.
Axel Fox is offline   Reply With Quote
Old 2004-06-24, 23:17   #2
S80780
 
Jan 2003
far from M40

1758 Posts
Default

It is indeed the 1) argument.
For a given exponent, one run of Miller-Rabin on a randomly chosen base would take about the same time as a run of Lucas-Lehmer.
If you compare Miller-Rabin and Lucas-Lehmer for Mersennes, you see that, roughly, the substraction of 2 in Lucas-Lehmer is substituted by a modular multiplication in Miller-Rabin.
So, for about the same cost, Miller-Rabin gives a maybe prime/definitely composite answer whereas Lucas-Lehmer gives a definitely prime/definitely composite answer.
The only advantage of Miller-Rabin is the information, that the tested base is (not) a factor of the Mersennenumber. Anyhow, this information is easier gained by Trial-Factoring, as the modular arithmetic used there is "cheaper".

Benjamin
S80780 is offline   Reply With Quote
Old 2004-06-25, 01:57   #3
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26×5 Posts
Default

Any of the probalistic tests would take just as long as a LL test.
ColdFury is offline   Reply With Quote
Old 2004-06-25, 06:30   #4
TTn
 

2×7×17×29 Posts
Default non rabin

Well... not any probabilisitic test.
  Reply With Quote
Old 2004-06-26, 07:52   #5
flava
 
flava's Avatar
 
Feb 2003

2×59 Posts
Default

Quote:
Originally Posted by TTn
Well... not any probabilisitic test.
Could you develop on that, please?
flava is offline   Reply With Quote
Old 2004-06-26, 09:46   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

29×349 Posts
Default

Quote:
Originally Posted by flava
Could you develop on that, please?
Trial division by all primes up to the cube root of the number.

If no factors are found, you can say that the number is either prime or has precisely two prime factors. In either case, the additional information gained by performing this test greatly increases the likelihood that the number is prime compared with the likelihood before.

It's a silly test, obviously, but it meets the criteria so far stated.


Paul
xilman is offline   Reply With Quote
Old 2004-06-27, 09:13   #7
flava
 
flava's Avatar
 
Feb 2003

2×59 Posts
Default

Quote:
Originally Posted by xilman
Trial division by all primes up to the cube root of the number.

If no factors are found, you can say that the number is either prime or has precisely two prime factors. In either case, the additional information gained by performing this test greatly increases the likelihood that the number is prime compared with the likelihood before.

It's a silly test, obviously, but it meets the criteria so far stated.


Paul
I see what you mean, but, unless I am missing something, it looks slower (not even comparable) than a LL test to me. You would have to make trial divisions up to p/3 bits for 2^p-1.
flava is offline   Reply With Quote
Old 2004-06-27, 13:09   #8
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

23·3·52 Posts
Default

What is the probability that a Mp number will have a factor that lies between the cube root and the square root?

In other words, could a 2^p-1 number have a factor that lies between Sqrt(2^p-1) and Cbrt(2^p-1) and if so, what is the probability of such a factor existing? Just a quick look at this indicates that the probability is very low as compared with a small 2kp+1 factor. My instinct says that the probability should form a hyperbola ranging from K=0 to k=max. Or am I way off base?

Fusion
Fusion_power is offline   Reply With Quote
Old 2004-06-27, 14:16   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

100111100010012 Posts
Default

Quote:
Originally Posted by flava
I see what you mean, but, unless I am missing something, it looks slower (not even comparable) than a LL test to me. You would have to make trial divisions up to p/3 bits for 2^p-1.
My point exactly.

It was claimed, incorrectly, by ColdFury that "Any of the probalistic tests would take just as long as a LL test". I gave a counter-example of a test that would take much longer than a LL test, thereby making TTn's "Well... not any probabilisitic test" claim explicit.

Paul
xilman is offline   Reply With Quote
Old 2004-06-27, 18:11   #10
flava
 
flava's Avatar
 
Feb 2003

11101102 Posts
Default

Quote:
Originally Posted by xilman
My point exactly.

It was claimed, incorrectly, by ColdFury that "Any of the probalistic tests would take just as long as a LL test". I gave a counter-example of a test that would take much longer than a LL test, thereby making TTn's "Well... not any probabilisitic test" claim explicit.

Paul
Now I get it, thanks. I was thinking "faster than LL" rather that "faster OR slower than LL"
flava is offline   Reply With Quote
Old 2004-06-27, 22:58   #11
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

Yes, when taken in context, ColdFury's statement should be interpreted as:
"Any of the probalistic tests would take at least as long as a LL test."

To point out the ambiguous phrasing, I think TTn intentionally interpreted it as:
"Any of the probalistic tests would take exactly as long as a LL test."
Maybeso 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
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
Miller-Rabin Strong Probable Prime Test (SPRP) fenderbender Miscellaneous Math 22 2010-11-11 01:04
Monier-Rabin Theorem flouran Math 2 2009-05-01 21:44

All times are UTC. The time now is 16:49.

Sat Oct 24 16:49:48 UTC 2020 up 44 days, 14 hrs, 0 users, load averages: 1.78, 1.87, 1.78

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.