20040322, 21:38  #1 
Mar 2004
29 Posts 
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^(n1) (mod n) thanks in advance for any and all opinions :o) regards Juergen BTW: I know that FLT doesn't proof primalty. 
20040324, 13:09  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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, SpringerVerlag for starters. 

20040331, 21:19  #3  
Mar 2004
11101_{2} Posts 
Quote:
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) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
First check and double check llrnet servers.  opyrt  Prime Sierpinski Project  3  20090102 01:50 
Very basic question about Wiedemann methods  fivemack  Math  0  20080616 10:57 
Methods to determine integer multiples  dsouza123  Math  6  20061118 16:10 
Guidelines for ECM Before Other Methods  wblipp  GMPECM  1  20050419 15:58 
Primalty Test  juergen  Math  23  20040515 21:21 