View Single Post
Old 2011-05-24, 18:38   #31
CRGreathouse's Avatar
Aug 2006

2·3·977 Posts

Originally Posted by JohnFullspeed View Post
Two hours to compute the llst (i can give the file)
Two hours?!? It takes PARI 11 seconds on this machine. (Technically that's "just" to 4.26e9 since this computer is running 32-bit gp.)

Originally Posted by JohnFullspeed View Post
and you can factorized 20 digits number in less than one minute.
Sure, as long as it's not a semiprime where both factors are between 2^32 and 10^10. But you can do much better -- using rho and SQUFOF, PARI can factor worst-case numbers of that size in about 200 milliseconds, and ten times faster for typical numbers.

But primality testing is much faster than factoring! PARI only takes about 2 milliseconds to prove that a number is prime; typical composites are extremely easy to detect, taking only 20 *microseconds* by my calculations (I had to test 100,000 to get good timing!).

So trial division works at that size, but we're looking for something really fast here.
CRGreathouse is offline   Reply With Quote