Large small factor

[Zeta-Flux]

Jes,

Thanks. I think I'll try the cygwin thing.

smh,

When I'm installing Cygwin, and I'm making sure I have those packages you listed, I click on the little "skip" button to the left of the name (for example gmp) and it has two versions. I assume I take the first version. Also, it brings up two boxes (under the categories "Bin?" and "Scr?"). The box under "Bin?" is clicked. Do I need to click the "Src?" box? Or just leave it empty? Or does it not matter at all?

Thanks,
Pace

[smh]

Originally Posted by Zeta-Flux

Jes,

Thanks. I think I'll try the cygwin thing.

smh,

When I'm installing Cygwin, and I'm making sure I have those packages you listed, I click on the little "skip" button to the left of the name (for example gmp) and it has two versions. I assume I take the first version. Also, it brings up two boxes (under the categories "Bin?" and "Scr?"). The box under "Bin?" is clicked. Do I need to click the "Src?" box? Or just leave it empty? Or does it not matter at all?

Thanks,
Pace

I choose the latest version (the one with the highest number). You don't need the source for running GGNFS

[smh]

Originally Posted by akruppa

The Factorizations of Cyclotomic Numbers page by Hisanori Mishima (http://www.asahi-net.or.jp/%7EKC2H-MSM/cn/index.htm) has lots of SNFS candidates, including easier ones that'd be excellent for learning the ways of SNFS.

Alex

Can you (or anyone) give an example or two on how to create the poly? I tried a while ago but had to give up.

[smh]

I think the smallest composites can be found here. There should be composites with ~100 digits, which take maybe a day with ggnfs.

If you choose numbers < 100 digits the script uses polyselect instead of Kleinjung's poly select tool. Even though the latter doesn't produce deg 4 poly's (like polyselect does for numbers < 100 if ran with the script and default parameters), i think you still better of using this tool.

[tcadigan]

be aware that if you are doing GNFS, composites up to 120 digits are doable, while not as fast as SNFS they do get done in a few weeks on a single computer. but make sure that isn't possible to do SNFS on it or a LOT of time will go to waste. One other word of caution if doing GNFS on numbers larger then 120 be ready for a ton of failures and work-arounds, and even then sometimes it just does NOT work, but they can be done! scour the yahoo group messages for proof. best of luck all!

[akruppa]

For cyclotomic numbers, there are four standard operations you can perform on the number (that I know of, that is):

(a) Multiplying by a constant, (b) increasing or decreasing a power, (c) dividing out algebraic factors, (d) the degree halving trick for symmetric polynomials.

(a) Suppose you want to factor a number of the form a^59-1 for a given "a" with a quintic. You can multiply by a and get a^60-a, which you can express as x^5-a with root m=a^12. For example, the smallest a^59-1 number not completly factored is 208^59-1, the polynomials would be x^5-208 and x-6557827967253220516257857536.

(b) If you want to factor a^61-1, you can rewrite the power as a*a^60 and get a*a^60-1, or a*x^5-1, again with root m=a^12. Thus, your polynomials are 208*x^5-1 and x-6557827967253220516257857536.

You can use both methods to get the exponent a multiple of the degree you want to use, choose the one that minimizes the largest coefficient of the algebraic polynomial.

You can also combine both methods if the base is composite. If you want to factor, say, 10^113-1 with a quintic, you could use 1000*x^5-1 (difficulty 113) or x^5-100 (difficulty 115) by (a) or (b) alone.
But you can also first multiply by 5^2 to get 2^113 * 5^115 - 25, then rewrite as 8*(2^110 * 5^115) - 25, or 8*x^5-25, with root 2^22*5^23 (difficulty ~114). So your polynomials are 8*x^5-25 and x-50000000000000000000000. The advantage is that the largest coefficient in the algebraic poly is now only 25 instead of 100 and you still have a low difficulty.

(c) If your exponent is divisible by 3, 5 or 7, you can divide out an algebraic factor and immediately get a polynoimal of suitable degree and small coefficients.

(a^3k-1)/(a^k-1) = a^2k + a^k + 1 which can be converted to a quadratic x^2+x+1 with root a^k. However, a quadratic has too small degree, the coefficients on the rational side would become huge. Instead, if k is odd, we write a^2*a^2(k-1) + a*a^(k-1) + 1 and can convert to a quartic in a^((k-1)/2). If you want a sextic, tweak the exponents accordingly by (b), perhaps multiplying by a power of "a" (a) to get small coefficients.

(a^5k-1)/(a^k-1) = a^4k + a^3k + a^2k + a^k + 1, which is a useable quartic in a^k.

(a^7k-1)/(a^k-1) = a^6k + a^5k + a^4k + a^3k + a^2k + a^k + 1, which is a useable sextic in a^k.

(d) For a^11k-1 and a^13k-1 you'd get degrees 10 and 12, respectively - too large. But the resulting polynomial is symmetric: (for the sake of less typing, let b=a^k)
(b^11-1)/(b-1) = b^10 + b^9 + b^8 + b^7 + b^6 + b^5 + b^4 + b^3 + b^2 + b + 1

We can multiply this by b^-5:
b^5 + b^4 + b^3 + b^2 + b + 1 + b^-1 + b^-2 + b^-3 + b^-4 + b^-5
and regroup
b^5 + b^-5 + b^4 + b^-4 + b^3 + b^-3 + b^2 + b^-2 + b + b^-1 + 1 (1)

Now we'd like to replace b^5+b^-5 by, say, (b+1/b)^5, but that gives us more terms than just b^5+b^-5 by the binomial theorem: (b+1/b)^5 = b^5 + 5b^3 + 10b + 10b^-1 + 5b^-3 + b^-5, and we have b^5+b^-5 = (b+1/b)^5 - 5*b^3 - 10*b - 10*b^-1 - 5*b^-3

Fortunately, those extra terms are again of the form c*(b^n + b^-n) and can be lumped together with the other summands of (1):

((b+1/b)^5 - 5*b^3 - 10*b - 10*b^-1 - 5*b^-3) + b^4 + b^-4 + b^3 + b^-3 + b^2 + b^-2 + b + b^-1 + 1 =

(b+1/b)^5 + b^4 + b^-4 - 4*(b^3 + b^-3) + b^2 + b^-2 - 9*(b + b^-1) + 1

Handle the term b^4 + b^-4 the same way, etc.

In the end, you'll have a polynomial

c_5*(b+1/b)^5 + c_4*(b+1/b)^4 + c_3*(b+1/b)^3 + c_2*(b+1/b)^2 + c_1*(b+1/b) + c_0. (Afaik, c_5, c_4 and c_1 are always 1)

Thus, you can use the quintic c_5*x^5 + c_4*x^4 + c_3*x^3 + c_2*x^2 + c_1*x + c_0
with root b+1/b.
The siever input file wants the root as an integer, so you have to do a modular inversion: in Pari/GP, use

Mod(b+1/b,N)

where you assigned N=(cofactor of a^11k-1), b=(value of a^k) before. The result will be printed as

Mod(M,N)

where the value in place of M is the root you want.

The linear poly will be x-(b+1/b). Using x-M directly is no good as M is about as large as N itself, so you'd have a far too large coefficient. Instead, multiply the linear poly by b:

g(x) = b*x - (b^2 + 1)

Now the coefficients b and (b^2+1) are small enough.

The method for getting the coefficients of the algebraic polynomial above shows why we should do a change of variables to b+1/b, but it is a tedious way of actually getting the coefficients. I find it easier to just set up a poly

f(x)=a_5*x^5 + a_4*x^4 + a_3*x^3 + a_2*x^2 + a_1*x + a_0,
and writing the difference

f(b+1/b)*b^5 - (b^11-1)/(b-1)

in Pari/GP (with b as a variable, not the value of a^k). This yields

(a_5 - 1)*b^10 + (a_4 - 1)*b^9 + ... + (a_4 - 1)*b + (a_5 - 1)

and we want the difference to be zero, so we can immediately set
a_5 = 1
a_4 = 1
Evaluating the difference again yields

(a_3 + 4)*b^8 + (a_2 + 3)*b^7 + ... + (a_2 + 3)*b^3 + (a_3 + 4)*b^2

so we set
a_3 = -4
a_2 = -3

Now the difference is

(a_1 - 3)*b^6 + (a_0 - 1)*b^5 + (a_1 - 3)*b^4

so we set
a_1 = 3
a_0 = 1

Now we have the polynomials

f(x) = x^5 + x^4 - 4*x^3 - 3*x^2 + 3*x + 1
g(x) = b*x - (b^2 + 1)
M = b+1/b (mod N)
with b=a^k.

Similarly for numbers of the form a^13k-1.

Enjoy!

Alex

(There probably are typos, let me know if you find any. Maybe the mods are nice and will fix them for me)

[trilliwig]

Originally Posted by Joe O

125 CPU hours on an AMD64 2.4MHz gave me the console output that I included in my post, and the following output:

Ah, ok, much becomes clear. So it looks like you ran polyselect standalone, using an example parameter file, which probably specified a number of iterations in the neighborhood of 1e9 or so. And by the end of it, polyselect had wrapped around some normally positive variables to negative.

So I would blame an overflow somewhere. You could call it a bug in the program, but I don't believe Chris Monico anticipated numbers this large would be entered. And I'm afraid this is also true of Kleinjung's pol51 tool, at least the version incorporated in GGNFS.

So in conclusion, I think you'll need a smaller number to do any useful self-education about NFS poly selection.

[Zeta-Flux]

smh,

I followed your instructions, trying to install version 0.77.0. When I type "Make" it has the following lines:

echo "#define GGNFS_VERSION \"0.77.0\"" > include/verison.h
make -C src
make[1]: Entering directory `/home/Owner/ggnfs/src'
Makefile:42: *** missing separator. Stop.
make[1]: Leaving directory `/home/Owner/ggnfs/src'
make: *** [all] Error 2

And then it quits. What am I doing wrong?

[ValerieVonck]

Originally Posted by akruppa

For cyclotomic numbers, there are four standard operations you can perform on the number (that I know of, that is):
....
ik, c_5, c_4 and c_1 are always 1)

