Resume linear algebra
 

I used Brian Gladman's python script which uses GGNFS and MSIEVE to factor 155 digit number, but it threw errors when it came to linear algebra step (I assumed it was because of RAM), so I moved it to another machine with more RAM.
When I ran the script there, it started sieving from beginning (so the .dat file was removed).

Do I have to run some command from cmd to resume linear algebra step?

By the way, I followed [URL="http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html"]this[/URL] guide.

If you still have the .dat file somewhere, eg on the original machine, you can probably restart linear algebra (you may have to re-build the matrix though). If you have lost the .dat file you will have to re-run the whole job. Make a backup copy of the .dat file (and everything else in the directory) before you start experimenting though.

Can you post the log from the failing run so we can see what went wrong. Also a directory listing of where you were running it.

You probably need to re-run the msieve step in the log, replacing -nc2 with -ncr, if you have all the files from the failing attempt at linear algebra. If that fails try running msieve with -nc to rebuild the matrix.

I assume you are running Windows from your mention of running things under cmd. What version is it though?

Chris

Without the relations and the matrix you can't finish the factorization. You need the matrix to resume linear algebra (-ncr to resume or -nc2 to rebuild) and the relations in the sqr fase (-nc3).

The important part is that -ncr is required to resume. Without -ncr you [i]will[/i] overwrite the data, sadly. More than one forum user has lost an in progress matrix in this manner before :smile:

But, if he didn't rerun on the original machine, the relations should still exist there. The OP would also need the original poly file, or fb, IIRC. On the original machine, there should be a compressed file with all the original relations, too.

Or, is my memory really bad, or the comparison between Win and linux too far removed?

The dir should look something like this on Windows (note this is an old dir)

[code]
18-04-2016 18:47 12.761.511.205 C204_119_99.dat.gz
30-12-2015 22:47 99.223 Changes
31-12-2015 22:45 864.110 libmsieve.a
11-09-2015 01:38 56.978 libwinpthread-1.dll
31-12-2015 22:45 3.175.900 msieve-svn988-x64-sandybridge.exe
22-04-2016 01:13 23.917.535.851 msieve.dat
29-04-2016 06:01 570.056.176 msieve.dat.bak.chk
29-04-2016 07:03 570.056.176 msieve.dat.chk
23-04-2016 00:51 509.858.000 msieve.dat.cyc
29-04-2016 07:36 114.010.464 msieve.dat.dep
23-04-2016 00:51 6.132.670.652 msieve.dat.mat
18-04-2016 15:21 429 msieve.fb
18-04-2016 15:21 502 msieve.poly
11-09-2014 14:01 185.976 pthreadGC2.dll
11-09-2014 14:01 82.944 pthreadVC2.dll
30-12-2015 22:47 25.290 Readme
30-12-2015 22:47 57.946 Readme.nfs
30-12-2015 22:47 7.987 Readme.qs
18-04-2016 15:21 205 worktodo.ini
17-08-2015 17:19 90.250 zlib1.dll
[/code]

Hi, I'm sorry for the late reply.

The problem is, this script ran on a really bad virtual machine, which has 4GB RAM and 4 core CPU with 1 thread each. Windows already used 50% of RAM so I guess msieve didn't have enough memory to complete linear algebra. I have Windows 2012 R2 by the way.

So, the minute I stopped the linear algebra step, I saved everything. I attached 2 pictures that show all files (it's zipped, so I couldn't ls it through cmd).

The full log is in attachments.

What RSA number are you trying to break?

This one:
1772352223689553499523382657591107586734440334822954296365208356693849378633858324876899946660923527875550194354495596668114847388151261943936272297881447 (154 digits)

I only use Linux, so I'm guessing a bit. But try the following after extracting the files onto another system:
msieve -s .\rsa/rsa.dat -l .\rsa/rsa.log -i .\rsa/rsa.ini -nf .\rsa/rsa.fb -t 4 -ncr

If that fails try restarting -nc2 from scratch:
msieve -s .\rsa/rsa.dat -l .\rsa/rsa.log -i .\rsa/rsa.ini -nf .\rsa/rsa.fb -t 4 -nc2

If either of those worked then run:
msieve -s .\rsa/rsa.dat -l .\rsa/rsa.log -i .\rsa/rsa.ini -nf .\rsa/rsa.fb -t 4 -nc3

But if they both failed try rebuilding the matrix (this will try to run all msieve steps in one go):
msieve -s .\rsa/rsa.dat -l .\rsa/rsa.log -i .\rsa/rsa.ini -nf .\rsa/rsa.fb -t 4 -nc

