mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2018-03-06, 14:16   #661
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×33×109 Posts
Default

C374 = P37 * C338 http://factordb.com/index.php?id=1100000000438534384
henryzz is offline   Reply With Quote
Old 2018-03-09, 17:28   #662
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

22·7·112 Posts
Default

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
RichD is offline   Reply With Quote
Old 2018-03-09, 20:17   #663
hyramgraff
 
Jan 2018

3×11 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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 is offline   Reply With Quote
Old 2018-03-12, 02:36   #664
hyramgraff
 
Jan 2018

3·11 Posts
Default

Here are two more factorizations:

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

C195 = P37 * P159
hyramgraff is offline   Reply With Quote
Old 2018-03-13, 00:14   #665
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

22·3·113 Posts
Default

Quote:
Originally Posted by hyramgraff View Post
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.
lavalamp is offline   Reply With Quote
Old 2018-03-14, 20:50   #666
Brownfox
 
Brownfox's Avatar
 
Dec 2017

3×23 Posts
Default

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
Brownfox is offline   Reply With Quote
Old 2018-03-14, 21:47   #667
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts
Default

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
Dubslow is offline   Reply With Quote
Old 2018-03-15, 16:20   #668
hyramgraff
 
Jan 2018

3310 Posts
Default

Quote:
Originally Posted by Brownfox View Post
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.
hyramgraff is offline   Reply With Quote
Old 2018-03-15, 21:07   #669
Brownfox
 
Brownfox's Avatar
 
Dec 2017

3×23 Posts
Default

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
Brownfox is offline   Reply With Quote
Old 2018-03-15, 22:14   #670
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

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.

Last fiddled with by Dubslow on 2018-03-15 at 22:14
Dubslow is offline   Reply With Quote
Old 2018-03-16, 15:04   #671
hyramgraff
 
Jan 2018

3310 Posts
Default

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
hyramgraff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Passive Pascal Xyzzy GPU Computing 1 2017-05-17 20:22
Tesla P100 — 5.4 DP TeraFLOPS — Pascal Mark Rose GPU Computing 52 2016-07-02 12:11
Nvidia Pascal, a third of DP firejuggler GPU Computing 12 2016-02-23 06:55
Calculating perfect numbers in Pascal Elhueno Homework Help 5 2008-06-12 16:37
Factorization attempt to a c163 - a new Odd Perfect Number roadblock 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.