mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Kibibit

Reply
 
Thread Tools
Old 2020-01-06, 16:42   #23
orever
 
Oct 2019

2 Posts
Default

Hello, first.
This text was written with the help of google translator.

I am entering this world of factoring, 6 months ago.

I have problems factoring a number of 1024 bits, I know it is too large.

So about polyselect, it ran for 99 days.

tasks.polyselect.P = 10000000
tasks.polyselect.admax = 1e8
tasks.polyselect.adrange = 250
tasks.polyselect.degree = 6
tasks.polyselect.incr = 60
tasks.polyselect.nq = 1296
tasks.polyselect.nrkeep = 100
tasks.polyselect.threads = 2


n: 1024 bits
skew: 3280536.395
# MurphyE (Bf = 1.43e + 09, Bg = 7.00e + 08, area = 3.07e + 18) = 4.29e-16

Is this result good?

What about sieve,

tasks.sieve.mfb0 = 70
tasks.sieve.mfb1 = 105
tasks.sieve.ncurves0 = 30
tasks.sieve.ncurves1 = 30
tasks.sieve.qrange = 1000
tasks.sieve.las.threads = 4
tasks.I = 16

Hundreds of found 0.
Info: Lattice Sieving: Found 0 relations in '', total is now 102/3794906671
orever is offline   Reply With Quote
Old 2020-01-06, 21:34   #24
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

424310 Posts
Default

The MurphyE score depends on other parameters that you didn't list. You also didn't list the polynomial, so I can't evaluate its quality myself.

You didn't list the large-prime bound parameters, nor lim0 and lim1, so I can't tell you how good or bad your param choices are.

I'd change I=16 to I=17, for a start.

If you know it is too large, why are you trying to factor it? Your machine isn't capable of finishing the job.

EDIT: Sorry, I had in mind a 768-bit number, not 1024-bit.
When the CADO group solved RSA768, they spent about 20 core-years on poly select. You spent 1 core-year (100 days * 4 cores, as a guess). So, you're about 5% of the way to "enough" for a number 1/1000th the difficulty of the one you're trying to factor.

So, a mere 500000 more core-days of poly select should be about right. Then, the sieving might take 20-30x that long, depending on how good your parameter choice is.

Your parameters are in the ballpark of decent for a 768-bit number, though.

Last fiddled with by VBCurtis on 2020-01-06 at 21:58
VBCurtis is offline   Reply With Quote
Old 2020-01-07, 00:09   #25
orever
 
Oct 2019

28 Posts
Default

Thanks for the answer.
The complementary data:

POLY:
Code:
skew: 3280536.395  
 c0: -2963521726450804168545574989181604944974055470262264097100  
 c1: -8152690578728840862728149245184473131571416030581953  
 c2: 4530419292332128770249146516543999988943765890  
 c3: 87634441208849856388603554546291847879  
 c4: -844120661985043880048339652132070  
 c5: 13409199100611061897507722  
 c6: -59711977080  
 Y0: -108073099124290591101496444923166525774281367655542  
 Y1: 2355770915946536318263  
 # MurphyE (Bf=1.43e+09,Bg=7.00e+08,area=3.07e+18) = 4.29e-16  
 # f(x) =  -59711977080*x^6+13409199100611061897507722*x^5-844120661985043880048339652132070*x^4+87634441208849856388603554546291847879*x^3+4530419292332128770249146516543999988943765890*x^2-8152690578728840862728149245184473131571416030581953*x-2963521726450804168545574989181604944974055470262264097100  
 # g(x) = 2355770915946536318263*x-108073099124290591101496444923166525774281367655542


Param:

