mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-01, 13:40   #958
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

14216 Posts
Default

Quote:
Originally Posted by Pascal Ochem View Post
The run with bound \(10^{2100}\) just finished and we see the impact of the C301.
The old file has 1589 composites.
http://www.lirmm.fr/~ochem/opn/old_mwrb2100.txt
The new file has 1192 composites.
http://www.lirmm.fr/~ochem/opn/mwrb2100.txt

Don't worry if you are working on a composite that has disappeared.
It will re-appear in mwrb2200 once the run with bound \(10^{2200}\) is over, because of the composite \(\sigma(11^{330})\).
I'm down to 1124 composites remaining in my mwrb2100.

Remaining: https://cs.stanford.edu/~rpropper/mwrb2100.txt
Factors found: https://cs.stanford.edu/~rpropper/opn.txt
ryanp is offline   Reply With Quote
Old 2021-07-09, 10:49   #959
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

103 Posts
Default no OPN is smaller than 10^2200

The run for \(10^{2200}\) is now over. The program gave up on the following branches:

\(127^{192}\) / \(19^2\) \(3^6\) \(1093^2\) \(398581^{102}\) / \(7^2\) / \(13^1\)
\(127^{192}\) / \(19^2\) \(3^6\) \(1093^2\) \(398581^{108}\) / \(7^2\) / \(13^1 \)
\(61^{232}\) / \(13^2\) \(3^2\) / \(5^{520}\) / \(179^{138}\) / \(1789^1\)

The first two situations are due to a standard branching on \(3^6\), so that the considered upper bound on the abundancy is \(\frac32\) instead of \(\frac{1093}{3^6}\).
I fixed it by making an exact branching, after \(127^{192}\) / \(19^2\), on every component \(3^{2i}\), that is, even when \(2i+1\) is composite.

There is no such fix for the third situation: we already have exact branchings on \(13^2\), \(3^2\), \(1789^1\), and the abundancy \(\sigma_{-1}(p^e)\) is really close to \(\sigma_{-1}(p^\infty)=\frac{p}{p-1}\) for \(61^{232}\), \(5^{520}\), \(179^{138}\).

The abundancy in this branch is \(\frac{61}{60}\frac{183}{13^2}\frac{13}{3^2}\frac54\frac{179}{178}\frac{1790}{1789}=1.99999792324886\), which is very close to 2.
If we don't get a miraculous ECM factor and if we want to avoid a huge roadblock circumventing, we can use an old school argument:
One copy of 5 comes from \(\sigma(1789^1)\).
The other 519 copies of 5 must come from things of the form \(\sigma(p^4)\) with \(p\equiv1\pmod{5}\). Moreover, \(p\ge963121\) so that the abundancy is at most 2.
The case of \(\sigma(p^{5^k-1})\) giving \(5^k\) with \(k\ge2\) is ruled out because it is suboptimal for our argument.
Now \((963121^4)^{519}\) is greater than our bound \(10^{2200}\).
Pascal Ochem is offline   Reply With Quote
Old 2021-07-09, 11:46   #960
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

171B16 Posts
Default

It might be a good learning exercise to push each of the forbidden factors as far as possible(assuming that previous primes have been forbidden). Working out the logic to circumvent these roadblocks could be an important learning exercise. I know runtime will limit some of the primes but AFAIK some are still quite quick runs.
The logic gained from these circumventions could potentially be used to shorten the current proof.

Unless I have made a mistake 179^139-1 looks factorable with 179*(179^23)^6-1 at 314 digits which looks within reach of nfs@home(or maybe ryanp) which is currently sieving a couple of SNFS candidates with 326 digits.
henryzz is offline   Reply With Quote
Old 2021-07-11, 05:27   #961
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

26·37 Posts
Default

Quote:
Originally Posted by Pascal Ochem View Post
The first two situations are due to a standard branching on \(3^6\), ...

I fixed it by making an exact branching, after \(127^{192}\) / \(19^2\), on every component \(3^{2i}\), that is, even when \(2i+1\) is composite.
Could I persuade you to explain the rationale for choosing this fix?

In the paper for \(10^{1500}\) you used exact branches on \(3^2\) and \(3^4\), which required additional standard branches at \(3^8\), \(3^{14}\), and \(3^{24}\). You could have added an exact branch at \(3^6\) by adding standard branches as \(3^{20}\), \(3^{34}\), and \(3^{48}\). I have thought of two possible reasons that you didn't do this. First, perhaps this wouldn't have been sufficient and more complex exact branches would have been required - \(3^8\) would be particularly complicated. Second, perhaps you judged this growing list of extra standard branches to be aesthetically ugly, and chose the "every component" as more elegant and simpler to explain.
wblipp is offline   Reply With Quote
Old 2021-07-11, 13:17   #962
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

