mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-12-10, 07:01   #1
2147483647
 
Dec 2016

2·32 Posts
Default What should the "q" value increase to for GNFS/SNFS computations?

Yesterday I started a large SNFS and I'm just wondering how long it's going to take.

I just did a C100 with SNFS and the sieving range was 510k to 590k.

What should the range look like for larger numbers, in increments of 10 digits? Will the range be larger for GNFS?
2147483647 is offline   Reply With Quote
Old 2016-12-10, 07:50   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

221608 Posts
Default

The script will take care of everything. q values should not concern you; they will be variable for different runs and will depend on the project's complexity. Different sievers will be chosen by the script, too; their rate of sieving might seem sometimes logical to the untrained eye and sometimes unexpectedly slower (on the next project) - but you should trust the script.

Here are the fairly good rules of thumb:
- for SNFS, with every 9 additional digits of SNFS difficulty, the overall runtime will double (or, which is the same, runtime will be 10x for every 30 digits)
- for GNFS, with every 5 additional digits of length(N), the overall runtime will double

Remember just these two and you will be in good shape.

Examples: a 120-digit SNFS complexity project might take 1 core-hour on your computer. Then you can assume that a 150-digit SNFS complexity project will take 10 hours, a 180-digit SNFS complexity project will take 100 hours, and a 210-digit SNFS complexity project will take 1000 hours (~40 core-days). Ok?

You can estimate how hard a GNFS project will be by taking length of the input number N, and converting to (N-30)*1.8 = similarly hard SNFS complexity. For example, a 130-digit GNFS is approximately as hard as a 180-SNFS-digit difficulty SNFS (from the estimate above, ~100 core-hours).
Batalov is offline   Reply With Quote
Old 2016-12-10, 08:42   #3
2147483647
 
Dec 2016

1810 Posts
Default

Quote:
Originally Posted by Batalov View Post
Here are the fairly good rules of thumb:
- for SNFS, with every 9 additional digits of SNFS difficulty, the overall runtime will double (or, which is the same, runtime will be 10x for every 30 digits)
- for GNFS, with every 5 additional digits of length(N), the overall runtime will double

Remember just these two and you will be in good shape.
Interesting, thanks. I suppose these will actually over-estimate the time for large enough numbers since the complexity of NFS is sub-exponential, but if it's a good approximation then that's fine.

I did a C165 SNFS in ~5h30m yesterday and the one I'm currently doing is a C201, so ~16 times longer = about 3 days 16 hours. That's quite a lot less than I was expecting actually.
2147483647 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Stockfish game: "Move 8 poll", not "move 3.14159 discussion" MooMoo2 Other Chess Games 5 2016-10-22 01:55
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 11:39.

Tue Mar 2 11:39:48 UTC 2021 up 89 days, 7:51, 0 users, load averages: 2.24, 2.03, 1.89

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.