mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-04-16, 14:02   #1
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

11×19 Posts
Default Is the website outdated, or me stupid?

First, I'm not a mathematician, so its probably the latter. According to this page on the maths

https://www.mersenne.org/various/math.php
when discussing trial factoring, it says

"Now the only question remaining is how much trial factoring should be done? The answer depends on three variables: the cost of factoring, the chance of finding a factor, and the cost of a primality test. The formula used is:

factoring_cost < chance_of_finding_factor * 2 * primality_test_cost

That is, the time spent factoring must be less than the expected time saved."

Where does the factor of 2 come from? Is it outdated now PRP tests are used, so that a LL test does not have to be performed twice? Or is it still current? I can't seem to get my head around that one - part of me thinks it is right, but part of me thinks it is wrong.

Being the website admin, director, loo cleaner etc for my own company,
https://www.kirkbymicrowave.co.uk/
I know what a nightmare it is trying to keep a website up to date, but I'm not even convinced it is outdated, but suspect it might be.

Dave

Last fiddled with by drkirkby on 2021-04-16 at 14:03
drkirkby is offline   Reply With Quote
Old 2021-04-16, 14:11   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

61×157 Posts
Default

Quote:
Originally Posted by drkirkby View Post
Where does the factor of 2 come from? Is it outdated now PRP tests are used, so that a LL test does not have to be performed twice?
It is outdated. The 2 is from 2 L-L tests. Mersenne.ca and GPU72 have started to factor in the savings, wrt bit level. Since TFing each bit level is double the effort of the bit level below, that translates to do 1 less bit level.
Uncwilly is online now   Reply With Quote
Old 2021-04-16, 14:12   #3
axn
 
axn's Avatar
 
Jun 2003

22·17·73 Posts
Default

Quote:
Originally Posted by drkirkby View Post
Where does the factor of 2 come from? Is it outdated now PRP tests are used, so that a LL test does not have to be performed twice? Or is it still current? I can't seem to get my head around that one - part of me thinks it is right, but part of me thinks it is wrong.
Yes, the factor of 2 is based on the 2 LL tests needed to conclusively prove an exponent is composite. With PRP+CERT, the factor of 2 should become 1.03 (or something similar).
axn is offline   Reply With Quote
Old 2021-04-16, 20:11   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10100000010102 Posts
Default

Quote:
Originally Posted by axn View Post
Yes, the factor of 2 is based on the 2 LL tests needed to conclusively prove an exponent is composite. With PRP+CERT, the factor of 2 should become 1.03 (or something similar).
Really more like for LL, 2(1+e+e2+...] where e=error rate per primality test is ~0.01 for ~p=100M with Jacobi check, double~0.02 without Jacobi check, and e is a strong function of exponent, or of runtime which is roughly 2.1 power of exponent. So 2.02 for LL with Jacobi check, 2.04 without, for 100M exponent, but ~2.5 for 100Mdigit, and ~19. for gigabit, and enormous for gigadigit or higher, as independent runs, due to increasingly large probability of error. (Background to support the LL error rate estimates is available in attachments at https://www.mersenneforum.org/showpo...6&postcount=14)

For PRP with GEC and proof, the numbers are much better; ~1.01, including GEC which is ~0.2% for block size 1000, thanks to the great reduction in verification by the VDF based proof generation and CERT, and the quick error detection and recovery along the way of GEC.
The value depends on the proof power and whether the initial verification succeeds.
For the usual case, proof power 8 or 9, and successful verification the first time, total test and verification effort is <1.01 times a single PRP test without proof.

See also https://www.mersenneforum.org/showpo...45&postcount=4
Attached Files
File Type: pdf prp preferable.pdf (21.8 KB, 8 views)
File Type: pdf proof cost.pdf (21.4 KB, 9 views)
kriesel is online now   Reply With Quote
Old 2021-04-17, 00:07   #5
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

11×19 Posts
Default

Who could update the website?
drkirkby is offline   Reply With Quote
Old 2021-04-17, 23:56   #6
LOBES
 
Mar 2019
USA

5·11 Posts
Default

Quote:
Originally Posted by drkirkby View Post
Who could update the website?
If whomever does update the site, can you please add one more column to the following page:

https://www.mersenne.org/worktypes/

That references the numerical value of the work preference in prime95?
LOBES is offline   Reply With Quote
Old 2021-04-18, 02:05   #7
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

957710 Posts
Default

Quote:
Originally Posted by LOBES View Post
That references the numerical value of the work preference in mprime95?
Fixed that for you.
Uncwilly is online now   Reply With Quote
Old 2021-04-18, 08:58   #8
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

11·19 Posts
Default

Quote:
Originally Posted by LOBES View Post
If whomever does update the site, can you please add one more column to the following page:

https://www.mersenne.org/worktypes/

That references the numerical value of the work preference in prime95?
Do you mean like like the following?

Code:
Use the following values to select a work type:
  0 - Whatever makes the most sense
 150 - First time prime tests
  152 - World record sized numbers to prime test
  151 - Double-check prime tests
  2 - Trial factoring
  4 - P-1 factoring
  153 - 100 million digit numbers to prime test
  160 - First time PRP on Mersenne cofactors
  161 - Double-check PRP on Mersenne cofactors
  5 - ECM for first factors of Mersenne numbers
  8 - ECM on Mersenne cofactors
  6 - ECM on Fermat numbers
  1 - Trial factoring to low limits
Uncwilly says he has fixed the page for you, but if you mean what I think you mean, the page is not fixed in the way you want.
drkirkby is offline   Reply With Quote
Old 2021-04-18, 10:10   #9
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

68616 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
Fixed that for you.
The numerical values are used in the prime.txt configuration file for both mprime and Prime95 ... and to communicate with PrimeNet. But only the mprime user interface confronts one with them directly.

It would indeed be a good idea to add that column to the table on the PrimeNet Assignment Work Types page, the v5.0 PrimeNet Web API 0.97 page can also benefit by being updated ;-)

Jacob
S485122 is offline   Reply With Quote
Old 2021-04-18, 14:17   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

61·157 Posts
Default

Quote:
Originally Posted by drkirkby View Post
]Uncwilly[/URL] says he has fixed the page for you, but if you mean what I think you mean, the page is not fixed in the way you want.
I "fixed" the mprime vs Prime95 reference. With mprime you need to use the numbers, Prime95 not so much. I did not fix the website. Only George, Aaron, and James (a little) have access to make changes to Mersenne.org.
Uncwilly is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Outdated msieve build in Arch AUR Dylan14 Msieve 2 2020-09-27 18:49
Stupid Windows.... petrw1 Hardware 11 2013-01-16 02:45
stupid mersenne game firejuggler Lounge 9 2011-02-20 22:07
Possibly stupid question about PRP. Biggles Prime Sierpinski Project 3 2006-02-07 22:50
Stupid Question fropones Math 2 2003-05-28 00:44

All times are UTC. The time now is 22:15.

Fri May 14 22:15:44 UTC 2021 up 36 days, 16:56, 0 users, load averages: 3.47, 3.45, 3.49

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.