Independent factorization of large numbers

[LaurV]

Originally Posted by frmky

I don't understand all of this interest in the number. Lessiv has clearly stated that they do not wish to reveal the number. They did the work to factor it themselves. They owe us no explanation, and we as a community should respect their wishes.

+1.
Well said. I can imagine a hundred reasons why the number be not said in public, and yet be nothing illegal. To avoid any arguments, the OP could just generate a rsa(154) with yafu, which has a function to do exactly that, and post it here, letting the others to scratch their head. However he was honest and said he can't disclose it.

End of story. Let it go.

[Lessiv]

Good afternoon dear experts!
Need help again.
Asked me to factorize another number, the search ended and the processing began and at that moment I turned off the computer (computer overheating). If I run the "Factmsieve.py example" command, data processing no longer happens.
What kind of team I need to write to continue the processing process "spairs.save.gz"?

[VBCurtis]

If you barely started the job when you turned off the computer, best to just start the job over anew. Erase the work-in-progress files and fire up factmsieve.

[Lessiv]

Originally Posted by VBCurtis

If you barely started the job when you turned off the computer, best to just start the job over anew. Erase the work-in-progress files and fire up factmsieve.

The final stage has already begun, after a week of searching, and 100% of the numbers have already been processed. And the process began:
Sun Apr 24 09:07:16 2022 commencing linear algebra
Sun Apr 24 09:07:16 2022 read 4098748 cycles
Sun Apr 24 09:07:20 2022 cycles contain 11569154 unique relations
Sun Apr 24 09:07:55 2022 read 11569154 relations
Sun Apr 24 09:08:05 2022 using 20 quadratic characters above 4294917295
Sun Apr 24 09:08:45 2022 building initial matrix
Sun Apr 24 09:10:03 2022 memory use: 1590.2 MB
Sun Apr 24 09:10:06 2022 read 4098748 cycles
Sun Apr 24 09:10:07 2022 matrix is ​​4098569 x 4098748 (1241.2 MB) with weight 390701857 (95.32/col)
Sun Apr 24 09:10:07 2022 sparse part has weight 276196077 (67.39/col)
Sun Apr 24 09:10:25 2022 filtering completed in 2 passes
Sun Apr 24 09:10:26 2022 matrix is ​​4097843 x 4098022 (1241.2 MB) with weight 390677271 (95.33/col)
Sun Apr 24 09:10:26 2022 sparse part has weight 276190614 (67.40/col)
Sun Apr 24 09:10:32 2022 matrix starts at (0, 0)
Sun Apr 24 09:10:33 2022 matrix is ​​4097843 x 4098022 (1241.2 MB) with weight 390677271 (95.33/col)
Sun Apr 24 09:10:33 2022 sparse part has weight 276190614 (67.40/col)
Sun Apr 24 09:10:33 2022 saving the first 48 matrix rows for later
Sun Apr 24 09:10:33 2022 matrix includes 64 packed rows
Sun Apr 24 09:10:34 2022 matrix is ​​4097795 x 4098022 (1199.3 MB) with weight 311380058 (75.98/col)
Sun Apr 24 09:10:34 2022 sparse part has weight 273415510 (66.72/col)
Sun Apr 24 09:10:34 2022 using block size 8192 and superblock size 1572864 for processor cache size 16384 kB
Sun Apr 24 09:10:45 2022 commencing Lanczos iteration (16 threads)
Sun Apr 24 09:10:45 2022 memory use: 963.3 MB
Sun Apr 24 09:10:49 2022 linear algebra at 0.0%, ETA 3h 0m

And at that moment my computer turned off.

[Lessiv]

When re-running "factmsieve.py example"
I am getting the following message:
See attached screenshot.

[chris2be8]

It looks as if you had just finished sieving and started LA (linear algebra) when the system overheated. So you are most of the way there.

I suggest:

1: Back up everything in the working folder, preferably to another computer. Or to another folder if you can't do that.

2: Check why the computer overheated. Try blowing dust and fluff out of it. Check for stuck or faulty fans, fix or replace them if so. And make sure it was heat, not running out of memory that caused the crash.

3: Try to restart the job. You may need to run msieve outside the script, passing it -ncr -nc3 as extra parameters. Run msieve -h to get a list of parameters msieve will accept. And possibly reducing the number of threads to stop the computer getting so hot.

4: If you are stuck post output from dir in the working folder.

I don't use factmsieve.py myself, or Windows (I use factMsieve.pl on Linux) so I can't be more specific.

[Lessiv]

Help me choose the right commands for linear algebra:


Msieve v. 1.53 (SVN 1005)