Obviously keep the backup zip files safe until you have factored the number.

If you run:
msieve -h
you will get a brief summary of what options msieve accepts. That should help you work out what it wants (eg after -l put the name of the log file.

Chris

I ran (added verbose too)
msieve -v -s .\rsa/rsa.dat -l .\rsa/rsa.log -i .\rsa/rsa.ini -nf .\rsa/rsa.fb -t 4 -ncr
and it threw an error: cannot open matrix checkpoint file, so I guess that won't work. Tried the -nc2, it built the matrix and is now performing linear algebra, BUT I get these errors:

lanczos halted after x iterations (dim = x)
linear algebra failed; retrying
memory use: 868.8 MB
lanczos error: submatrix is not invertible

Those were the same errors as on the virtual machine, I thought they were because of memory, but I have 16 GB of RAM here...

Is this normal? By the way, I'm using the same .dat and .dat.cyc.

Let's hope that the person is sane and doesn't do anything illegal with the factorization of a RSA-512 bit number :mooc:

Haha, nothing illegal, don't worry.

Try the -nc version of the command. Filtering (the -nc1 step that happens between sieving and solving the matrix) is somewhat memory-sensitive, and may have given you a matrix that doesn't solve. So, erase the .cyc file, and run the command line you have but with -nc at the end rather than -nc2.

It will proceed to read all the relations, build a matrix, solve the matrix, and run the final step (square root). Those are individually -nc1, -nc2, and -nc3; runnning -nc does all 3 in order.

Good luck!

This is kind of what VBCurtis has said, but I would add, start with "only" the rsa.dat, rsa.fb and whichever (rsa.n or rsa.ini) has the composite in it. These three files should be all you need. I would also run all three steps separate, although as VBCurtis mentioned -nc would do all three in order and the log file would allow you to observe the activity.

To recap (three files only):
[code]
msieve -i rsa.n (or rsa.ini) -s rsa.dat -l rsa.log -nf rsa.fb -nc1

msieve -i rsa.n (or rsa.ini) -s rsa.dat -l rsa.log -nf rsa.fb -nc2

msieve -i rsa.n (or rsa.ini) -s rsa.dat -l rsa.log -nf rsa.fb -nc3
[/code]or
[code]
msieve -i rsa.n (or rsa.ini) -s rsa.dat -l rsa.log -nf rsa.fb -nc
[/code]

I tried what VBCurtis said and it threw same errors after building matrix and stuff.

[CODE]lanczos halted after 9 iterations (dim = 510)
linear algebra failed; retrying...
commencing Lanczos iteration (4 threads)
memory use: 867.6 MB
lanczos error: submatrix is not invertible[/CODE]

Trying EdH's now (I also included the .poly or should I remove that too?)... but I doubt it will work.

It could be the binaries? I got them from [URL="http://gilchrist.ca/jeff/factoring/index.html"]here[/URL]. I'm using gnfs-win64-ivybridge-asm64 and msieve152_svn939_win64_i7. Do I have to compile from source? Using Windows 10 on the new machine by the way.

[QUOTE=Timic;478150]
It could be the binaries? I got them from [URL="http://gilchrist.ca/jeff/factoring/index.html"]here[/URL]. I'm using gnfs-[B]win64[/B]-[B]ivybridge[/B]-asm64 and msieve152_svn939_[B]win64_i7[/B]. Do I have to compile from source? Using Windows 10 on the new machine by the way.[/QUOTE]
What machine did you do the sieving on? the name of the binary implies it is compiled for windows x64 Ivybridge (probably will work on later architectures)?

Same for the machine you're running Msieve on, is it win64 i7 (or later)?

If you're sure you're using the correct binaries, and still can't get past the linear algebra, maybe you could send your relations (.dat)(preferably compressed like .gz or .7z or .zip etc.) and poly (.fb .poly) to somebody on the forum to eliminate the machine/setup not working correctly. You might have to split it so you can upload/send it (for instance wetransfer.com has a 2GB limit).

If you're concerned about the binaries, run another factorization of something around 100 digits. It'll take an hour or two, but if it completes you have reason to believe your binaries work fine.

I've had another look at the log you posted, and compared it with a successful run I did to factor a 155 digit number. I had 48059844 relations, which is less than the 57105545 relations you have for a slightly smaller number. So that's not the problem.

Nothing else looks odd to me. So re-running the -nc1 step is the next thing to try (if you havn't already).

If that fails I'm out of ideas, short of posting the relations and letting someone else try to solve them.

@jasonp, have you any suggestions?

Chris

[QUOTE=Timic;478150]...
Trying EdH's now (I also included the .poly or should I remove that too?)... but I doubt it will work...[/QUOTE]
.poly is used for sieving. It is converted to .fb for msieve. Only the files referenced in the command line will be accessed initially. All other intermediate files will be created by msieve.

I don't recall if you mentioned running a separate duplicate removal tool on the relations. I know of remdups4 for linux. Maybe someone else might chime in as to whether there is a Windows version. If so, you might want to run it on the relations file, at least prior to zipping and sending, if you choose that direction.

I have an Intel CPU i7 3770 (new machine, where I'm trying to get through linear algebra) - third generation is Ivy Bridge so it can't be binaries. I've seen that msieve version 1.53 is available and I have version 1.52, should I try with the latest version?

I tried to factor a 100 digit composite (1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139, found on Wikipedia). It took 15 minutes to sieve, but then linear algebra went up to 1500% over the last 10 minutes. Is this normal? I cancelled the job.

[CODE]-> msieve -s .\test/test.dat -l .\test/test.log -i .\test/test.ini -nf .\test/test.fb -t 8 -nc1
-> Running matrix solving step ...
-> msieve -s .\test/test.dat -l .\test/test.log -i .\test/test.ini -nf .\test/test.fb -t 8 -nc2
linear algebra completed 2495058 of 163312 dimensions (1527.8%, ETA 529h 2m)[/CODE]

Woot :confused:

Show us your task manager processes.

Can you give us access to the machine through teamviewer so we can take a look onto your files to dig out what’s going on? Or as suggested previously send us the dat file although I can only test it within 8 days.

Please run this msieve benchmark with your msieve version.

[url]http://www.mersenneforum.org/showpost.php?p=362039&postcount=13[/url]

Could some other process interfere with the msieve? Attached processes list.

I ran -nc on the test 100 digit composite again tho - it logged this:
[CODE]using block size 8192 and superblock size 786432 for processor cache size 8192 kB
commencing Lanczos iteration
memory use: 35.4 MB
linear algebra at 7.4%, ETA 0h 1m 163312 dimensions (7.4%, ETA 0h 1m)
linear algebra completed 161907 of 163312 dimensions (99.1%, ETA 0h 0m)
lanczos halted after 2580 iterations (dim = 163083)[/CODE]
then it crashed (msieve.exe has stopped working). If you can point me to where the crash logs are stored, I can put them here.

EDIT: I ran -nc again and it's going above 100% again. Currently at 500%.
EDIT2: Running that benchmark now.

I've never seen msieve exceed 100% on the matrix stage, so seems your msieve binary isn't working properly. I'd find another one from a different source, or download one built for a more generic architecture.

15 min for a quad-core to do the sieving step is about right, so the GGNFS binaries and factmsieve script are likely fine.

Hope the benchmark has been completed successfully.

Yep, got the factors from the benchmark:
[CODE]prp62 factor: 56705226558738617322827862743750795277295350027271122668092243
prp68 factor: 73608085926851965199193284432491192647997340345077698457673136684611[/CODE]
So I guess it was the binaries, gonna replace the msieve now and I will let you know how it goes tomorrow. Thanks.

Glad you got it working!

I would just like you to know that the msieve successfully found 2 primes.

Thanks to everyone who helped! This will make an interesting presentation for my class on how to crack RSA. I learned a lot. :smile:

If you end up doing a powerpoint or something similar, feel free to post it up! :smile:

The powerpoint will be in Slovenian, not English, so no one will be able to understand what's written on it :smile: I might make a blog or something about it in the near future tho :grin:

[QUOTE=Timic;478251]The powerpoint will be in Slovenian, not English, so no one will be able to understand what's written on it :smile: I might make a blog or something about it in the near future tho :grin:[/QUOTE]

Even the equations? Lol

[QUOTE=Timic;478123]Haha, nothing illegal, don't worry.[/QUOTE]

They all say that.

Well done :)

[QUOTE=Timic;478251]The powerpoint will be in Slovenian, not English, so no one will be able to understand what's written on it :smile: [/QUOTE]
Not necessarily!

@Timic: Sorry for bumping an old thread, but you didn't post the factors to factordb. Could you please do that?

[URL]http://www.factordb.com/index.php?id=1100000000829662603[/URL]

@Timic: Hello? I really want to know the factors of that number, and I don't have enough time or RAM to factor it myself. Please post them.