Register FAQ Search Today's Posts Mark Forums Read

 2018-03-06, 14:16 #661 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2×33×109 Posts C374 = P37 * C338 http://factordb.com/index.php?id=1100000000438534384
 2018-03-09, 17:28 #662 RichD     Sep 2008 Kansas 22·7·112 Posts 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. Code: 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
2018-03-09, 20:17   #663
hyramgraff

Jan 2018

3×11 Posts

Quote:
 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

 2018-03-12, 02:36 #664 hyramgraff   Jan 2018 3·11 Posts Here are two more factorizations: C157 = P40 * C118 The resulting composite is now the smallest composite in the t2100 file. C195 = P37 * P159
2018-03-13, 00:14   #665
lavalamp

Oct 2007
Manchester, UK

22·3·113 Posts

Quote:
 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.

 2018-03-14, 20:50 #666 Brownfox     Dec 2017 3×23 Posts 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
2018-03-14, 21:47   #667
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts

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:

Quote:
 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:
Code:
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).

Last fiddled with by Dubslow on 2018-03-14 at 21:55

2018-03-15, 16:20   #668
hyramgraff

Jan 2018

3310 Posts

Quote:
 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.

 2018-03-15, 21:07 #669 Brownfox     Dec 2017 3×23 Posts 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
 2018-03-15, 22:14 #670 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2018-03-16, 15:04 #671 hyramgraff   Jan 2018 3310 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy GPU Computing 1 2017-05-17 20:22 Mark Rose GPU Computing 52 2016-07-02 12:11 firejuggler GPU Computing 12 2016-02-23 06:55 Elhueno Homework Help 5 2008-06-12 16:37 jchein1 Factoring 30 2005-05-30 14:43

All times are UTC. The time now is 04:18.

Wed Aug 4 04:18:43 UTC 2021 up 11 days, 22:47, 0 users, load averages: 5.29, 3.66, 3.08