20040624, 21:50  #1 
May 2003
2^{5}×3 Posts 
Why no RabinMiller Tests ?
I recently studied some stuff relating to RabinMiller 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 RabinMiller test takes longer than the LL Test 2) Mersenne numbers are strong pseudoprimes for most bases (although that it shouldn't be for at least 3/4 of the bases) Greetings, Axel Fox. 
20040624, 23:17  #2 
Jan 2003
far from M40
125_{10} Posts 
It is indeed the 1) argument.
For a given exponent, one run of MillerRabin on a randomly chosen base would take about the same time as a run of LucasLehmer. If you compare MillerRabin and LucasLehmer for Mersennes, you see that, roughly, the substraction of 2 in LucasLehmer is substituted by a modular multiplication in MillerRabin. So, for about the same cost, MillerRabin gives a maybe prime/definitely composite answer whereas LucasLehmer gives a definitely prime/definitely composite answer. The only advantage of MillerRabin is the information, that the tested base is (not) a factor of the Mersennenumber. Anyhow, this information is easier gained by TrialFactoring, as the modular arithmetic used there is "cheaper". Benjamin 
20040625, 01:57  #3 
Aug 2002
500_{8} Posts 
Any of the probalistic tests would take just as long as a LL test.

20040625, 06:30  #4 
10011010100010_{2} Posts 
non rabin
Well... not any probabilisitic test.

20040626, 07:52  #5  
Feb 2003
2·59 Posts 
Quote:


20040626, 09:46  #6  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2^{3}×5×283 Posts 
Quote:
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 

20040627, 09:13  #7  
Feb 2003
1110110_{2} Posts 
Quote:


20040627, 13:09  #8 
Aug 2003
Snicker, AL
1677_{8} 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^p1 number have a factor that lies between Sqrt(2^p1) and Cbrt(2^p1) 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 
20040627, 14:16  #9  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
26070_{8} Posts 
Quote:
It was claimed, incorrectly, by ColdFury that "Any of the probalistic tests would take just as long as a LL test". I gave a counterexample of a test that would take much longer than a LL test, thereby making TTn's "Well... not any probabilisitic test" claim explicit. Paul 

20040627, 18:11  #10  
Feb 2003
2·59 Posts 
Quote:


20040627, 22:58  #11 
Aug 2002
Portland, OR USA
112_{16} 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." 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Probabilistic primality tests faster than Miller Rabin?  mathPuzzles  Math  14  20170327 04:00 
MillerRabin test questions  firejuggler  Miscellaneous Math  6  20111222 05:57 
Number of RabinMiller NonWitnesses  ATH  Math  0  20110730 16:42 
MillerRabin Strong Probable Prime Test (SPRP)  fenderbender  Miscellaneous Math  22  20101111 01:04 
MonierRabin Theorem  flouran  Math  2  20090501 21:44 