Primalty Test

[juergen]

Hi all,

are there any primalty tests which are faster than the fermat test for large numbers.
The primalty test doesn't need to guarantee that a number is prime, it is already enough if I can rule out some numbers, because I proof their primalty later anyway.
I already do trial divisions using a sieve, to rule out most of the composite values, but even the remaining numbers are too many and the fermat test as a second instance for ruling out the composite values is still too slow.
Is there some testing algo which is faster than the fermat check?

faster than x^(n-1) (mod n)

[Cyclamen Persicum]

I have already asked about it:
"Is there kind of "middle" test, much slower than trial division on 3,5,7 but still much faster then Rabin??? I want to embed it before Rabin-test."

But I didn't recieve answer so far.
I believe there is NO.

[juergen]

Originally Posted by Cyclamen Persicum

I have already asked about it:
"Is there kind of "middle" test, much slower than trial division on 3,5,7 but still much faster then Rabin??? I want to embed it before Rabin-test."

But I didn't recieve answer so far.
I believe there is NO.

Hi Cyclamen,

Rabin only works for Mersenne numbers, right?
Oh, I looked at mathworld. It seems also be working for other primes :o)
I guess it is much faster, isn't it?
I will have a look at this one. Thank you for your proposal :o)

Juergen

[ET_]

Originally Posted by juergen

Hi Cyclamen,

Rabin only works for Mersenne numbers, right?
Oh, I looked at mathworld. It seems also be working for other primes :o)
I guess it is much faster, isn't it?
I will have a look at this one. Thank you for your proposal :o)

Juergen

Is Miller-Rabin test faster than PRP? I still did not read that chapter on my "Primes and programming" book...

Luigi

[akruppa]

Miller-Rabin is a kind of PRP (probabilistic primality) test. The problem with Fermat's test ist that there is a class of numbers, called Carmichael numbers, which look prime in Fermat's test to almost all bases even though they are composite.
Miller-Rabin's test, in addition to a^(p-1)==1 (mod p), checks that the square root of 1 seen during the exponentiation is either 1 or -1, which are the only two solutions for x^2=1 (mod p) if p is prime. If p is a not prime, more solutions exist and if one of those is encountered, the number is reported composite. The nice thing is that for Miller-Rabin it can be proved that any composite number is detected as composite with at least 75% probability for any randomly chosen base.

Alex

[Cyclamen Persicum]

I guess it is much faster, isn't it?
No. When I said "Rabin test" I meant it as a synonym to Fermat test,
although Rabin is STRONG pseudoprime test but Fermat itself is weak and pseudoprime affected.

But if we take Square Root from Fermat, namely a^[(N-1)/2]=1 or -1 (mod N),
not always =1, that will be strong test, much easier than Rabin but strong as well, and Carmichael number could not deceive it.

[juergen]

Originally Posted by Cyclamen Persicum

I guess it is much faster, isn't it?
No. When I said "Rabin test" I meant it as a synonym to Fermat test,
although Rabin is STRONG pseudoprime test but Fermat itself is weak and pseudoprime affected.

But if we take Square Root from Fermat, namely a^[(N-1)/2]=1 or -1 (mod N),
not always =1, that will be strong test, much easier than Rabin but strong as well, and Carmichael number could not deceive it.

Hi Cyclamen,

to me the speed of such a test is more relevant than the safety. To proof my kind of numbers are prime I only need to perform a fermat check in combination with another step which takes about half of the time of a fermat check.
So what I am searching for is a test, which is faster than a fermat check. It doesn't need to be totally accurate. But ideally it should identify some of the numbers as composite while consuming less computing time than the fermat test would need to proof that the numbers are composite.
Do you think there is such a test?

Btw. I recognized that the miller rabin test would not be much faster in my case :o(

Kind regards

Juergen

[Cyclamen Persicum]

It doesn't need to be totally accurate.

You need not primality test. You need a "compositeness" test, i.e. kinda
test which never miss if it says "composite". It can say "dont' knoff" but if it says "composite" then a number is 100% composite.

1) if trial division by 3,5,7 says "composite", i.e. N mod 3,5,7 = 0, then a number is indeed 100% composite.
2) if Fermat says "composite", i.e. a^(N-1) =/= 1 (mod N), then a number is
indeed 100% composite
3) is there anything else ???

[juergen]

Originally Posted by Cyclamen Persicum

It doesn't need to be totally accurate.

You need not primality test. You need a "compositeness" test, i.e. kinda
test which never miss if it says "composite". It can say "dont' knoff" but if it says "composite" then a number is 100% composite.

1) if trial division by 3,5,7 says "composite", i.e. N mod 3,5,7 = 0, then a number is indeed 100% composite.
2) if Fermat says "composite", i.e. a^(N-1) =/= 1 (mod N), then a number is
indeed 100% composite
3) is there anything else ???

you are right. Miller Rabin is also such a compositeness test. Okay I guess thats clear, because it is just a variant of the fermat check.
But maybe there is really no faster proof for compositeness than fermat :o(
Because of course the miller-rabin test needs the same amount of time to proof that a number is really composite than the fermat check. The only difference is, that it might be faster in testing, that a number might be prime and it is a method to proof primalty (but I guess for this it need a lot of steps).

My kind of numbers already passed a trial division up to some millions (because i create a sieve after I performed one pass of trial divions).
I also guess that I wouldn't really make the process faster if I increase the number of trial divisions, because after a certain number of trial divisions the time which is needed to do this extra divisions is more than the time which can be saved by doing these trial divisions :o(

BTW. Does anybody know a link or reference to a ressource about primalty and compositeness tests which contains a more or less complete list of tests?

Thank you in advance

Juergen

[Cyclamen Persicum]

Have you written your own PRP prog or you just a user of NewPGEN-PRP.EXE ?

[juergen]

Originally Posted by Cyclamen Persicum

Have you written your own PRP prog or you just a user of NewPGEN-PRP.EXE ?

No I wrote this program myself.
What is a PRP-Program by the way? and what does the program do you mentioned?