mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Operation Kibibit (https://www.mersenneforum.org/forumdisplay.php?f=97)
-   -   Poly select and test-sieving for RSA232 (https://www.mersenneforum.org/showthread.php?t=24254)

orever 2020-01-06 16:42

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

VBCurtis 2020-01-06 21:34

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.

orever 2020-01-07 00:09

[LEFT] Thanks for the answer.[/LEFT]
The complementary data:[LEFT]
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
[/code]



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[/LEFT]
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,

[url]https://mersenneforum.org/showpost.php?p=531881&postcount=6[/url]

"I bet they'd have better-yet performance with nq of 7776 and admax around 3e11"
[LEFT]
[/LEFT]
Would these be better for a 1024 bits?
[LEFT] [/LEFT]
[LEFT] [/LEFT]

VBCurtis 2020-01-07 01:57

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


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

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