Thus, you can use the quintic c_5*x^5 + c_4*x^4 + c_3*x^3 + c_2*x^2 + c_1*x + c_0
with root b+1/b.
The siever input file wants the root as an integer, so you have to do a modular inversion: in Pari/GP, use

Mod(b+1/b,N)
....

(There probably are typos, let me know if you find any. Maybe the mods are nice and will fix them for me)

Is it possible to make a program of some sorts that will take a number as input and do the calculations????? It should produce a polynomial file you can use....
Personally, if I such code, my head starts to ache......
Sorry for complaining that much, but I am not mathematically gifted a some of the people here..

Regards,
Cedric

[akruppa]

In fact I did, but only for degree 4 polys. I plan to extend it to other degrees sometime. But there really isn't much point in letting a program do all the parameter selection, learning about the maths involved is what integer factoring is all about, imo! I find the actual factors themselves are pretty uninteresting...

Alex

[ValerieVonck]

Originally Posted by akruppa

In fact I did, but only for degree 4 polys. I plan to extend it to other degrees sometime. But there really isn't much point in letting a program do all the parameter selection, learning about the maths involved is what integer factoring is all about, imo! I find the actual factors themselves are pretty uninteresting...

Alex

I agree, but for me this higher and more advanced math then I have seen in my life. The most complex stuff I saw was calculate Integrals + it is almost 5 - 6 years when I opened any math books..