20070515, 03:07  #1 
Mar 2004
3·167 Posts 
Time to test arbitrary number
Define an arbitrary number N to be a number I might type if I were to hit the number keys with the palm of my hand until I got tired of it. In other words, it's a number of no special form.
Verifying compositeness is usually (always?) faster than verifying primality. You can run a seive, or do some other test. Define T(L) to be the amount of time it takes to verify that an arbitrary number of length L (in base 10, say) that a priori may not be prime is in fact prime. What is the maximum that L has to be for T(L) to be equal to one day? 
20070515, 06:00  #2 
"Curtis"
Feb 2005
Riverside, CA
2·3·751 Posts 
I think ECPP is the most general primality proving method, so if you had to be *sure* something was or was not prime in 1 day, the solution would be whatever L requires one day to test with ECPP.
This does not allow time for trial factoring, but spending that time would reduce the time allowed for ECPP, thus lowering the possible size of number to test. curtis 
20070516, 11:23  #3 
Feb 2006
Denmark
2×5×23 Posts 
Limited experimentation with Marcel Martin's ECPP implementation Primo has hinted that the typical time to certify an Ldigit prime is roughly proportional to L^4.7. A 1 GHz Athlon cpu may typically be able to certify a number around 18002000 digits in one GHz day. Note however that the time varies considerably and the worst case time is unknown. There may be some numbers that take far longer or cannot be certified with Primo. FastECPP as Implemented by Morain; Franke, Kleinjung and Wirth is not publicly available. Variants of it made the current top14 ECPP proofs. It appears faster than Primo at record sizes. I don't know how much it can typically prove in a day on a single cpu. ECPP has not been proved to have polynomial worst case time complexity. It is proved for AKS but that is far slower than ECPP in practice.

20070516, 12:13  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:
about the density of nearprimes (integers of the form kp where k is tiny) in short intervals are correct. BTW, I can not speak for the latest ECPP implementations, but my prior expierience is that APRCL is faster than ECPP up to several thousand digits. (but it is most definitely not polynomial time) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Can I run Prime95 on two different computers same time to test one same exponent?  king  Information & Answers  8  20180211 17:38 
Arbitrary Precision by Google  a1call  Miscellaneous Math  0  20171203 17:39 
CPU time for 100M digit prime test  biggerben  Software  7  20141024 05:47 
Isn't it time for a new Mersennen prime number? ;)  joblack  Lounge  2  20100515 04:44 
Question about ArbitraryPrecision Calculator?  Unregistered  Software  8  20050129 00:23 