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.

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

Any of the probalistic tests would take just as long as a LL test.

non rabin
 

Well... not any probabilisitic test.

[QUOTE=TTn]Well... not any probabilisitic test.[/QUOTE]

Could you develop on that, please?

[QUOTE=flava]Could you develop on that, please?[/QUOTE]
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

[QUOTE=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[/QUOTE]

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.

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

[QUOTE=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.[/QUOTE]
My point exactly.

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

Paul

[QUOTE=xilman]My point exactly.

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

Paul[/QUOTE]

Now I get it, thanks. I was thinking "faster than LL" rather that "faster OR slower than LL" :redface:

Yes, when taken in context, ColdFury's statement should be interpreted as:
"Any of the probalistic tests would take [B]at least[/B] 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 [B]exactly[/B] as long as a LL test."