20121211, 11:17  #1 
Nov 2012
Bonn University
8_{16} Posts 
Mihailescu's CIDE
We have confirmed the primality of the Leyland numbers (5596 digits) and (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.unibonn.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 20121211 at 11:25 Reason: Trying to fix URL 
20121211, 11:55  #2 
"Åke Tilander"
Apr 2011
Sandviken, Sweden
2·283 Posts 
When I go to your webpage and try to reach the link "description of their format" it says "403  Forbidden".

20121211, 12:47  #3 
Nov 2012
Bonn University
2^{3} Posts 
403  Forbidden
The pdffile had the wrong permissions. It should be OK now.

20121211, 16:35  #4 
Nov 2012
Canada
25_{8} Posts 
Several questions.
1. Is there a factorization algorithm extant (public domain or not) that is able to factor arbitrary sized integers like ECMGMP 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 20121211 at 16:49 
20121211, 18:43  #5 
∂^{2}ω=0
Sep 2002
República de California
9,791 Posts 
@ishkibabel:
My, what a lot of technobabble acronyms ... that sounds like one of those "conference abstracts" folks have developed software to autogenerate, 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..." 
20121211, 20:40  #6  
Jun 2003
Ottawa, Canada
7·167 Posts 
Quote:
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 runtime/amount of work required to prove the same number? 

20121211, 21:46  #7 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7197_{10} Posts 
Dang, that beats the current ECPP record by a fair amount. Impressive. (Forgive my ignorance, but if we do get a CPUusage estimate for the larger test, how would that compare to the approximate ECPP time required?)

20121211, 22:18  #8  
"Åke Tilander"
Apr 2011
Sandviken, Sweden
2×283 Posts 
Quote:
Last fiddled with by aketilander on 20121211 at 22:22 

20121213, 15:04  #9  
Nov 2012
Bonn University
2^{3} Posts 
Quote:
Quote:
Very roughly speaking, run time was a few days for the 5.5knumber, and less than a year for the 30knumber. 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 30knumber). 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 AtkinMorain ECPP round. Depending on the input number, this may be hard or not so hard. For AtkinMorain 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 for finding a certificate and for verifying it, where may be chosen arbitrarily small. 

20121213, 15:14  #10  
Nov 2012
Bonn University
2^{3} Posts 
Quote:
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 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. 

20121213, 16:02  #11  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
3^{4}×5^{3} Posts 
Quote:
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 MR 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 specialpurpose 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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any CIDE Primality Test Implementations?  Stargate38  Computer Science & Computational Number Theory  4  20141102 19:25 