Time to test arbitrary number

[JuanTutors]

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?

[VBCurtis]

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

[Jens K Andersen]

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.

[R.D. Silverman]

Originally Posted by Jens K Andersen

<snip>

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)