mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

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

3·167 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
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·3·751 Posts
Default

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
VBCurtis is offline   Reply With Quote
Old 2007-05-16, 11:23   #3
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

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
Default

Quote:
Originally Posted by Jens K Andersen View Post
<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)
R.D. Silverman is offline   Reply With Quote
Reply

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.