mersenneforum.org > Math Why no Rabin-Miller Tests ?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2004-06-24, 21:50 #1 Axel Fox     May 2003 6016 Posts 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.
 2004-06-24, 23:17 #2 S80780   Jan 2003 far from M40 1758 Posts 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
 2004-06-25, 01:57 #3 ColdFury     Aug 2002 26×5 Posts Any of the probalistic tests would take just as long as a LL test.
 2004-06-25, 06:30 #4 TTn   2×7×17×29 Posts non rabin Well... not any probabilisitic test.
2004-06-26, 07:52   #5
flava

Feb 2003

2×59 Posts

Quote:
 Originally Posted by TTn Well... not any probabilisitic test.
Could you develop on that, please?

2004-06-26, 09:46   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

29×349 Posts

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

2004-06-27, 09:13   #7
flava

Feb 2003

2×59 Posts

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.

 2004-06-27, 13:09 #8 Fusion_power     Aug 2003 Snicker, AL 23·3·52 Posts 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
2004-06-27, 14:16   #9
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

100111100010012 Posts

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

2004-06-27, 18:11   #10
flava

Feb 2003

11101102 Posts

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"

 2004-06-27, 22:58 #11 Maybeso     Aug 2002 Portland, OR USA 2·137 Posts 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."

 Similar Threads Thread Thread Starter Forum Replies Last Post mathPuzzles Math 14 2017-03-27 04:00 firejuggler Miscellaneous Math 6 2011-12-22 05:57 ATH Math 0 2011-07-30 16:42 fenderbender Miscellaneous Math 22 2010-11-11 01:04 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

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.