Newb question

PicGrabber · 2014-10-28, 17:06

Hi Guys,

I'm really new on this factoring process...

I'm doing some testing on factoring a 154 digit number, but so far after running more than 2 months, on a 16 core machine, seems it get stuck found more than 200% of relations of the estimated minimum.... well.... is this normal ?

Any input will be really appreciated.

Follow there is the latest part of log file:

Code:

Tue Oct 28 14:53:58 2014  Msieve v. 1.52 (SVN Unversioned directory)
Tue Oct 28 14:53:58 2014  random seeds: 894070d5 f5ac8ff5
Tue Oct 28 14:53:58 2014  factoring 72072768185004740358563051119566553651161274827789017091691967225053019202312733660302$
Tue Oct 28 14:53:58 2014  no P-1/P+1/ECM available, skipping
Tue Oct 28 14:53:58 2014  commencing number field sieve (154-digit input)
Tue Oct 28 14:53:58 2014  R0: -727861500029455165753448337222
Tue Oct 28 14:53:58 2014  R1: 48998213182668073
Tue Oct 28 14:53:58 2014  A0: 43086771132098199031797347785629544105
Tue Oct 28 14:53:58 2014  A1: 381147722825056832454953819804967
Tue Oct 28 14:53:58 2014  A2: 154794203159127330013186513
Tue Oct 28 14:53:58 2014  A3: -2452774929706423983
Tue Oct 28 14:53:58 2014  A4: -1344669234002
Tue Oct 28 14:53:58 2014  A5: 35280
Tue Oct 28 14:53:58 2014  skew 9775467.26, size 6.327e-15, alpha -8.184, combined = 3.334e-12 rroots = 5
Tue Oct 28 14:53:58 2014
Tue Oct 28 14:53:58 2014  commencing relation filtering
Tue Oct 28 14:53:58 2014  estimated available RAM is 30100.9 MB
Tue Oct 28 14:53:58 2014  commencing duplicate removal, pass 1
Tue Oct 28 14:53:58 2014  error -15 reading relation 9478
Tue Oct 28 15:01:07 2014  found 59569829 hash collisions in 119409736 relations
Tue Oct 28 15:01:36 2014  commencing duplicate removal, pass 2
Tue Oct 28 15:02:23 2014  found 91059808 duplicates and 28349928 unique relations
Tue Oct 28 15:02:23 2014  memory use: 724.8 MB
Tue Oct 28 15:02:24 2014  reading ideals above 88670208
Tue Oct 28 15:02:24 2014  commencing singleton removal, initial pass
Tue Oct 28 15:04:41 2014  memory use: 753.0 MB
Tue Oct 28 15:04:41 2014  reading all ideals from disk
Tue Oct 28 15:04:41 2014  memory use: 432.2 MB
Tue Oct 28 15:04:42 2014  commencing in-memory singleton removal
Tue Oct 28 15:04:43 2014  begin with 28349928 relations and 27499045 unique ideals
Tue Oct 28 15:04:47 2014  reduce to 9930955 relations and 4731784 ideals in 14 passes
Tue Oct 28 15:04:47 2014  max relations containing the same ideal: 15
Tue Oct 28 15:04:48 2014  reading ideals above 100000
Tue Oct 28 15:04:48 2014  commencing singleton removal, initial pass
Tue Oct 28 15:06:07 2014  memory use: 376.5 MB
Tue Oct 28 15:06:07 2014  reading all ideals from disk
Tue Oct 28 15:06:07 2014  memory use: 423.0 MB
Tue Oct 28 15:06:08 2014  keeping 13847504 ideals with weight <= 200, target excess is 53270
Tue Oct 28 15:06:09 2014  commencing in-memory singleton removal
Tue Oct 28 15:06:10 2014  begin with 9930956 relations and 13847504 unique ideals
Tue Oct 28 15:06:12 2014  reduce to 205 relations and 0 ideals in 9 passes
Tue Oct 28 15:06:12 2014  max relations containing the same ideal: 0
Tue Oct 28 15:06:12 2014  filtering wants 1000000 more relations
Tue Oct 28 15:06:12 2014  elapsed time 00:12:14
Tue Oct 28 15:06:12 2014 LatSieveTime: 4185.38
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112328 as file Factr.job.T0
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112385 as file Factr.job.T1
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112442 as file Factr.job.T2
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112500 as file Factr.job.T3
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159124915 as file Factr.job.T4
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159124943 as file Factr.job.T5
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159124971 as file Factr.job.T6
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159125000 as file Factr.job.T7
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137491 as file Factr.job.T8
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137494 as file Factr.job.T9
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137497 as file Factr.job.T10
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137500 as file Factr.job.T11
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159149948 as file Factr.job.T12
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159149965 as file Factr.job.T13
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159149982 as file Factr.job.T14
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159150000 as file Factr.job.T15
Tue Oct 28 15:06:12 2014 -> Lattice sieving algebraic q from 159100000 to 159200000.
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T0 -v -n0 -a Factr.job.T0
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T1 -v -n1 -a Factr.job.T1
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T2 -v -n2 -a Factr.job.T2
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T3 -v -n3 -a Factr.job.T3
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T4 -v -n4 -a Factr.job.T4
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T5 -v -n5 -a Factr.job.T5
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T6 -v -n6 -a Factr.job.T6
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T7 -v -n7 -a Factr.job.T7
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T8 -v -n8 -a Factr.job.T8
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T9 -v -n9 -a Factr.job.T9
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T10 -v -n10 -a Factr.job.T10
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T11 -v -n11 -a Factr.job.T11
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T12 -v -n12 -a Factr.job.T12
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T13 -v -n13 -a Factr.job.T13
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T14 -v -n14 -a Factr.job.T14
Tue Oct 28 15:06:12 2014 -> gnfs-lasieve4I14e -k -o spairs.out.T15 -v -n15 -a Factr.job.T15
Tue Oct 28 16:06:32 2014 Found 119472517 relations, 209.5% of the estimated minimum (57029236).
Tue Oct 28 16:06:32 2014
Tue Oct 28 16:06:32 2014
Tue Oct 28 16:06:32 2014  Msieve v. 1.52 (SVN Unversioned directory)
Tue Oct 28 16:06:32 2014  random seeds: 1cb514d0 a95d2f8a
Tue Oct 28 16:06:32 2014  factoring 72072768185004740358563051119566553651161274827789017091691967225053019202312733660302$
Tue Oct 28 16:06:32 2014  no P-1/P+1/ECM available, skipping
Tue Oct 28 16:06:32 2014

