How to use my own polynomial with Msieve

[jasonp]

jordis: of course it's possible to use msieve by itself to factor RSA130. Msieve will finish 3-4x faster if you generate a polynomial of your own (see guide). On top of that, using GGNFS for the sieving will complete 5x faster than using msieve, even with the same polynomial (see guide). Considering that the sieving will take ~1 week after you do both of the above, this is a considerable savings in time.

You just have to

- install GGNFS
- determine the polynomial you want
- put the polynomial in a text file that GGNFS will understand
- run the factMsieve.pl perl script

Good luck. Others have tried using just msieve for large jobs, and the exercise will take more patience than you likely have.

[jordis]

I'll try to explain me better.

Msieve 1.41 found the next polynomial:

R0: -8924486172666962366962516
R1: 145411794718189
A0: 168755071662659923747852490418825
A1: -3984467007355947750022001202
A2: 11277970053707868290387
A3: 78231399916697658
A4: -4991900068
A5: 31920
skew 385657.43, size 1.594433e-012, alpha -7.678658, combined = 7.617254e-011

When I tried to determine how good it's the polynomial:
>msieve.exe -v -ns 330001,330101
completed b = 330101, found 22 relations
elapsed time 00:12:28

This is not a good polynomial, then I want to test this:
5748,30224,87384,05200 X^5 + 9882,26191,74822,86102 X^4
- 13392,49938,91281,76685 X^3 + 16875,25245,88776,84989 X^2
+ 3759,90017,48552,08738 X - 46769,93055,39319,05995


The question was,

How do I put the polynomial in a text file that msieve can understand?

[akruppa]

Originally Posted by FactorEyes

Ah-yup: I've factored RSA-129 twice now. It's my reference stick, kept under a vacuum-sealed bell jar at a steady temperature.

We use the original RSA155 polynomial a lot for testing the CADO siever. I think we've factored it completely 3 or 4 times or so, but if you sum up the relations found in partial sieving tests, there must have been enough to factor it twenty times over.

Alex

[bsquared]

Originally Posted by jordis

How do I put the polynomial in a text file that msieve can understand?

you probably want something like this in msieve.fb

N 1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557
SKEW 1.00
R0 -12574411168418005980468
R1 1
A0 -46769930553931905995
A1 3759900174855208738
A2 16875252458877684989
A3 -13392499389128176685
A4 9882261917482286102
A5 5748302248738405200

[jasonp]

The msieve polynomial has a very low yield because it has an extremely large amount of skew. You cannot sieve lines around 300k; most of the relations you can find will be below 20k, and to compensate you have to line sieve using lines that are much wider than the default msieve chooses. Compare the yield at 300k with the number of relations you find at 1k. The polynomial is fine, you just cannot sieve with it for very long.

Now use the sieving tools in GGNFS and watch the sieving speed take off.

[jordis]

bsquared: Thanks.

With "my" polynomial and same range:

completed b = 330101, found 183 relations
elapsed time 00:12:48


completed b = 1100, found 435 relations
elapsed time 00:11:56


Do you thing that this is a good polynomial?


Jason:

I had factorized RSA120 and I had to get relations near b=1726k (544 relations)
If I want to factorize RSA130 surely I'll need to test larger range?


I use a parallel msieve's modification, I can't use GGNFS :-(
To factorize RSA130 I have almost 70 computers, this is the reason for I want a good polynomial. I have already tested with a not good polynomial and was impossible to factor the number

[jasonp]

"Your" polynomial has a skew of nearly 1.0, which means the number of relations you get will drop off fairly slowly over a large number of lines. A skew of 1.0 means that the (a,b) number for each relation should have nearly the same size values of 'a' and 'b'.

Msieve's polynomial expects the 'a' values to be 386000 times larger than the 'b' values. This means that virtually all the relations you will find will be for lines less than about 10k. This is far too few for the line sieve in msieve; even if you did all 10k lines, you would only find ~10% of the relations you would need. However, the lattice sieve in GGNFS looks for relations over a much larger area, and can work with this restriction easily.

If you figured out how the GGNFS lattice siever works, with 70 machines you can finish off the sieving for RSA130 in maybe 6 hours. With msieve alone and 'your' polynomial it would need maybe a week.

PS: Now I remember where I first saw you. Your project really will only work with unskewed (skew=1) polynomials because you are limiting yourself to the line sieve in msieve. The code can also generate unskewed polynomials, if you build from source. I would think you would need maybe 10 million lines...

[jordis]

Is the "SKEW" value 1 because has to be 1? or is it 1 because bsquared write 1?

Has someone a 130-digit number and its associated polynomial for testing?


Thanks

[jasonp]

The optimal skew for your polynomial is close to 1. It may be 2 or 3, but any choice around this size will work about the same.

(Msieve doesn't use the skew at all...)

[Andi_HB]

Originally Posted by jordis

I use a parallel msieve's modification, I can't use GGNFS :-(

If you cant`t use GGNFS because Perl or the configuration of factMsieve.pl is the Problem u can try the Ubasic script. Its easy to use with GGNFS and don`t need a configuration.
The Ubasic script and Informations how to use you can read here http://www.mersenneforum.org/showthread.php?t=11438

Regards Andi_HB

[jasonp]

Jordi is involved with a BOINC client that calls the msieve binary (or uses the msieve library directly, he never specified which). Of course, if you can call one binary, it should be easy to call a lattice sieve binary instead...