103 Posts
Default

Henry:
Luckily, the ad-hoc argument is simple (and computer-free) thanks to a Fermat prime raised to large power (5^520) and a special prime that is already specified.
It is good enough for now, we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.
Maybe more important feasible composites will show up after a closer look at the log files of this run.

William:
Assuming subtle mathematical or aesthetical motives is not a good bet this time.
The exact branch at 3^6 that you describe certainly works, but there is no suitable command option to do it, whereas I only had to replace "-X4 3" by "-Y 3".
The expected computational gain is not worth the effort of adding the "-X6" option and the risk to mess with Michael's code.
Pascal Ochem is offline   Reply With Quote
Old 2021-07-11, 23:26   #963
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2×3×227 Posts
Default

Quote:
Originally Posted by Pascal Ochem View Post
we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.
Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.

Last fiddled with by lavalamp on 2021-07-11 at 23:29
lavalamp is offline   Reply With Quote
Old 2021-07-11, 23:55   #964
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

32×383 Posts
Default

Quote:
Originally Posted by lavalamp View Post
Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.
I don't know of much ECM work except the above post by ryanp which did a blanket ECM run of the entire file. Based upon the factors found I am guessing about a t60 or t61.
RichD is offline   Reply With Quote
Old 2021-07-12, 03:34   #965
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

1010000102 Posts
Default

Quote:
Originally Posted by lavalamp View Post
Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.
For that one in particular, I've hit it with 110K curves at B1=85e7. May try B1=29e8 next.
ryanp is offline   Reply With Quote
Old 2021-09-09, 14:06   #966
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

134338 Posts
Default

Quote:
Originally Posted by Pascal Ochem View Post
Henry:
Luckily, the ad-hoc argument is simple (and computer-free) thanks to a Fermat prime raised to large power (5^520) and a special prime that is already specified.
It is good enough for now, we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.
Maybe more important feasible composites will show up after a closer look at the log files of this run.

William:
Assuming subtle mathematical or aesthetical motives is not a good bet this time.
The exact branch at 3^6 that you describe certainly works, but there is no suitable command option to do it, whereas I only had to replace "-X4 3" by "-Y 3".
The expected computational gain is not worth the effort of adding the "-X6" option and the risk to mess with Michael's code.
I have finally had time to think further on this and have a few more questions:

Am I correct in thinking that 5 being a Fermat prime made it easier to determine the optimal way of finding all the needed 5s and similar logic could be applied to other primes although less effectively(maybe \(963121^{519}\) rather than \((963121^4)^{519}\)?) Does the special prime need to always be specified as long as it is accounted for(there may be examples of it providing more than one of the prime).
If we can generalize this technique without it becoming ineffective it could reduce the tree significantly. Surely there must be a useful argument for finding the needed 232 61s. Applying this sort of argument to more than one prime at once could get complicated as a term could provide both needed primes. I will think on this further. It shouldn't be too difficult for a program to find a list of the 232 smallest \(p^x\) such that \(61 | \sigma(p^x)\), however, it would be necessary to also check for \(61^2 | \sigma(p^x)\) for \(\sigma(p^x)\) up to twice the size(and 61^3 etc.) which could be harder. Maybe a suboptimal(we underestimate the size) case could be proven.

You mentioned a -Y option above. The version posted at https://www.arthy.org/opn/ doesn't contain this. Are you working with a later version(if so would you be willing to share?)? Am I correct in thinking that the -X2, -X4 and -Y options are only needed for some of the primes to avoid issues but could be removed for other forbidden factors? Theoretically, the -Y could only be used for 127^192 reducing computation in the other trees where 3 appears especially 3^x.

Are we still only forbidding the factors 127,19,7,11,331,31,97,61,13,398581,1093,3,5,307,17? http://www.lirmm.fr/~ochem/opn/efficiency.txt suggests this was only sufficient up to 1735

The link to the BCR paper http://wwwmaths.anu.edu.au/~brent/pub/pub116.html is now broken. https://maths-people.anu.edu.au/~brent/pub/pub116.html seems to work.
henryzz 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 03:02.


Tue Oct 19 03:02:06 UTC 2021 up 87 days, 21:31, 0 users, load averages: 1.48, 1.63, 1.64

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.