Large small factor

[akruppa]

These numbers are, in fact, correct. 140 = 2 * 2 * 5 * 7, so we can try to factor 376^70+1 and divide out the algebraic factor 376^14+1 (makes a degree 4 polynomial and leaves difficulty 144) or 376^10+1 (makes a degree 6 polynomial and leaves difficulty 155). If you force degree 5, phi.c can't divide out any algebraic factors at all, so the difficulty is 70*log_10(376)=180 there.

If you wanted to divide out both algebraic factors, you'd get a degree 24 polynomial. That is way too high. Since that polynomial would by self-reciprocal you could use the degree halving trick, but degree 12 is still way too high. Sorry - you can make use of only one algebraic factor here.

If ECM could find a factor up to, say, 35 digits, you'd have an easy MPQS number.

Note: the "376^70-1" on the first comment line has the minus wrong, that should be a plus. To be fixed.

Alex

[trilliwig]

Originally Posted by smh

For phi(53,x) the poly's look better (more rels/sec).

I just tried Phi(140,376):

(140 376 (716819461) (C 115))

n: 5670349667640533737345129029795054544400388689234852451198849403078229477068582060516180863076298052484046267440141
# 376^70-1, difficulty: 180.26, skewness: 1.00, alpha: 0.00
# cost: 2.38863e+016, est. time: 11.37 GHz days (not accurate yet!)
skew: 1.000
c5: 1
c0: 1
Y1: -1
Y0: 1128833343118249207414947823407333376
m: 1128833343118249207414947823407333376

Difficulty 180 seems a bit high for a number just over 120 digits

Note that X⁵ +/- 1 is a factorizable polynomial and so cannot be used for NFS. GGNFS at least will fail in factorbase generation if this input is given. I don't know what the CWI/Franke tools will do.

--
Sam

[schickel]

Originally Posted by akruppa

I made a binary for Pentium 3 for Windows. Speed is not important for this program so architecture specific optimisation is not necessary.

Alex

Edit: I found that after stripping symbols, the binary is small enough to attach instead of linking.

Alex,
Can you recompile phi.c to take its input from a text file rather than the command line? I want to generate some polys on a Win98 system, but the numbers are too long to input because of limited line length, and it won't let me redirect the input from a file.

Frank

[akruppa]

Will a fix that allows reading the number from stdin work for you?

Alex

[akruppa]

In case it does, try this patch. Unfortunately I can't build Windows executables while at work, but maybe someone with Windows and MinGW can do it? Otherwise, I could do it over the weekend.

Alex

[schickel]

Originally Posted by akruppa

In case it does, try this patch. Unfortunately I can't build Windows executables while at work, but maybe someone with Windows and MinGW can do it? Otherwise, I could do it over the weekend.

Alex

That should work, and over the weekend is fine. I kept trying to use phi to set up SNFS runs for some cyclotomic numbers I was ECMing and couldn't figure out why it kept telling me N didn't divide the x^n-1 I was giving it. I finally noticed last night that the whole number wasn't pasting into the DOSbox.....

[akruppa]

It's at http://home.in.tum.de/~kruppa/phi.0.1.2.1.zip

Alex

Edit: And now the file is even readable!

[schickel]

Originally Posted by akruppa

It's at http://home.in.tum.de/~kruppa/phi.0.1.2.1.zip

Alex

Edit: And now the file is even readable!

Thanks! I'll give it a try when I get a free machine.

[Greenbank]

What about a script for Homogeneous Cunningham numbers (a^n +/- b^n) (i.e., takes a, b, n, known factors) and spits out an SNFS poly file?

I'm going to try and knock up my own based but someone else might have already done it...