fun with msieve

[fivemack]

52922 * 5^172 - 1

is

P59 32599483763372345759798382914032153002917095147476974965231
P67 2711853794492163994795944424494187019620533385136340335327072913079

This took 7.2 hours with snfs on one CPU K8/2200; the machine I have access to is a dual-core, so I ran the number twice, one with a degree-4 and once with a degree-5 polynomial, and both took the same amount of time to within ten minutes.

[mdettweiler]

Since I've reserved the candidate, msieve has gotten a little more than 10 hours of CPU time total. Yet (and yes, I can confirm that msieve is correctly resuming from previous stop points because it says in the log, or in the console if I run it with the -v option, that it resumed from a previous save point), my current progress line in the console output shows this:

3021 relations (2828 full + 193 combined from 171995 partial), need 140096

I ran it through a calculator to find out what % done that was, and it turns out that 3021 of 140096 is about 2.2%. After 10 hours of CPU time, I would have expected to have more than that; is there something that I'm not factoring into my percentage calculation that I should be? Or is it just that these factorizations take a very long time?

Considering how long this is taking, I'd kind of rather spend my CPU time working on something that's actually more useful, so would it be OK if I attached my msieve.dat file to a message here and let someone else take my candidate from where I left off?

[bsquared]

Originally Posted by Anonymous

I ran it through a calculator to find out what % done that was, and it turns out that 3021 of 140096 is about 2.2%. After 10 hours of CPU time, I would have expected to have more than that; is there something that I'm not factoring into my percentage calculation that I should be? Or is it just that these factorizations take a very long time?

The msieve implementation of QS for these size numbers uses the double large prime variation. Basically what this means is that the growth rate of relations is non-linear, and you can't compute percent done that way. After a while, the number of relations combined from partials will start to explode and will eventually dominate over the number of full relations. That said, you still have a long way to go...

- ben.

[Andi_HB]

Anonymous after 10 hours you must have more than 3000 relations if you have an actually Processor.

If it`s ok i reserve the number from anonymous 45742*5^143-1
I have started msieve yesterday and have now after 15 hours :
38437 relations (19422 full + 19015 combined from 1185048 partial), need 140096
I think the factorization take 2 more days.

[mdettweiler]

Originally Posted by Andi_HB

Anonymous after 10 hours you must have more than 3000 relations if you have an actually Processor.

If it`s ok i reserve the number from anonymous 45742*5^143-1
I have started msieve yesterday and have now after 15 hours :
38437 relations (19422 full + 19015 combined from 1185048 partial), need 140096
I think the factorization take 2 more days.

Okay. I was actually going to post my msieve.dat file here in case whoever wanted to reserve it instead of me wanted to pick up where I left off (thus saving part of the work being done twice). But I guess if you've already started working on my candidate and have gotten farther than I was, then I may as well not bother.

masser, you can change the name on the reservation now.

Andi_HB, what kind of processor are you running it on? I was using a Pentium 4 3.2GHz HT, and it had an entire thread to itself. (With hyperthreading, things take about twice as long to do, but you can do two tasks at a time.) Maybe it had only gotten as far as it did because of the hyperthreading.

[bsquared]

Originally Posted by Anonymous

Andi_HB, what kind of processor are you running it on? I was using a Pentium 4 3.2GHz HT, and it had an entire thread to itself. (With hyperthreading, things take about twice as long to do, but you can do two tasks at a time.) Maybe it had only gotten as far as it did because of the hyperthreading.

Msieve (like other fast QS implementations) get its speed from heavily optimized memory accessing. It tries hard to keep everything in first L1 then L2 cache as much as possible. I don't know much about hyperthreading, but I suspect that anything else running in another thread that was also accessing memory would severely effect msieve's performance, much more than 2x. This differs from multi-core architectures because each core has its own cache.

[ValerieVonck]

Originally Posted by fivemack

You haven't quite understood the syntax of the file; my notes are written in general maths notation, but the ggnfs input file requires the parameters to be given as

c4: 71098

