Large small factor

[Kosmaj]

Alex
Thanks for an insightfull post above! I'm new to the factoring field but I've been using ecm for almost two months now trying (until now in vain) to prove primality of some general rep-units by factoring cyclotomic cofactors of N-1. I have several cofactors with 140-150 digits I'd like to apply SNFS to. Can you kindly comment on the following cases.

(1) Phi(192) is a cofactor of x^96+1. It's easy to select a poly for x^96+1 but the power is too high. For example, consider Phi(192,109), the first number not completely factored, 109^96 has 196 digits while we want to factor a c116. Then we better consider Phi(192)=x^64-x^32+1 (?) But how to select a poly now? x^4-x^2+1 is an obvious possibility but is power 4 enough? (Phi(192,109) has 131 digits, while my x is a bit larger.)

(2) Phi(300) is a cofactor of x^150+1. Again 150 is too high, while
Phi(300)=x^80 + x^70 - x^50 - x^40 - x^30 + x^10 + 1
Can we use x^8 + x^7 - x^5 - x^4 - x^3 + x + 1 ??

Thanks in advance.

[Kosmaj]

I did some more tweaking on Phi(192,a)=a^64-a^32+1 and come up with the following two poly's.

(1) x^5 - a^7*x^2 + a
Multiplying by a, and setting x=a^13.

(2) a^4*x^6 - a^2*x^3 + 1
by setting x=a^10.

Is this correct? (1) looks better (?) but when a=109, a^7 has 15 digits...

[akruppa]

CedricVonck: The math really isn't that tough. Start with the easy cases, for example a^59-1. You can make polynomials of degree 4, 5 or 6 very easily for this one: just multiply by a. You get a^60-a which you can express as x^4-a with root M=a^15, as x^5-a with root a^12, or as x^6-a with root a^10.

Degree 5 is a good overall choice for the smaller remaining numbers. Thus your polynomials will be x^5-a for the algebraic side, x-a^12 for the rational side, with common root M=a^12.

These numbers will give you an opportunity to get familiar with the programs. Later you can try more fancy polynomials.

Alex

[akruppa]

Kosmaj: the coefficient a^7 is far too large.

For Phi_192(a): 192=2^6*3, so you have the factor 3 in the exponent.
You can write (a^96+1)/(a^32+1) = a^64 - a^32 + 1 and make a degree 4 poly
x^4-x^2+1 with root a^16.

Or, if your input number is larger than, say 10^160, use a sextic:
multiply by a^2: a^66 - a^34 + a^2, rewrite as a^66 - a * a^33 + a^2 so you get the sextic x^6 - a*x^3 + a^2 with root a^11.

For Phi_300(a), you have (a^150+1) which has the algebraic factors (a^50+1) and (a^30+1). Both also include the factor (a^10+1), which we must divide out only once, i.e.

? (a^150+1)/(a^50+1)/(a^30+1)*(a^10+1)
%9 = a^80 + a^70 - a^50 - a^40 - a^30 + a^10 + 1

This is an obvious degree 8 poly in a^10. Degree 8 is too high, so use the degree halving trick: set up a quartic as

f(x)=b_4*x^4 + b_3*x^3 + b_2*x^2 + b_1*x + b_0

and solve for the coefficients by equating

f(a+1/a)*a^4 - (a^8 + a^7 - a^5 - a^4 - a^3 + a + 1) = 0

This gives you degree 4 which isn't great for large numbers, but dividing out the relatively large algebraic factors (a^50+1) and (a^30+1) makes it worthwhile.

Alex

[xilman]

Originally Posted by R.D. Silverman

Indeed. It will also require only 64 bit machines because 32 bit machines
do not have enough address space. Nor are there many machines with > 4G
of real memory.


And I don't think current implementations
allow larger than 32 bit primes in the factor base, nor have the extended
128-bit integer routines that would be required.

Doing (say) R311 or M1061 with SNFS would be a massive, massive effort
for the sieving, and I doubt whether the capability exists anywhere for
solving the matrix. I estimate (very roughly) a minimum of 500 million rows
would be in the matrix (for SNFS; GNFS would be much bigger).
RSA-200 had 64 million rows.

While I agree that kilobit SNFS won't be easy, I believe your estimates are a little too gloomy.

Some of your earlier estimates of the resources needed to perform particular computations have also been too gloomy. I won't quote them here, but can easily dig them out of the archives if required.

For a start, although I believe that 64-bit machines will be used extensively in a kilobit SNFS factorization, I believe that's because they are becoming common-place and not because they are absolutely necessary. I believe that 32-bit systems will also play a valuable role in the first kilobit SNFS. I do not believe that >4G physical memory will be required for the sievers (though almost certainly for the subsequent stages, but not necessarily per node in a cluster). It is virtually certain that a >31-bit file system will be required for post-sieving processing.

I believe your comment about >32-bit primes in the factor base is correct. Large primes > 2^32 bits have been used for years, and on 32-bit machines too.

I believe your estimated matrix size is substantially too large. My estimate is that it will be somewhere between 30M and 100M square with a reasonable density of around 50 - 100 set bits per row or column. There are a number of systems around that can solve such a matrix, as we have already seen.

