mersenneforum.org Mihailescu's CIDE
 Register FAQ Search Today's Posts Mark Forums Read

 2012-12-11, 11:17 #1 JFranke     Nov 2012 Bonn University 108 Posts Mihailescu's CIDE We have confirmed the primality of the Leyland numbers $3110^{63}+63^{3110}$ (5596 digits) and $8656^{2929}+2929^{8656}$ (30008 digits) by an implementation of a version of Mihailescu's CIDE. The certificates, together with a description of their format and a table of Gauß sums for their verification may be found under http://www.math.uni-bonn.de/people/f...est/ptest.html. Calculations were carried out using resources at the Hausdorff Center for Mathematics, the Institutefor Numerical Simulation in Bonn, and LACAL in Lausanne. J. Franke, T. Kleinjung, A. Decker, J. Ecknig, A. Großwendt Last fiddled with by JFranke on 2012-12-11 at 11:25 Reason: Trying to fix URL
 2012-12-11, 11:55 #2 aketilander     "Åke Tilander" Apr 2011 Sandviken, Sweden 10668 Posts When I go to your webpage and try to reach the link "description of their format" it says "403 - Forbidden".
 2012-12-11, 12:47 #3 JFranke     Nov 2012 Bonn University 23 Posts 403 - Forbidden The pdf-file had the wrong permissions. It should be OK now.
 2012-12-11, 16:35 #4 ishkibibble   Nov 2012 Canada 1516 Posts Several questions. 1. Is there a factorization algorithm extant (public domain or not) that is able to factor arbitrary sized integers like ECM-GMP or failing that certify that the number is prime without resorting to a secondary primality proving routine like ECPP. That is, the same algorithm is able to find arbitrary factors as fast as it would take to certify a number as prime. 2. How long would it take to prove such numbers prime using the algorithm specified (Mihailescu's CIDE) with pencil and paper (ballpark figure). 3. Rather than prove an arbitrary number prime based on the properties of the number, could using an algorithm such as PSLQ to develop a set of POS or SOP closed forms equivalent to that number be used instead. Primality may then be ascertained through analytic methods. The salient point being that certain structures in class number theory must be present such that any extension of these equivalence forms to numerical values are proven primes. Decision, search and scheduling as applied to Turing type computations can be developed as P/NP statements (as in the above 3.) relative to an arbitrary von Neumann architecture or simultaneous state bit flips of quantum computation. Godel's thesis, Matiyasevich's result and applications such as ACL2 provide insight and assistance in developing good questions with provable answers. I especially like the EQP result. Cheers, Ishki Last fiddled with by ishkibibble on 2012-12-11 at 16:49
 2012-12-11, 18:43 #5 ewmayer ∂2ω=0     Sep 2002 República de California 2×13×449 Posts @ishkibabel: My, what a lot of techno-babble acronyms ... that sounds like one of those "conference abstracts" folks have developed software to auto-generate, to check whether anyone is really reading those submissions before replying with "congratulations! Your submission has been accepted to the 2013 ITRHTRTOTYJGFW4BTRKYTKTY Memorial Conference, pending receipt of a submission fee of \$150..."
2012-12-11, 20:40   #6
Jeff Gilchrist

Jun 2003

3·17·23 Posts

Quote:
 Originally Posted by JFranke We have confirmed the primality of the Leyland numbers $3110^{63}+63^{3110}$ (5596 digits) and $8656^{2929}+2929^{8656}$ (30008 digits) by an implementation of a version of Mihailescu's CIDE. The certificates, together with a description of their format and a table of Gauß sums for their verification may be found under http://www.math.uni-bonn.de/people/f...est/ptest.html.