with the parameter name (the c has to be lower-case, the Y has to be upper-case), a colon, a space, and the parameter value. And you have to write the numbers explicitly, so

Y0: 5684341886080801486968994140625

because

Y0: 5^44

will be parsed as setting Y0=5.

You should also put Y1 as -1 (because the value at which the polynomial is evaluated is the root of Y0+Y1*x=0, ie if you want the value to be Y then you should have Y0=Y and Y1=-1 to get the equation Y-x=0); but it doesn't matter here because the polynomial has coefficients only at even powers, and (-t)^4 = t^4.

By following your instructions I came up with following poly file

n: 74229775530521455488007758492787522898438620227229981378006965553757821319102732125294955012329012333793798461556434631347656251
type: snfs
skew: 1
c4: 71098
c0: 1
Y0: 5684341886080801486968994140625
Y1: -1

GGNFS ran smoothly but then crashed when processing the relations?
Can anyone enlighten me?

Thx

[Andi_HB]

Originally Posted by Anonymous

Andi_HB, what kind of processor are you running it on? I was using a Pentium 4 3.2GHz HT, and it had an entire thread to itself. (With hyperthreading, things take about twice as long to do, but you can do two tasks at a time.) Maybe it had only gotten as far as it did because of the hyperthreading.

I have also a Pentium 4 HT but only 2.6GHz! Because the Hyperthreading Processor`s are not two real Hardwareprocessors i only use one thread.
If i do run 2 msieve thread`s my PC make trouble and i can`t use Inet .....
I think with the new Core2 Duo ore Quad it maybe better to make 2 or more threads-but not with my P4HT Processor.

Andi_HB

[Andi_HB]

The work is done
The factors of 45742*5^143-1 are
prp36 factor: 578037285615470899665893992114959193
prp69 factor: 709692011365907351480560401645431000568960939811347710470002422761693

At this time i want to say thank you to jasonp for his good work @ msieve!
I hope many new Version will follow :)

Sat Sep 08 14:20:02 2007  Msieve v. 1.26
Sat Sep 08 14:20:02 2007  random seeds: 37d705c0 f032a970
Sat Sep 08 14:20:02 2007  factoring 410228443872933007732436727032622999532939147170019740362955631626795671706986468052491545677185058593749 (105 digits)
Sat Sep 08 14:20:03 2007  commencing quadratic sieve (105-digit input)
Sat Sep 08 14:20:03 2007  using multiplier of 1
Sat Sep 08 14:20:03 2007  using 64kb Pentium 4 sieve core
Sat Sep 08 14:20:03 2007  sieve interval: 18 blocks of size 65536
Sat Sep 08 14:20:03 2007  processing polynomials in batches of 6
Sat Sep 08 14:20:03 2007  using a sieve bound of 3950183 (140000 primes)
Sat Sep 08 14:20:03 2007  using large prime bound of 592527450 (29 bits)
Sat Sep 08 14:20:03 2007  using double large prime bound of 6178388598508650 (44-53 bits)
Sat Sep 08 14:20:03 2007  using trial factoring cutoff of 53 bits
Sat Sep 08 14:20:03 2007  polynomial 'A' values have 14 factors
Sat Sep 08 14:20:10 2007  restarting with 34029 full and 2067167 partial relations
Sat Sep 08 14:20:10 2007  140389 relations (34029 full + 106360 combined from 2067167 partial), need 140096
Sat Sep 08 14:20:14 2007  begin with 2101196 relations
Sat Sep 08 14:20:17 2007  reduce to 366337 relations in 12 passes
Sat Sep 08 14:20:17 2007  attempting to read 366337 relations
Sat Sep 08 14:20:26 2007  recovered 366337 relations
Sat Sep 08 14:20:26 2007  recovered 357347 polynomials
Sat Sep 08 14:20:26 2007  attempting to build 140389 cycles
Sat Sep 08 14:20:26 2007  found 140389 cycles in 6 passes
Sat Sep 08 14:20:26 2007  distribution of cycle lengths:
Sat Sep 08 14:20:26 2007     length 1 : 34029
Sat Sep 08 14:20:26 2007     length 2 : 24367
Sat Sep 08 14:20:26 2007     length 3 : 24046
Sat Sep 08 14:20:26 2007     length 4 : 19060
Sat Sep 08 14:20:26 2007     length 5 : 14273
Sat Sep 08 14:20:26 2007     length 6 : 9836
Sat Sep 08 14:20:26 2007     length 7 : 6074
Sat Sep 08 14:20:26 2007     length 9+: 8704
Sat Sep 08 14:20:26 2007  largest cycle: 21 relations
Sat Sep 08 14:20:27 2007  matrix is 140000 x 140389 with weight 9613514 (avg 68.48/col)
Sat Sep 08 14:20:32 2007  filtering completed in 4 passes
Sat Sep 08 14:20:32 2007  matrix is 134051 x 134115 with weight 9221720 (avg 68.76/col)
Sat Sep 08 14:20:34 2007  saving the first 48 matrix rows for later
Sat Sep 08 14:20:34 2007  matrix is 134003 x 134115 with weight 7156974 (avg 53.36/col)
Sat Sep 08 14:20:34 2007  matrix includes 64 packed rows
Sat Sep 08 14:20:34 2007  using block size 21845 for processor cache size 512 kB
Sat Sep 08 14:20:34 2007  commencing Lanczos iteration
Sat Sep 08 14:24:33 2007  lanczos halted after 2121 iterations
Sat Sep 08 14:24:34 2007  recovered 15 nontrivial dependencies
Sat Sep 08 14:24:37 2007  prp36 factor: 578037285615470899665893992114959193
Sat Sep 08 14:24:37 2007  prp69 factor: 709692011365907351480560401645431000568960939811347710470002422761693
Sat Sep 08 14:24:37 2007  elapsed time 00:04:35

[michaf]

I decided to give 7528*5^204+1 a go with snfs (my very first snfs try)

It has 147 digits --> bigger then c120 and smaller then c200 so I decided to use degree 5 polynomial

204 = 4 mod 5, so I need to go one up to get 0 mod 5
f(x) = 7528*5^204+1
5*f(x) = 7528*5^205+5

so, c4 = 7528 and c0 = 5

Y0 should be 5^41 because 205/5 = 41
Y0 = 45474735088646411895751953125

My .poly now became:

n: 292792868823366717321128213730354845519771364538330913612407536725855330141364790907704603928064825677825278038568512783967889845371246337890625001
type: snfs
skew: 1
c4: 7528
c0: 5
Y0: 45474735088646411895751953125
Y1: -1

One thing I don't understand is how to choose Y1.
both Y1=1 and Y1=-1 give the same error while making the factor base:

=> "../ggnfs/ggnfs/src/makefb.exe" -rl 600000 -al 800000 -lpbr 25 -lpba 25 -3p -of test.fb -if test.poly
Making factor base...Error: Bad polynomial: f(m) !=0 (mod n)
m = 0
Making factor base...Error: Bad polynomial: f(m) !=0 (mod n)
m = 0
Return value 65280. Terminating...

Is there any flaw in my reasoning, or am I doing something wrong fundamentally? (or both)

Thanks for helping out

[JHansen]

Originally Posted by michaf

I decided to give 7528*5^204+1 a go with snfs (my very first snfs try)

It has 147 digits --> bigger then c120 and smaller then c200 so I decided to use degree 5 polynomial

204 = 4 mod 5, so I need to go one up to get 0 mod 5
f(x) = 7528*5^204+1
5*f(x) = 7528*5^205+5

Correct.

Originally Posted by michaf

so, c4 = 7528 and c0 = 5

Not quite. You are making a degree 5 polynomial, not a degree 4. Hence c5=7528 and c0= 5.

You are using M=5^41 as root, as you correctly inferred, thus your linear polynomial is X-M, Hence Y1=1 and Y0=5^41.

Cheers,
Jes