Mihailescu's CIDE

JFranke · 2012-12-11, 11:17

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

aketilander · 2012-12-11, 11:55

When I go to your webpage and try to reach the link "description of their format" it says "403 - Forbidden".

JFranke · 2012-12-11, 12:47

The pdf-file had the wrong permissions. It should be OK now.

ishkibibble · 2012-12-11, 16:35

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

ewmayer · 2012-12-11, 18:43

@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..."

Jeff Gilchrist · 2012-12-11, 20:40

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?

Dubslow · 2012-12-11, 21:46

Dang, that beats the current ECPP record by a fair amount. Impressive.

(Forgive my ignorance, but if we do get a CPU-usage estimate for the larger test, how would that compare to the approximate ECPP time required?)

aketilander · 2012-12-11, 22:18

Quote:

Originally Posted by aketilander

"description of their format"

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!

JFranke · 2012-12-13, 15:04

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.

JFranke · 2012-12-13, 15:14

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.

xilman · 2012-12-13, 16:02

Quote:

Originally Posted by JFranke

Apparently yes http://en.wikipedia.org/wiki/Leyland_number.

A rather undeserved accolade, IMO.

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

2012-12-11, 11:17	#1
JFranke Nov 2012 Bonn University 10₈ 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, 12:47	#3
JFranke Nov 2012 Bonn University 10₈ 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 3·7 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

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

2012-12-11, 11:55	#2
aketilander "Åke Tilander" Apr 2011 Sandviken, Sweden 1000110110₂ Posts	When I go to your webpage and try to reach the link "description of their format" it says "403 - Forbidden".

2012-12-11, 18:43	#5
ewmayer ∂²ω=0 Sep 2002 República de California 5×2,351 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, 21:46	#7
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 16065₈ Posts	Dang, that beats the current ECPP record by a fair amount. Impressive. (Forgive my ignorance, but if we do get a CPU-usage estimate for the larger test, how would that compare to the approximate ECPP time required?)