Nice work Jens. I guess this means we have a new largest proven prime Leyland number? (also interesting, I didn't know that Paul had his own style of number named after him)

Wow, that was a lot of work. Maybe I missed it but I didn't see any description of how much CPU power you actually used for that (just a short reference to CPU months). Can you comment on how your CIDE implementation might compare to using something like ECPP for run-time/amount of work required to prove the same number?

 2012-12-11, 21:46 #7 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-12-11, 22:18   #8
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts

Quote:
 Originally Posted by aketilander
Well if I understand the status of this (37 page) paper rightly it is not yet accepted by any peer reviewed journal, so we really have to wait and see if the mathematical community accepts this method as a primality test or if it is rejected for some reason. If I understand it rightly this is the first test ever using this specific method so I could imagine that one or two other mathematicians have something to say about it. But I surely keep my fingers crossed hoping that it will be generally accepted. Well done!

Last fiddled with by aketilander on 2012-12-11 at 22:22

2012-12-13, 15:04   #9
JFranke

Nov 2012
Bonn University

23 Posts

Quote:
 Originally Posted by Jeff Gilchrist (also interesting, I didn't know that Paul had his own style of number named after him)
Apparently yes http://en.wikipedia.org/wiki/Leyland_number.
Quote:
 Originally Posted by Jeff Gilchrist Wow, that was a lot of work. Maybe I missed it but I didn't see any description of how much CPU power you actually used for that (just a short reference to CPU months). Can you comment on how your CIDE implementation might compare to using something like ECPP for run-time/amount of work required to prove the same number?
We did not provide information about CPU months because the environment was heterogeneous. Also, programs are currently still suboptimal, so I decided not to include this information in the mail I sent to several people, and in my post in this forum.

Very roughly speaking, run time was a few days for the 5.5k-number, and less than a year for the 30k-number. I would have to dig out my logs, and get Thorsten's logs. There is still room for improvement, both of the run time and the certificate size (it currently is slightly larger than one gigabyte for the 30k-number).

The method is probably less predictable than classical ECPP since its first step is to find a Mihailescu twin, either directly or after an initial Atkin-Morain ECPP round. Depending on the input number, this may be hard or not so hard. For Atkin-Morain ECPP, you have thousands of reduction steps and the accumulated run time of these steps becomes very predictable. With only one or two steps to do, it will vary considerably.

Heuristically, the expected run time is $\log(N)^{3+\epsilon}$ for finding a certificate and $\log(N)^{2+\epsilon}$ for verifying it, where $\epsilon>0$ may be chosen arbitrarily small.

2012-12-13, 15:14   #10
JFranke

Nov 2012
Bonn University

23 Posts

Quote:
 Originally Posted by aketilander Well if I understand the status of this (37 page) paper rightly it is not yet accepted by any peer reviewed journal, so we really have to wait and see if the mathematical community accepts this method as a primality test or if it is rejected for some reason.
Absolutely. It is not published in any journal or volume of proceedings, peer reviewed or not. If I am informed correctly the same holds for the preprints of Mihailescu from which we took most of the ideas. You currently have to read it yourself and to decide whether you want to believe it.

Also, the process of verification of the certificate is very complex, and it is quite easy to forget something. For instance, the certification programs I had used last week forgot to check surjectivity of $\Xi$ in theorem 4 of our format description. I wrote a small program which tests this surjectivity before making our result public. But it is possible there still omissions in the certificate test program, and you cannot be sure until someone has written an independent test program, which is a highly complex task.

2012-12-13, 16:02   #11
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

24×13×53 Posts

Quote:
 Originally Posted by JFranke Apparently yes http://en.wikipedia.org/wiki/Leyland_number.

The story is that many years ago someone mailed me the assertion that there were only a finite (and implied small) number of primes of the form x^y+y^x where 1 < x < y. I thought it a doubtful claim and ran a small search which turned up quite a few. A significantly larger number passed at least one M-R test. When these results were put on my web site I observed that they might be good test cases for general purpose primality proving software because they appear to be reasonably common, have a simple description and do not have any known algebraic properties which can be exploited by special-purpose algorithms. Crandall and Pomerance attached my name to them in their second edition but I didn't find out about this until long after publication.

Paul

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Computer Science & Computational Number Theory 4 2014-11-02 19:25

All times are UTC. The time now is 03:23.

Tue Nov 30 03:23:20 UTC 2021 up 129 days, 21:52, 0 users, load averages: 1.06, 1.26, 1.30