mersenneforum.org Newb question
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-10-28, 17:06 #1 PicGrabber   Oct 2014 1112 Posts Newb question 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
2014-10-28, 19:29   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

994210 Posts

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%

 2014-10-28, 19:47 #3 wombatman I moo ablest echo power!     May 2013 5·192 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·1,657 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 26D616 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 70D16 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, 21:01 #8 debrouxl     Sep 2009 2·3·163 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
2014-10-28, 21:11   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,657 Posts

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.'

Last fiddled with by Batalov on 2014-10-28 at 21:18

2014-10-29, 02:55   #11
wombatman
I moo ablest echo power!

May 2013

5·192 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post EddieTheBear Hardware 19 2015-10-23 13:22 Neo Information & Answers 6 2011-01-02 16:01 hj47 Hardware 10 2008-10-28 20:00 Proggie Software 4 2005-01-05 07:35 crash893 Software 2 2003-12-26 18:50

All times are UTC. The time now is 02:09.

Sat Oct 1 02:09:19 UTC 2022 up 43 days, 23:37, 0 users, load averages: 0.97, 1.07, 1.07

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