performance of primalty check methods

[juergen]

Hi all,

I would like to know how fast primalty checks on real large numbers are (lets say for numbers of several thousands of digits).
Are the primalty check methods (which proof that the number is a prime like aks) faster or slower than a check which would take 1.5 times a check based on Fermat's little theorem?

In other words, is the fastest method (I guess it is AKS) to check for primalty (checks which proof that a number is prime) faster than

1.5 * the time which is needed to compute 2^(n-1) (mod n)

thanks in advance for any and all opinions :o)

regards
Juergen

BTW: I know that FLT doesn't proof primalty.

[R.D. Silverman]

Originally Posted by juergen

Hi all,

I would like to know how fast primalty checks on real large numbers are (lets say for numbers of several thousands of digits).
Are the primalty check methods (which proof that the number is a prime like aks) faster or slower than a check which would take 1.5 times a check based on Fermat's little theorem?

In other words, is the fastest method (I guess it is AKS) to check for primalty (checks which proof that a number is prime) faster than

1.5 * the time which is needed to compute 2^(n-1) (mod n)

thanks in advance for any and all opinions :o)

regards
Juergen

BTW: I know that FLT doesn't proof primalty.

AKS is not practical. It is far from the fastest method. Both ECPP and
Cyclotomy are much faster. ECPP is polynomial time if certain (as yet
unproved but widely believed) conjectures are true. However, its run
time is O(log^6 N), whereas a simple Fermat test is O(log^3 N).
Cyclotomy runs in time O(log N^{logloglog N}) and is the fastest test
in practice up to (and maybe exceeding) 10000 digits. But it certainly
takes longer than a fixed multiple of a Fermat test.

Pomerance has proved that there exists certificates for all primes p which
take at most O(log^3 p) time to verify. But *finding* the certificate is
more difficult.

Primality proofs in practice take a lot longer than 1.5 * Fermat Test Time.

May I suggest that you read some books on this subject? Try

D. Bressoud Factorization & Primality Testing, Springer-Verlag

for starters.

[juergen]

Originally Posted by Bob Silverman

Pomerance has proved that there exists certificates for all primes p which
take at most O(log^3 p) time to verify. But *finding* the certificate is
more difficult.

Primality proofs in practice take a lot longer than 1.5 * Fermat Test Time.

May I suggest that you read some books on this subject? Try

D. Bressoud Factorization & Primality Testing, Springer-Verlag

for starters.

Thank you very much Bob for this detailed answer!

Do you think that 1.5 times it takes to perform a fermat test is also faster as what is done to proof the primality of a mersenne number?
I guess it is called miller test?!

The reason for my question is, that I found an algorithm to compute large prime numbers and because of their form I can really proof their primality by doing something which takes about 1.5 times a fermat test.
But anyway it is still very slow. I ran it on a Pentium III for one week and still only have a Number which is about 8000 digits long. But I gess I could improve the performance by using some optimizations like using sieves :o)