How to get started with Factoring

[VictordeHolland]

Originally Posted by pinhodecarlos

Also will LA run in 8 threads with the following command line for a batch of numbers?

Linear Algebra will only run multi-threaded if the matrix is large enough, otherwise it defaults to single-thread. So for <120 digits it is completely normal that LA runs single-threaded.

[RichD]

Originally Posted by pinhodecarlos

Also will LA run in 8 threads with the following command line for a batch of numbers?

start /min /low YAFU-1.34.5-win64.exe "nfs(@)" -batchfile in.bat -threads 8

"-threads <num>" are the number of sievers. "-lathreads <num>" is used to control the LA phase.

Edit: They both can be used on the same command line.

[bsquared]

Originally Posted by RichD

"-threads <num>" are the number of sievers. "-lathreads <num>" is used to control the LA phase.

Edit: They both can be used on the same command line.

If you just use -threads then that works for all parallel phases (sievers, poly and LA). If you use both, then the -lathreads will override the -threads during LA.

For the msieve part of your question, unfortunately there is no way to use an external msieve executable. You're stuck with the embedded one. (You can, of course, compile in the newest one from sources.)

[RichD]

Originally Posted by bsquared

If you just use -threads then that works for all parallel phases (sievers, poly and LA). If you use both, then the -lathreads will override the -threads during LA.

Ah, years ago I ran into this problem. Either it was a bug that was fixed or the number was small as pointed out by Victor (which I can verify). I just kept with my own stubborn ways.

[chris2be8]

Originally Posted by VictordeHolland

Linear Algebra will only run multi-threaded if the matrix is large enough, otherwise it defaults to single-thread. So for <120 digits it is completely normal that LA runs single-threaded.

See https://mersenneforum.org/showthread.php?t=23711 (you can probably do this for the msieve embedded in yafu but I havn't tried that).

Chris

[DukeBG]

Can this thread by sticky, please? I went to find it yesterday only vaguely remembering when and where it was posted and how it was called. And did not find it.

[AlienDjinn]

Originally Posted by VictordeHolland

Jeffs site is temporary down, so users can't access the beginners guide and the links to all the precompiled executables. So here a short version for Windows x64.

Step 1) Download and install Python 3.6
Here is a link to the installer (~30MB):
https://www.python.org/ftp/python/3.....6.5-amd64.exe

Step 2) Download GGNFS.zip (attached to this post, 2.8MB) and extract it to C:\GGNFS .

Import: extract it to that exact path and don't change any filenames.
If you do want to put it in a other path, you'll need to edit the python script to point to the right paths/filenames (lines 63,64,104,117,118).

The zip includes the msieve exe, the python (factmsieve-0.86.py) and lasieve4 sievers, readme files for information and a couple of RSA.n files which has numbers to factor.

The dir C:\GGNFS should now look like this:

-a----        10-5-2018      1:52           1793 Authors-GMPECM.txt
-a----        10-5-2018      1:52           4272 Authors-MPIR.txt
-a----        10-5-2018      1:49         101203 Changelog-msieve.txt
-a----        10-5-2018      1:52          35819 Copying-GMPECM.txt
-a----        10-5-2018      1:52          35819 Copying-MPIR.txt
-a----        10-5-2018      2:01           3700 def-nm-params.txt
-a----        10-5-2018      2:00           4968 def-par.txt
-a----        10-5-2018      3:57          77305 factmsieve-0.86.py
-a----        10-5-2018      1:55              0 gnfs-lasieve4-win64-core2-asm64.txt
-a----       19-10-2016     18:26          94208 gnfs-lasieve4I11e.exe
-a----       19-10-2016     18:26         649290 gnfs-lasieve4I11e_argfix.exe
-a----       19-10-2016     18:26          94208 gnfs-lasieve4I12e.exe
-a----       19-10-2016     18:26         618986 gnfs-lasieve4I12e_argfix.exe
-a----       19-10-2016     18:26          94208 gnfs-lasieve4I13e.exe
-a----       19-10-2016     18:26         603608 gnfs-lasieve4I13e_argfix.exe
-a----       19-10-2016     18:26          94208 gnfs-lasieve4I14e.exe
-a----       19-10-2016     18:26         596268 gnfs-lasieve4I14e_argfix.exe
-a----       19-10-2016     18:26          94208 gnfs-lasieve4I15e.exe
-a----       19-10-2016     18:26         592342 gnfs-lasieve4I15e_argfix.exe
-a----       19-10-2016     18:26          94208 gnfs-lasieve4I16e.exe
-a----       19-10-2016     18:26         589819 gnfs-lasieve4I16e_argfix.exe
-a----        10-5-2018      4:01           3789 msieve-1.53-SVN998-win64-core2-options.txt
-a----       15-10-2016      7:16        1396224 msieve-1.53-SVN998-win64-core2.exe
-a----        10-5-2018      1:53          37678 Readme-GMPECM.txt
-a----        10-5-2018      1:53           4075 Readme-MPIR.txt
-a----        10-5-2018      1:47          25825 Readme-msieve.txt
-a----        10-5-2018      1:48          59002 Readme-NFS.txt
-a----        10-5-2018      1:48           8144 Readme-QS.txt
-a----         5-2-2018     15:27            102 RSA100.n
-a----         5-2-2018     18:45            112 RSA110.n
-a----         5-2-2018     22:42            122 RSA120.n

