mersenneforum.org > Math Time to test arbitrary number
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-15, 03:07 #1 JuanTutors     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?
 2007-05-15, 06:00 #2 VBCurtis     "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
 2007-05-16, 11:23 #3 Jens K Andersen     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 L-digit prime is roughly proportional to L^4.7. A 1 GHz Athlon cpu may typically be able to certify a number around 1800-2000 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 top-14 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.
2007-05-16, 12:13   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Jens K Andersen ECPP has not been proved to have polynomial worst case time complexity.
Correct. However, it is know to run in polynomial time if certain conjectures
about the density of near-primes (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 APR-CL is faster than ECPP up to several thousand digits.
(but it is most definitely not polynomial time)

 Similar Threads Thread Thread Starter Forum Replies Last Post king Information & Answers 8 2018-02-11 17:38 a1call Miscellaneous Math 0 2017-12-03 17:39 biggerben Software 7 2014-10-24 05:47 joblack Lounge 2 2010-05-15 04:44 Unregistered Software 8 2005-01-29 00:23

All times are UTC. The time now is 18:56.

Sat Dec 5 18:56:35 UTC 2020 up 2 days, 15:07, 0 users, load averages: 2.06, 2.47, 2.67