lim0 = 700000000
lim1 = 1430000000
lpb0 = 35
lpb1 = 36
maxfailed = 5000
name = c310
tasks.I = 16
tasks.maxtimedout = 3000
tasks.qmin = 1073741823
tasks.threads = 2
tasks.wutimeout = 24000
tasks.filter.maxlevel = 40
tasks.filter.target_density = 170.0
tasks.filter.purge.keep = 160
tasks.linalg.m = 64
tasks.linalg.n = 64
tasks.linalg.bwc.interleaving = 0
tasks.linalg.bwc.interval = 1000
tasks.linalg.characters.nchar = 50
tasks.polyselect.P = 10000000
tasks.polyselect.admax = 1e6
tasks.polyselect.adrange = 1000
tasks.polyselect.degree = 6
tasks.polyselect.incr = 60
tasks.polyselect.nq = 1296
tasks.polyselect.nrkeep = 100
tasks.polyselect.threads = 2
tasks.sieve.mfb0 = 70
tasks.sieve.mfb1 = 105
tasks.sieve.ncurves0 = 30
tasks.sieve.ncurves1 = 30
tasks.sieve.qrange = 1000
tasks.sieve.las.threads = 4
I read on params.c240 in git:

tasks.polyselect.P = 20000000
tasks.polyselect.admax = 2e12
tasks.polyselect.adrange = 10000000
tasks.polyselect.incr = 110880
tasks.polyselect.nq = 1296 # this is 6^4
tasks.polyselect.nrkeep = 100
tasks.wutimeout = 7200
tasks.polyselect.sopteffort = 20
tasks.polyselect.ropteffort = 10

Read and your post,

https://mersenneforum.org/showpost.p...81&postcount=6

"I bet they'd have better-yet performance with nq of 7776 and admax around 3e11"

Would these be better for a 1024 bits?

Last fiddled with by VBCurtis on 2020-01-07 at 01:43 Reason: added code tags
orever is offline   Reply With Quote
Old 2020-01-07, 01:57   #26
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,243 Posts
Default

You're missing the point entirely- you have copied / used parameters from either RSA768 (a 232-digit number) or RSA-240. These are, you know, SIXTY or more digits smaller than the number you wish to factor.

If you tried to use good parameters from a 180-digit job to factor a 240-digit job, they would fail miserably. So will yours, for the same reasons.

1. You're not getting any relations because the siever is too small. You need I=18 for a kilobit number. One instance of this siever requires 120GB or more of memory.

2. You don't know what you are doing, so you don't know how to scale any of these settings for this job. Since this job is impossible for you to complete, this doesn't matter a whole lot; but if you happen to be pals with Ben Delo and share his level of hardware resources, you would factor a 140 digit number, then 160, then 180, then 200, then 220 and see how the settings change and memory needs change and time requirements change. Then you and Ben would realize 1024-bit GNFS is not a good idea, but maybe 250-digit GNFS is possible (it is).

3. There are discussions scattered around about trying to factor RSA-1024. You should find these papers or forum posts for ideas about how big a job this is, and what settings might be reasonable. Things like 4 large primes on one side & 3 on the other, 42-bit large primes (or 43, or 44- how much disk space do you have?). Once you have 20 or 50 TB of disk prepared for this task, then you can decide how to write a grant proposal to get access to a cluster with, say, 512GB of memory per node to attempt the postprocessing. That matrix might have a billion rows and a billion columns.

In closing, your settings *might* factor a 230-digit number in some reasonable number of decades, but they won't factor a kilobit number before you die.

EDIT: I pasted your poly into cownoise to see what its score was. Results: optimal skew 8832525.55458 score 7.74032539e-22

Last fiddled with by VBCurtis on 2020-01-07 at 02:16
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
YAFU Poly Select Deadline amphoria YAFU 22 2016-09-17 09:47
msieve poly select: choosing Stage1norm VBCurtis Msieve 0 2016-04-11 21:33
Starting NFS skipping poly select jux YAFU 5 2016-01-02 01:01
Poly Search vs Sieving times EdH Factoring 10 2013-10-14 20:00
Test Sieving Questions nstaab1 Lounge 15 2013-03-06 13:48

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

Thu Aug 13 19:39:38 UTC 2020 up 16:15, 1 user, load averages: 1.50, 2.02, 2.09

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.