usage: msieve.exe [options] [one_number]

numbers starting with '0' are treated as octal,
numbers starting with '0x' are treated as hexadecimal

options:
-s <name> save intermediate results to <name>
instead of the default msieve.dat
-l <name> append log information to <name>
instead of the default msieve.log
-i <name> read one or more integers to factor from
<name> (default worktodo.ini) instead of
from the command line
-m manual mode: enter numbers via standard input
-q quiet: do not generate any log information,
only print any factors found
-d <min> deadline: if still sieving after <min>
minutes, shut down gracefully (default off)
-r <num> stop sieving after finding <num> relations
-p run at idle priority
-v verbose: write log information to screen
as well as to logfile
-z you are Paul Zimmermann
-t <num> use at most <num> threads

elliptic curve options:
-e perform 'deep' ECM, seek factors > 15 digits

quadratic sieve options:
-c client: only perform sieving

number field sieve options:

[nfs_phase] "arguments"

where the first part is one or more of:
-n use the number field sieve (80+ digits only;
performs all NFS tasks in order)
-nf <name> read from / write to NFS factor base file
<name> instead of the default msieve.fb
-np perform only NFS polynomial selection
-np1 perform stage 1 of NFS polynomial selection
-nps perform NFS polynomial size optimization
-npr perform NFS polynomial root optimization
-ns perform only NFS sieving
-nc perform only NFS combining (all phases)
-nc1 perform only NFS filtering
-nc2 perform only NFS linear algebra
-ncr perform only NFS linear algebra, restarting
from a previous checkpoint
-nc3 perform only NFS square root

the arguments are a space-delimited list of:
polynomial selection options:
polydegree=X select polynomials with degree X
min_coeff=X minimum leading coefficient to search
in stage 1
max_coeff=X maximum leading coefficient to search
in stage 1
stage1_norm=X the maximum norm value for stage 1
stage2_norm=X the maximum norm value for stage 2
min_evalue=X the minimum score of saved polyomials
poly_deadline=X stop searching after X seconds (0 means
search forever)
X,Y same as 'min_coeff=X max_coeff=Y'
line sieving options:
X,Y handle sieve lines X to Y inclusive
filtering options:
filter_mem_mb=X try to limit filtering memory use to
X megabytes
filter_maxrels=X limit the filtering to using the first
X relations in the data file
filter_lpbound=X have filtering start by only looking
at ideals of size X or larger
target_density=X attempt to produce a matrix with X
entries per column
X,Y same as 'filter_lpbound=X filter_maxrels=Y'
linear algebra options:
skip_matbuild=1 start the linear algebra but skip building
the matrix (assumes it is built already)
la_block=X use a block size of X (512<=X<=65536)
la_superblock=X use a superblock size of X
cado_filter=1 assume filtering used the CADO-NFS suite
square root options:
dep_first=X start with dependency X, 1<=X<=64
dep_last=Y end with dependency Y, 1<=Y<=64
X,Y same as 'dep_first=X dep_last=Y'

[Lessiv]

The question is: how to properly unpack the "spairs.save.gz" archive so that later you can run "msieve" with the necessary parameters? And how is the "example.dat" file created?

[frmky]

Make sure you have everything backed up elsewhere first.

spairs.save.gz should be just a gzipped copy of example.dat. You can just leave it compressed and copy it to msieve.dat.gz and it should work. Since you are replacing the dat file, I would restart with filtering. With msieve, msieve.dat.gz, example.ini, and example.fb in the same directory,

msieve -i example.ini -nf example.fb -nc1 -nc2 -nc3 -t 16 -v

[Lessiv]

Originally Posted by frmky

Make sure you have everything backed up elsewhere first.

spairs.save.gz should be just a gzipped copy of example.dat. You can just leave it compressed and copy it to msieve.dat.gz and it should work. Since you are replacing the dat file, I would restart with filtering. With msieve, msieve.dat.gz, example.ini, and example.fb in the same directory,

msieve -i example.ini -nf example.fb -nc1 -nc2 -nc3 -t 16 -v

Many thanks!
Everything worked out.

[orever]

On this github there is code that says it factors in a matter of hours. A number of 512-bit RSA keys.

https://github.com/eniac/faas

And so, anyone can factor a 512 very quickly.

If you use this number for business, you better rethink.
And he didn't even need to prove it was a vulnerability.

"Since 2015, NIST has recommended a minimum of 2048-bit keys for RSA,[14] an update to the widely accepted recommendation of a minimum of 1024 bits since at least 2002.[15]"

So if they changed it to a number of 1024, a number of 2048 is better.

https://en.wikipedia.org/wiki/Key_size