Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2007-05-15, 03:07   #1
JuanTutors's Avatar
Mar 2004

50910 Posts
Default 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?
JuanTutors is offline   Reply With Quote
Old 2007-05-15, 06:00   #2
VBCurtis's Avatar
Feb 2005
Riverside, CA

478710 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.

VBCurtis is offline   Reply With Quote
Old 2007-05-16, 11:23   #3
Jens K Andersen
Jens K Andersen's Avatar
Feb 2006

E616 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.
Jens K Andersen is offline   Reply With Quote
Old 2007-05-16, 12:13   #4
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by Jens K Andersen View Post

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)
R.D. Silverman is offline   Reply With Quote

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 2018-02-11 17:38
Arbitrary Precision by Google a1call Miscellaneous Math 0 2017-12-03 17:39
CPU time for 100M digit prime test biggerben Software 7 2014-10-24 05:47
Isn't it time for a new Mersennen prime number? ;) joblack Lounge 2 2010-05-15 04:44
Question about Arbitrary-Precision Calculator? Unregistered Software 8 2005-01-29 00:23

All times are UTC. The time now is 10:04.

Mon May 17 10:04:19 UTC 2021 up 39 days, 4:45, 0 users, load averages: 1.26, 1.37, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.