Pascal's OPN roadblock files

[henryzz]

C374 = P37 * C338 http://factordb.com/index.php?id=1100000000438534384

[RichD]

These are the "easiest" ones in the t600 file. All are fully ECMed and ready for factMsieve or your favorite NFS suite. Be warned, they will take several weeks each on a four core system. All can use the degree halving polynomial.

SNFS-216 C161 969550980294955841 12
SNFS-221 C169 11658852700685942029849 10
SNFS-218 C176 6721393100152677634549 10
SNFS-222 C191 2959025653654433029 12
SNFS-219 C193 1943777054011345723 12
SNFS-219 C198 7560423642616328727781 10
SNFS-211 C200 1372831999148013167419 10
SNFS-214 C201 2642270235905971097617 10
SNFS-224 C205 5056496574263951471 12
SNFS-216 C212 4408320270589390433141 10
SNFS-213 C214 563120390493837601 12
SNFS-222 C219 16952580673293897376649 10

[hyramgraff]

Originally Posted by lavalamp

Getting all 65k composites to 40 digits (or even 35 digits) is a hell of an undertaking, as I'm sure you know. If it isn't too much trouble, for higher ECM levels can I suggest sorting the composites by either size or SNFS difficulty? That way the candidates that it's possible to SNFS are fully ECM'd sooner and the monsters that are out of reach of SNFS anyway can be run later.

I've finished running 25 digit ECM for all composites in the t2100 file and now I'm running 30 digit ECM on the ~3,500 C1XX composites.

Here are the last two full factorizations from my 25 digit work:

C856 = P26 * PRP831 http://factordb.com/index.php?id=1100000000685532388

C848 = P27 * PRP821 http://factordb.com/index.php?id=1100000000511682066

[hyramgraff]

Here are two more factorizations:

C157 = P40 * C118 The resulting composite is now the smallest composite in the t2100 file.

C195 = P37 * P159

[lavalamp]

Originally Posted by hyramgraff

C157 = P40 * C118 The resulting composite is now the smallest composite in the t2100 file.

Very strange, the number already had a 44 digit factor. You were looking for 30 digit factors, and found a 40 digit factor. Then I factored the remaining C118 into ... p37 * p82.

[Brownfox]

Sorry to break in but I've got a couple of questions. Firstly, is there a current up-to-date list of the composites that need factoring? I've had a look at the t2100 file on Pascal's site and it's dated 07/2017. The first composite in that is only 103 digits, assuming I've understood the format correctly. That would be only hours' work for GNFS, but there's no entry in factordb for it. What am I missing?

And secondly, is there an explanation for the source of some of these numbers? It's all very well being asked to factor a^2+a+1 for some large a, but in some circumstances it might be possible to use the algebraic form of a to generate a better polynomial for SNFS.

Thanks for any help
Steve

[Dubslow]

As far as I know, pascal's lists + cross referencing the FDB (+ maybe checking this thread) is the best way to get up to date information.

As for algebraic form, all OPN numbers are of the form sigma(p^(m)) ~ (p^(m+1) + 1)/(p-1) for prime p and various m. Quoting the description:

tXXXX contains composite numbers encountered when targetting the lower bound 10^XXXX.
The format is p q c where c is a composite factor of sigma(p^q).

The first line listed in t2100.txt is:

32255735115003306513692416251654907813239666644230888161178016067166921037 2 520265584590898068859754378133743032119120450966287262997866771153575366825960463761001173652178932891073

That composite, which is a cofactor of (p^(m+1)-1)/(p-1) where p is 32255735115003306513692416251654907813239666644230888161178016067166921037 and m is 2 (so the total power is 3), has been factored. Typically for OPN work, the p in question is itself some prime factor of another sigma(q^n), for some prior prime q and power n. These "chains" of iterated sigmas are how the search works, and following those chains for each base prime p is how you can construct an SNFS poly (it's not necessarily easy). This, for instance, is a typical example of such a chain (although it looks like, in that post, in the denominators, I should have written (y-1)*...*... and (x-1)*...*... rather than y*... and x*... oops).

[hyramgraff]

Originally Posted by Brownfox

Sorry to break in but I've got a couple of questions. Firstly, is there a current up-to-date list of the composites that need factoring? I've had a look at the t2100 file on Pascal's site and it's dated 07/2017. The first composite in that is only 103 digits, assuming I've understood the format correctly. That would be only hours' work for GNFS, but there's no entry in factordb for it. What am I missing?

Even though Pascal's site makes it look like the t2100 file was last updated in July, it is actually updated fairly frequently. (You can see how the file has evolved by looking at the history of it in a git repository I created: https://gitlab.com/hyramgraff/odd-perfect-ecm)

Any composites in the t2100 file that are less than 130 digits are usually factored very quickly and they will be removed when the file is updated. However, primes found when factoring other composites can become a new unfactored branch in the proof tree and will be added to the file. The p for the C103 that you mentioned is the second largest factor of (93120567780622842301313419400053^7-1) and it looks like that factorization was finished on February 16th.

That was a long-winded of saying that the t2100 file is a fairly current list of the numbers that need factoring but it's easy to think that it's out of date if you just look at the smallest numbers in the file because every time a branch in the proof tree is fully factored it can lead to new small composites being added to the t2100 file.

[Brownfox]

Thank you both. That's a lot clearer now.

It would still be useful to know the source of the base, I think.

For instance, if we want to factor N=a^2+a+1, that's not very useful as a polynomial for SNFS. However, if we know that a=b^4+b^3+b^2+b+1, we can substitute that to get a nice sextic with root b.

Probably teaching my grandmother to suck eggs.

Cheers
Steve

[Dubslow]

Often the FDB can be used (in a somewhat roundabout way) to find where a particular base came from. For instance, search for the base of our standard example, the C103 which is p^2+p+1=sigma(p^2), where p is 322555...; click on the "More information" arrow, where it tells you that p is a factor of some (ex-)C143; clicking "More information" there reveals that this C143, and thus p, is also a factor of a (ex-)C177; notice that the special form of this C177 is given in the search box; you can either use that form directly, or click "More information" and follow to the C185, which the filled-in search box tells us is "(4664607259009421338832033924593^7-1)/4664607259009421338832033924592". So we see that our p in question is in fact the largest factor of this number, which is sigma(4664607259009421338832033924593^6). You can of course repeat the process on this previous-base 4664607259009421338832033924593, to see where it came from, etc, etc as far back as you please. It's a bit tedious, but doable.

[hyramgraff]

I'm now running 35 digit ECM on the ~3,500 C1XX composites in the t2100 file. I've decided to stop posting all of the full factorizations that I find and to just post factorizations that lead to a composite with less than 130 digits. I don't have a factoring program installed but I'm hoping that someone else will be able to quickly finish the factorization.

C143 = P38 * C106 http://factordb.com/index.php?id=1100000000824425381