Why no Rabin-Miller Tests ?

Axel Fox · 2004-06-24, 21:50

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.

S80780 · 2004-06-24, 23:17

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

ColdFury · 2004-06-25, 01:57

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

2004-06-25, 06:30

Well... not any probabilisitic test.

flava · 2004-06-26, 07:52

Quote:

Originally Posted by TTn

Well... not any probabilisitic test.

Could you develop on that, please?

xilman · 2004-06-26, 09:46

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

flava · 2004-06-27, 09:13

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.

Fusion_power · 2004-06-27, 13:09

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

xilman · 2004-06-27, 14:16

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

flava · 2004-06-27, 18:11

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"

Maybeso · 2004-06-27, 22:58

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

2004-06-24, 21:50	#1
Axel Fox May 2003 2⁵×3 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-25, 06:30	#4
TTn 10011010100010₂ Posts	non rabin Well... not any probabilisitic test.

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

2004-06-24, 23:17	#2
S80780 Jan 2003 far from M40 125₁₀ 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 500₈ Posts	Any of the probalistic tests would take just as long as a LL test.

2004-06-27, 13:09	#8
Fusion_power Aug 2003 Snicker, AL 1677₈ 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, 22:58	#11
Maybeso Aug 2002 Portland, OR USA 112₁₆ 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."