Step 3) Launch a command-prompt or Windows Powershell (search for cmd.exe or alternatively press Windowskey+X should give you the option to launch Powershell)

Step 4) navigate to C:\GGNFS

cd C:\GGNFS

Step 5) Launch the python scrip and specify what you want to factor. I find it easiest to put the number in a .n txt file (inside the text file is only "n:yournumberhere" ) to make it easier to start from the terminal.

python factmsieve-0.86.py RSA100.n

Step 6) The script should how now perform the GNFS factorization steps:
Lines like this indicate poly search:

-> msieve-1.53-SVN998-win64-core2 -s .\RSA100.dat.T0 -l .\RSA100.log.T0 -i .\RSA100.ini.T0 -nf .\RSA100.fb.T0 -np 1,100 -v > .\RSA100.msp.T0

After a few minutes it should start sieving:

Thu May 10 02:04:20 2018 -> entering sieving loop
Thu May 10 02:04:20 2018 -> making sieve job for q = 900000 in 900000 .. 925000 as file RSA100.job.T0
Thu May 10 02:04:20 2018 -> making sieve job for q = 925000 in 925000 .. 950000 as file RSA100.job.T1
Thu May 10 02:04:20 2018 -> making sieve job for q = 950000 in 950000 .. 975000 as file RSA100.job.T2
Thu May 10 02:04:20 2018 -> making sieve job for q = 975000 in 975000 .. 1000000 as file RSA100.job.T3

Once it has enough relations it should attempt to filter them, perform LA and SQR.

Once it is done you should find the factors at the bottom of the log (RSA100.log)

7) You can delete all the RSA100.xxxx and spairs.gz temporary files if you like.

As you mentioned I got an error with the Python script on RSA100.n. My rough approximation is that there's a bug in the timescale code with very large files.


Total yield: 284168
0/0 mpqs failures, 19634/8406 vain mpqs
milliseconds total: Sieve 64247 Sched 0 medsched 38900
TD 62984 (Init 5857, MPQS 23562) Sieve-Change 57323
TD side 0: init/small/medium/large/search: 1335 5156 1522 1771 10374
sieve: init/small/medium/large/search: 2522 17070 1795 7528 3954
TD side 1: init/small/medium/large/search: 415 3868 1329 1617 5523
sieve: init/small/medium/large/search: 1437 11826 1767 8906 7442
appending spairs.out.T0 to spairs.out
appending spairs.out.T1 to spairs.out
appending spairs.out.T2 to spairs.out
appending spairs.out.T3 to spairs.out
appending spairs.out to RSA100.dat
compressing spairs.out to spairs.save.gz
Found 4361978 relations, 106.5% of the estimated minimum (4095000).
-> msieve-1.53-SVN998-win64-core2 -s .\RSA100.dat -l .\RSA100.log -i .\RSA100.ini -nf .\RSA100.fb -t 4 -nc1
-> Running matrix solving step ...
-> msieve-1.53-SVN998-win64-core2 -s .\RSA100.dat -l .\RSA100.log -i .\RSA100.ini -nf .\RSA100.fb -t 4 -nc2
linear algebra completed 190156 of 191179 dimensions (99.5%, ETA 0h 0m)
-> Running square root step ...
-> msieve-1.53-SVN998-win64-core2 -s .\RSA100.dat -l .\RSA100.log -i .\RSA100.ini -nf .\RSA100.fb -t 4 -nc3
-> Computing time scale for this machine...
-> procrels -speedtest> PIPE
Traceback (most recent call last):
File "factmsieve-0.86.py", line 2253, in <module>
output_summary(NAME, fact_p, pols_p, poly_p, lats_p)
File "factmsieve-0.86.py", line 1911, in output_summary
(ret, res) = run_exe(PROCRELS, '-speedtest', out_file = subprocess.PIPE)
File "factmsieve-0.86.py", line 350, in run_exe
p = subprocess.Popen([ex] + args.split(' '), **al)
File "C:\Users\ken_r\AppData\Local\Programs\Python\Python37\lib\subprocess.py", line 775, in __init__
restore_signals, start_new_session)
File "C:\Users\ken_r\AppData\Local\Programs\Python\Python37\lib\subprocess.py", line 1178, in _execute_child
startupinfo)
FileNotFoundError: [WinError 2] The system cannot find the file specified