AND SO ON....
Thanks

Batalov · 2014-10-28, 19:29

The poly is fine for this size, but you are using some broken version of the sieving script.
See highlighted areas below:

Quote:

Originally Posted by PicGrabber

Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112328 as file Factr.job.T0
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112385 as file Factr.job.T1
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112442 as file Factr.job.T2
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159100000 in 159100000 .. 159112500 as file Factr.job.T3
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159124915 as file Factr.job.T4
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159124943 as file Factr.job.T5
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159124971 as file Factr.job.T6
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159112500 in 159112500 .. 159125000 as file Factr.job.T7
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137491 as file Factr.job.T8
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137494 as file Factr.job.T9
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137497 as file Factr.job.T10
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159125000 in 159125000 .. 159137500 as file Factr.job.T11
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159149948 as file Factr.job.T12
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159149965 as file Factr.job.T13
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159149982 as file Factr.job.T14
Tue Oct 28 15:06:12 2014 -> making sieve job for q = 159137500 in 159137500 .. 159150000 as file Factr.job.T15

In essence, most of your threads are doing the same job over and over again.

Now, it is important to know that as implemented, the lattice sieving is deterministic.
That is, if you sieve twice
q = 159125000 in 159125000 .. 159137494 as file Factr.job.T9
and
q = 159125000 in 159125000 .. 159137497 as file Factr.job.T10 (which is practically the same area)
you will get the same result files.

But for the factoring to succeed the relations have to be all unique. At the filtering stage all repeated relations (and yours are repeated ~4 times each) are discarded, so you have less than ~1/4 of the number of relations that you would have with a good script. You are now virtually at ~50% needed relations, not ~200%

wombatman · 2014-10-28, 19:47

Did you change the number of threads used for sieving at any point in the process?

PicGrabber · 2014-10-28, 19:56

HHmmm...

Actually I have changed the thread number, yes.... but I can't remember if it was at beginning or at some point of it.
I saw some errors when running more than one thread, so I changed to have only one.

Any idea to "fix", improve this repetition ?

thanks.

PicGrabber

Batalov · 2014-10-28, 20:29

