mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-03-22, 21:38   #1
juergen
 
Mar 2004

29 Posts
Question performance of primalty check methods

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.
juergen is offline   Reply With Quote
Old 2004-03-24, 13:09   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
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.
R.D. Silverman is offline   Reply With Quote
Old 2004-03-31, 21:19   #3
juergen
 
Mar 2004

111012 Posts
Default

Quote:
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)
juergen is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
First check and double check llrnet servers. opyrt Prime Sierpinski Project 3 2009-01-02 01:50
Very basic question about Wiedemann methods fivemack Math 0 2008-06-16 10:57
Methods to determine integer multiples dsouza123 Math 6 2006-11-18 16:10
Guidelines for ECM Before Other Methods wblipp GMP-ECM 1 2005-04-19 15:58
Primalty Test juergen Math 23 2004-05-15 21:21

All times are UTC. The time now is 07:54.

Fri Feb 26 07:54:48 UTC 2021 up 85 days, 4:06, 0 users, load averages: 0.99, 1.25, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.