>>>>> I "FIXED" it by commenting out this code. When I re-ran the same command it finished and wrote the report to the g100-RSA100.txt file.

>>>>> code commented out - Part I
# # Figure the time scale for this machine.
# output('-> Computing time scale for this machine...')
# (ret, res) = run_exe(PROCRELS, '-speedtest', out_file = subprocess.PIPE)
# if res:
# tmp = grep_l('timeunit:', res)
# timescale = float(re.sub('timeunit:\s*', '', tmp[0]))
# else:
# timescale = 0.0

>>>>> code commented out - Part II
#print('Scaled time: {0:1.2f} units (timescale= {1:1.3f}).'
# .format(total_time * timescale, timescale))


THANKS SO MUCH for the detailed posts Victor de Hollander!

--Alien

[hansl]

Hi, I'm trying to get started on windows 10 64-bit, and have followed the instructions in post #3.

I don't really understand the RSA factoring step, is this just to test that the GGNFS setup is working, or does it need to build some tables for later usage by yafu?

It completed except for the end step of running "procrels"

-> procrels -speedtest> PIPE
Traceback (most recent call last):
  File "factmsieve-0.86.py", line 2253, in <module>
    output_summary(NAME, fact_p, pols_p, poly_p, lats_p)
  File "factmsieve-0.86.py", line 1911, in output_summary
    (ret, res) = run_exe(PROCRELS, '-speedtest', out_file = subprocess.PIPE)
  File "factmsieve-0.86.py", line 350, in run_exe
    p = subprocess.Popen([ex] + args.split(' '), **al)
  File "C:\Users\hans\AppData\Local\Programs\Python\Python37\lib\subprocess.py", line 775, in __init__
    restore_signals, start_new_session)
  File "C:\Users\hans\AppData\Local\Programs\Python\Python37\lib\subprocess.py", line 1178, in _execute_child
    startupinfo)
FileNotFoundError: [WinError 2] The system cannot find the file specified

I found this thread with a link to procrels.exe: https://www.mersenneforum.org/showthread.php?t=21952

So I extracted to C:\GGNFS and ran again, but got another error this time:

-> procrels -speedtest> PIPE
Traceback (most recent call last):
File "factmsieve-0.86.py", line 2253, in <module>
output_summary(NAME, fact_p, pols_p, poly_p, lats_p)
File "factmsieve-0.86.py", line 1914, in output_summary
timescale = float(re.sub('timeunit:\s*', '', tmp[0]))
IndexError: list index out of range

Is this of any consequence or should I just ignore these errors?

Also I'm wondering is it likely that I will be able to factor a ~1100 decimal digit composite number with this software or is that beyond reasonable computability?

Thanks for the step by step instructions and links, very helpful.

[VBCurtis]

Originally Posted by hansl

Also I'm wondering is it likely that I will be able to factor a ~1100 decimal digit composite number with this software or is that beyond reasonable computability?

Thanks for the step by step instructions and links, very helpful.

Difficulty in factoring numbers of no special form doubles every 5 digits or so. Thus, a 200-digit number is a 30-core-year project, and the largest publicly known factorization yet completed is 232 digits (it took some 2000 core-years).

1100 is far, far out of the question.

YAFU does not re-use any previous data; we factor a sample 100-digit number (and then, usually, something 110-120 digits) to make sure things work and to get a feel for how long things take.

[hansl]

Originally Posted by VBCurtis

Difficulty in factoring numbers of no special form doubles every 5 digits or so. Thus, a 200-digit number is a 30-core-year project, and the largest publicly known factorization yet completed is 232 digits (it took some 2000 core-years).

1100 is far, far out of the question.

YAFU does not re-use any previous data; we factor a sample 100-digit number (and then, usually, something 110-120 digits) to make sure things work and to get a feel for how long things take.

Well, I don't know that the factors are necessarily going to be close to the square root, there may be some relatively smaller factors in the number that are still searchable?

Specifically I am interested in fully factorizing fermat number 12 (the first not-fully factored one):
http://factordb.com/index.php?query=2%5E2%5E12%2B1

So there is a 1133 composite factor remaining for it. Is this considered a special form after its been factored already? I was playing with gmp-ecm on a different (linux) machine and it can do -pm1 (B1=1e9) in about an hour. Time seems to scale linearly with the b1 from the tests I've done so far, so I could go try up to 1e12 over ~1.5months. I briefly tested the input limits and it looks like 4e12 is rejected immediately by gmp-ecm, but 3e12 is allowed, so absolute maximum for that method is somehwere between those values.

Or is it likely that factorization has already been attempted up to such limits for this number?

[hansl]

Ok, nevermind, I see now that -pm1 1e10 quicky used all 80GB available ram+swap on the second stage and the process was killed. So much higher is definitely out of the question for me anyways.