One thing that the script is equipped to do is restart. You can kill the existing script.
Then backup the whole directory, just in case something goes wrong later. You will "bite your elbows", as the Russian saying goes, if you don't.

Then you have to examine the script and if you know a bit of perl (python), change it so that it does indeed prepare 1/16th slices of each chunk of work. Or you can try to get the latest script from http://sourceforge.net/p/ggnfs/code/.../factMsieve.pl and be sure to edit to set CPU number to 16 and then start the new copy. You can post the similar log output later and we will check if this worked.

Batalov · 2014-10-28, 20:49

Another (optional) thing to do is this: you don't have* to drag the existing set (which is 4 times bloated) into the new (continued) run.

Now, here's what you can do.
1. Get the remdups.c source and build it.
2. cat Factr.dat spar* | remdups 250 > Factr2.dat
(and observe the output of this binary; it should say in the end how many unique relations it wrote to the new file and how many were redundant)
3. If step 2 goes well, then replace Factr.dat with Factr2.dat

____
*you can but it will be suboptimal. The script will try to filter every time, needlessly. It will finish nevertheless but later than if you do a bit of cleanup.

wombatman · 2014-10-28, 20:59

You've run into the same problem I have with changing threads midstream.

The other alternative (and one I've employed on a few occasions) is to edit the main job file. In short, you need to manually divide up the sections into 16 chunks across the Q-range. I think the default size of 100,000, so each chunk would be just 6,250. I'm at work, so I can't pull up an example file, but that's the general idea. You may need to delete the ".job.T*" files before you restart.

debrouxl · 2014-10-28, 21:01

A 154-digit integer (cut off in your paste)... a 512-bit RSA key, perhaps ?

As Batalov wrote, the jobs are now broken. 16 modern cores need significantly less than 2 months to go through a 512-bit RSA key, they should only need 2 weeks at worst.

Batalov · 2014-10-28, 21:11

Quote:

Originally Posted by wombatman

...You may need to delete the ".job.T*" files before you restart.

This may force the script to start sieving from low values again, which is as good as starting from the beginning.
I don't know about the .py script, but perl script looks up the last q0_start from .job.T1 file.

Also note that the number is easily reconstructed from the polynomial (it is a resultant). Left as an exercise to the reader. It is not factored in FactorDB and is not a cofactor of any interesting number, so yeah, looks like a key. Who knows what this key will open, maybe a BMW recovered from another state, or someone's account on a weak outdated network... /sigh/

...which reminds me of a Dr.House's team dilemma in one of the episodes. '"And we saved him", Taub remarks grimly.'

VBCurtis · 2014-10-28, 22:31

If you restart with 16 threads, and do not edit the script during the run, you should get back to this number of unique relations in about 2 days. I think you're better off with a fresh start in a new folder than you are trying to fix what is wrong in this run.

It appears you had it set to 8 threads at some point, then 4, then 16. The part of the script that divides each interval of 100k Q into pieces for the threads bases its new pieces on the previous run's pieces; it does not expect to be asked to change the size of the pieces on the fly. It pulls the number of threads from the script itself, so when the # of threads changes, it just makes up new intervals in a way that isn't actually doing unduplicated work.

A 4-core desktop could do this number in 2 weeks or less, so you should be able to gather enough relations in 4-5 days to survive filtering and proceed to the matrix step. It's common to "need" 120% or so of "expected relations"; the expected number is set low intentionally to trigger filtering attempts sooner than necessary. This prevents wasting time gathering more relations than strictly necessary, but is confusing to beginners to the script. There is no precise prediction of how many relations are needed a priori; we do the filtering step to ask "are we there yet?" of the relation set. In the default script, it's not unusual for filtering to fail quite a few times.

wombatman · 2014-10-29, 02:55

Quote:

Originally Posted by Batalov

This may force the script to start sieving from low values again, which is as good as starting from the beginning.
I don't know about the .py script, but perl script looks up the last q0_start from .job.T1 file.

Also note that the number is easily reconstructed from the polynomial (it is a resultant). Left as an exercise to the reader. It is not factored in FactorDB and is not a cofactor of any interesting number, so yeah, looks like a key. Who knows what this key will open, maybe a BMW recovered from another state, or someone's account on a weak outdated network... /sigh/

...which reminds me of a Dr.House's team dilemma in one of the episodes. '"And we saved him", Taub remarks grimly.'

That's a good point. I didn't want to say for sure since I couldn't check.

2014-10-28, 21:01	#8
debrouxl Sep 2009 977 Posts	A 154-digit integer (cut off in your paste)... a 512-bit RSA key, perhaps ? As Batalov wrote, the jobs are now broken. 16 modern cores need significantly less than 2 months to go through a 512-bit RSA key, they should only need 2 weeks at worst. Last fiddled with by debrouxl on 2014-10-28 at 21:02

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Newb who needs help with PC	EddieTheBear	Hardware	19	2015-10-23 13:22
100MD LL Test - Newb Question	Neo	Information & Answers	6	2011-01-02 16:01
Questions from a GIMPS newb	hj47	Hardware	10	2008-10-28 20:00
Newb help (it crashes)	Proggie	Software	4	2005-01-05 07:35
linux question ( newb)	crash893	Software	2	2003-12-26 18:50

2014-10-28, 19:47	#3
wombatman I moo ablest echo power! May 2013 1,741 Posts	Did you change the number of threads used for sieving at any point in the process?

2014-10-28, 19:56	#4
PicGrabber Oct 2014 7₁₀ Posts	HHmmm... Actually I have changed the thread number, yes.... but I can't remember if it was at beginning or at some point of it. I saw some errors when running more than one thread, so I changed to have only one. Any idea to "fix", improve this repetition ? thanks. PicGrabber

2014-10-28, 20:29	#5
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴·3·193 Posts	One thing that the script is equipped to do is restart. You can kill the existing script. Then backup the whole directory, just in case something goes wrong later. You will "bite your elbows", as the Russian saying goes, if you don't. Then you have to examine the script and if you know a bit of perl (python), change it so that it does indeed prepare 1/16th slices of each chunk of work. Or you can try to get the latest script from http://sourceforge.net/p/ggnfs/code/.../factMsieve.pl and be sure to edit to set CPU number to 16 and then start the new copy. You can post the similar log output later and we will check if this worked.

2014-10-28, 20:49	#6
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴·3·193 Posts	Another (optional) thing to do is this: you don't have* to drag the existing set (which is 4 times bloated) into the new (continued) run. Now, here's what you can do. 1. Get the remdups.c source and build it. 2. cat Factr.dat spar* \| remdups 250 > Factr2.dat (and observe the output of this binary; it should say in the end how many unique relations it wrote to the new file and how many were redundant) 3. If step 2 goes well, then replace Factr.dat with Factr2.dat ____ *you can but it will be suboptimal. The script will try to filter every time, needlessly. It will finish nevertheless but later than if you do a bit of cleanup.

2014-10-28, 20:59	#7
wombatman I moo ablest echo power! May 2013 1,741 Posts	You've run into the same problem I have with changing threads midstream. The other alternative (and one I've employed on a few occasions) is to edit the main job file. In short, you need to manually divide up the sections into 16 chunks across the Q-range. I think the default size of 100,000, so each chunk would be just 6,250. I'm at work, so I can't pull up an example file, but that's the general idea. You may need to delete the ".job.T*" files before you restart.

2014-10-28, 22:31	#10
VBCurtis "Curtis" Feb 2005 Riverside, CA 2²·13·89 Posts	If you restart with 16 threads, and do not edit the script during the run, you should get back to this number of unique relations in about 2 days. I think you're better off with a fresh start in a new folder than you are trying to fix what is wrong in this run. It appears you had it set to 8 threads at some point, then 4, then 16. The part of the script that divides each interval of 100k Q into pieces for the threads bases its new pieces on the previous run's pieces; it does not expect to be asked to change the size of the pieces on the fly. It pulls the number of threads from the script itself, so when the # of threads changes, it just makes up new intervals in a way that isn't actually doing unduplicated work. A 4-core desktop could do this number in 2 weeks or less, so you should be able to gather enough relations in 4-5 days to survive filtering and proceed to the matrix step. It's common to "need" 120% or so of "expected relations"; the expected number is set low intentionally to trigger filtering attempts sooner than necessary. This prevents wasting time gathering more relations than strictly necessary, but is confusing to beginners to the script. There is no precise prediction of how many relations are needed a priori; we do the filtering step to ask "are we there yet?" of the relation set. In the default script, it's not unusual for filtering to fail quite a few times.