Why no Rabin-Miller Tests ?

[ColdFury]

I of course meant at least or longer than a LL test. We can come up with all sorts of strange tests that don't guarantee primality and take longer than a LL test.

[xilman]

Originally Posted by Maybeso

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."

As did I, of course.

I do not know of any probabalistic tests that are significantly short than a LL test yet give a significantly increased probability that the number is prime. Trial division to a small number of bits without finding a factor does, of course, increase the likelihood of primality but by such an insignificant degree that it's barely worth doing. That's why Prime95 factors to under one in a hundred thousand of the bits (around 65 bits in trial factors compared with around 20 million bits in the Mersenne exponent.)


Paul

[TauCeti]

Originally Posted by xilman

As did I, of course.
I do not know of any probabalistic tests that are significantly short than a LL test yet give a significantly increased probability that the number is prime.
Paul

I remembered vaguely that Rabin-Miller uses several independend iterations (rounds) to determine primality with high probability. So i thought that it could at least be used to improve the time to check _one_ specific exponent (e.g. PRIME, UNVERIFIED) given many machines working in parallel.

But after i looked up Rabin-Miller it seems that even one 'round' of the test is of comparable complexity to LL and that you do need only two rounds at all with numbers of our size.

So even with an unlimited number of deterministic processing units i cannot think of a 'better' test but to let all those units TF in different regions.

I wonder if there are known theoretical complexity limits concerning probability primality tests.