I've observed that the Franke, Kleinjung et. al. team very frequently produce matrices which are much harder (for a given size of integer factored) than do other teams such as CWI, NFSNET, Dodson&Lenstra, and so on. I don't know why they do but suspect that if they spent more time sieving they would make the LA much easier. Note that the RSA-200 effort spent around 30% of the time in the LA. I know that asymptotically one should spend 50%, but RSA-200 is still asymptotically quite small (to abuse the language ) and current technology still makes it much easier to find sievers than LA engines.

As for time scale, I would not be surprised if a kilobit SNFS is begun this year. I will be surprised if it hasn't been started before the end of next year.


Paul

[smh]

Originally Posted by 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.

Thanks for this extensive reply (and examples in following posts) Alex. (a) and (b) are the easy ones, i've been doing this all the time with different types of numbers. I'll take a look at the others next week when things should settle down on my side.

Thanks again,
Sander

[Kosmaj]

Alex thank you for your help with polynomials. I decided to try Phi(192,113), a 132-digit number with only known factor being 193, using x^4-x^2+1. But my first attempt using precompiled binaries, ver. 0.72.2 from the ggnsf group failed. On Pentium-M, gnfs-lasieve4I12e prints out "xmalloc: m" and exits, while sieve says it cannot determine sieve type and exits too I'll try on Athlon later. For the beginning can you, or somebody in the know just tell me do I have to run makefb before, or after the sieving. Actually makefb runs OK, it can recognize the 132-digit input number and it creates the .fb file all right. And roughly how long will it take to process the above number (on any platform)?

[smh]

But my first attempt using precompiled binaries, ver. 0.72.2 from the ggnsf group failed. On Pentium-M, gnfs-lasieve4I12e prints out "xmalloc: m" and exits, while sieve says it cannot determine sieve type and exits too

You should really try to compile a newer version youreself. There were lots of changes/improvements since 0.72.2

The old script required one of the following lines in the poly file

type: gnfs

or

type: snfs

This should solve the sieve type error

[Kosmaj]

smh, thanks for your help. I already had "type: snfs" in my file. By inspecting the source code I found that the type have to be selected as either "classical" or "lattice". But I gave up the idea to use sieve because I12 eventually worked both on my Pentium-M laptop (xmalloc error indicated insufficient memory, most likely I had to many applications opened at the same time) and on my home Athlon-2000 dualie. And I was able to successfully factor one example from ggnfs distribution, a c-98 of 7^122-11 manually, without the pearl script, by running I12, makefb, procrels and other precompiled binaries (ver. 0.72.2/P4 and 0.72.12/Athlon). I used the suggested rlim=300k, alim=q0=350k and setting qintsize=110k was enough.

I'm now sieving a c-130 of Phi(192,113)/193 on 2 cpu's using x^4-x^2+1. I'll appreciate if somebody can teach me how to estimate when to stop sieving (in terms of rlim, alim, difficulty?). In this case I have rlim=800k, alim=q0=700k but sieving to 1.3M was not enough (my other parameters are lpbr/a=25, mfbr/a=44, r/alambda=2.2). I'm now continuing to 2.5M when I'll try procrels again. I see that the script is using a kind of a trial/error approach but I prefer to work without the script since I plan to attack a larger number by sieving on several machines not on the same LAN. Later I'll try to compile one of the latest versions (0.77.0 ?) under cygwin.

Thanks again to Alex and smh for direct help and to all the others who by starting this topic engaged me to try ggnfs by myself. I hope I'll be able to report my first useful factorization soon.

[JHansen]

Originally Posted by Kosmaj

I'm now sieving a c-130 of Phi(192,113)/193 on 2 cpu's using x^4-x^2+1. I'll appreciate if somebody can teach me how to estimate when to stop sieving (in terms of rlim, alim, difficulty?). In this case I have rlim=800k, alim=q0=700k but sieving to 1.3M was not enough (my other parameters are lpbr/a=25, mfbr/a=44, r/alambda=2.2)

There is an estimate that says you have to collect 0.8*Pi(LPA)+0.8*Pi(LPA), (which is 1.6*Pi(LP) when you use the same large prime bound on each side) so you could need 3.3M relations, but with these smaller factorizations, you sometimes need less. But you very probably won't need more than 3.3M relations.

--
Cheers,
Jes

[Kosmaj]

I'm happy to announce my first factorization using ggnfs:
Phi(192,113)=193*p62*p68
p62=16370313206778185393186100748027465595594079094039301429132353
p68=78959808296114678472657834173218307251324259680597277398790058463489

Sieving in the 700k-3.1M required about 15hrs cpu time (12hrs on Athlon-2000 and 3hrs on 1.7GHz Pentium-M). Several runs of procrels required about 40 minutes, the last one took almost half an hour and announced that
> There are 1631531 large primes versus 1744289 relations.
matsolve required about 55 minutes on Athlon, the matrix was
> Matrix pruned to 116355 x 117020 with weight 18799396
Two runs of sqrt required 100 sec each.

Altogether it was a very nice excercise and I'd like to thank again everybody for their help. Next, I'm getting ready to attack c-148 of a 171-digit cyclotomic number.