fun with msieve

[michaf]

uh.. right... that was a simple one

However, this now makes the SNFS-diff. to NaN
(What does the accronym mean?)
and still the same error as before :(

-> Working with NAME=test...
-> SNFS_DIFFICULTY is about NaN.
-> Selected default factorization parameters for 100 digit level.
-> Selected lattice siever: ../ggnfs/ggnfs/src/gnfs-lasieve4I12e.exe
-> Creating param file to detect parameter changes...
=> "../ggnfs/ggnfs/src/makefb.exe" -rl 300000 -al 350000 -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...

[michaf]

I just noticed with another number running snfs, that a fourth-degree gives me the SNFS-difficulty, and the 5th degrees do not.
The sieving started just fine on the other number, so my setup seems not to be of any problem so far

[Xyzzy]

Here is a wiki article that may help:

http://www.mersennewiki.org/index.ph...mial_Selection

We really need a SNFS polynomial thread for total beginners, because we can't figure any of this out, even with the paper above and all the posts about it on the forum. The limitation is probably our basic math skills.

We managed to successfully factor a number this week but the polynomial was given to us. (The outpile file is attached.)

[michaf]

Xyzzy,

Thanks for the link, some nice tricks in there.
(However, I think my poly is fine, and I 'just' need to get it started :) )

[jasonp]

Originally Posted by Andi_HB

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

My pleasure, new versions are always in progress.

Originally Posted by michaf

uh.. right... that was a simple one

However, this now makes the SNFS-diff. to NaN
(What does the accronym mean?)
and still the same error as before :(

NaN is Not-A-Number, it's what a computer will give you when you attempt to divide zero by zero. With GGNFS, you should either specify m (= 5^41) so that the program uses a polynomial of X-m, or you should manually specify both coefficients of the polynomial (Y1=1, Y0=-5^41). If you only specify Y0, which you appear to be doing, then Y1 is treated as zero, which is where the divide errors are coming from. Whether Y1 = +1 or -1 should track whether c0 is positive or negative. You want to choose the coefficients so that when you replace X in the polynomials with 5^41, the result modulo the number to be factored is zero.

[michaf]

NaN is Not-A-Number, it's what a computer will give you when you attempt to divide zero by zero. With GGNFS, you should either specify m (= 5^41) so that the program uses a polynomial of X-m, or you should manually specify both coefficients of the polynomial (Y1=1, Y0=-5^41). If you only specify Y0, which you appear to be doing, then Y1 is treated as zero, which is where the divide errors are coming from.

I put both Y0 and Y1 in there
Ah... I see a magic minus sign appear with Y0.. and one disappearing with Y1

..... a quick test shows that that is the problem!
(crunching away at 0.01874 sec/rel)

So, to make things clear for myself, the program uses a polynomial

and if you specify , it takes as being -

Thanks for your patience & time :)

[jasonp]

Originally Posted by michaf

So, to make things clear for myself, the program uses a polynomial

and if you specify , it takes as being -

Thanks for your patience & time :)

You're correct, I didn't notice that Jes forgot a minus sign.

These are really the simplest examples you can find for inventing SNFS polynomials. SNFS applies to a much wider range of input numbers, and the tricks needed to get 1) a polynomial 2) of the correct degree 3) with small enough coefficients can really become very elaborate. In the worst case, you need a computer algebra package to expand and simplify the intermediate mess. See the XYYXF mailing list on yahoogroups for some other SNFS examples.

[masser]

Thanks to everybody that participated in this little side project.

I want to summarize what I believe we learned from this.

1. Our small n candidates have only been factored up to about 30 digits. If we really want to factor the rest of these candidates, we need to do more P-1, P+1 and ECM runs.

2. Msieve works great on general numbers up to 105 digits or so, but for our candidates (with form k*b^n+/-1), there are more efficient factoring techniques (SNFS). If we really want to factor some of these numbers, we need to make the effort to compile and build snfs software.

3. These side projects can attract attention to our project (maybe).

4. never get involved in a land war in Asia

5. never go in against a Sicilian when death is on the line

[michaf]

Originally Posted by jasonp

You're correct, I didn't notice that Jes forgot a minus sign.

These are really the simplest examples you can find for inventing SNFS polynomials. SNFS applies to a much wider range of input numbers, and the tricks needed to get 1) a polynomial 2) of the correct degree 3) with small enough coefficients can really become very elaborate. In the worst case, you need a computer algebra package to expand and simplify the intermediate mess. See the XYYXF mailing list on yahoogroups for some other SNFS examples.

I knew these were the easy ones, but you have to start somewhere :)
Sieving nearing the end now.

The reason why I wanted to plunge into snfs, is that I have a ton of composites, all from cyclic Smarandache numbers (or reverse), and I wanted to see if these were snfs-able.

I have read someplace that someone had done a reverse smarandache with snfs, but I can't find where anymore :(

The type of numbers I'd love to do are:

smarandache: 123456789101112...
reverse smarandache: ...121110987654321
cyclic smarandache : 4567891011...9899123
reverse cyclic smarandache: 1110987654321999897...141312

No idea whether these are even doable with snfs, but spelled decimally, they are easily expressed.
If anyone has any clues as to wether it is possible to get poly's, please give me a few hints, and I'll go delve some deeper.

For now, gnfs will still keep me busy for a year to come (If only snfs could make that 1/4 year :> )

[michaf]

Since the last post, I have refound the snsf-reference for it, and it seems it involves multiplying with 99^2.

http://tech.groups.yahoo.com/group/ggnfs/message/1302

It gives rather large coefficents, but I'll start experimenting with it.

[michaf]

My very first snfs-run has finished.

N=7528*5^204+1
It turned out to have 2 small factors :>
I learned a lot along the way though.

N=292792868823366717321128213730354845519771364538330913612407536725855330141364790907704603928064825677825278038568512783967889845371246337890625001
( 147 digits)
SNFS difficulty: 147 digits.
Divisors found:
r1=352042334615300056485001457009 (pp30)
r2=47330575791755921130680649674330073979 (pp38)
r3=17572106013468407341637483994981767417863184990533618563687045947541523762891291 (pp80)
Version: GGNFS-0.77.1-20060513-athlon-xp
Total time: 30.31 hours.
Scaled time: 47.10 units (timescale=1.554).
Factorization parameters were as follows:
n: 292792868823366717321128213730354845519771364538330913612407536725855330141364790907704603928064825677825278038568512783967889845371246337890625001
type: snfs
skew: 1
c5: 7528
c0: 5
Y0: -45474735088646411895751953125
Y1: 1