mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2012-12-11, 11:17   #1
JFranke
 
JFranke's Avatar
 
Nov 2012
Bonn University

816 Posts
Default 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
JFranke is offline   Reply With Quote
Old 2012-12-11, 11:55   #2
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts
Default

When I go to your webpage and try to reach the link "description of their format" it says "403 - Forbidden".
aketilander is offline   Reply With Quote
Old 2012-12-11, 12:47   #3
JFranke
 
JFranke's Avatar
 
Nov 2012
Bonn University

23 Posts
Default 403 - Forbidden

The pdf-file had the wrong permissions. It should be OK now.
JFranke is offline   Reply With Quote
Old 2012-12-11, 16:35   #4
ishkibibble
 
Nov 2012
Canada

258 Posts
Default 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
ishkibibble is offline   Reply With Quote
Old 2012-12-11, 18:43   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

@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..."
ewmayer is offline   Reply With Quote
Old 2012-12-11, 20:40   #6
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7·167 Posts
Default

Quote:
Originally Posted by JFranke View Post
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?
Jeff Gilchrist is offline   Reply With Quote
Old 2012-12-11, 21:46   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

719710 Posts
Default

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?)
Dubslow is offline   Reply With Quote
Old 2012-12-11, 22:18   #8
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Thumbs up

Quote:
Originally Posted by aketilander View Post
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
aketilander is offline   Reply With Quote
Old 2012-12-13, 15:04   #9
JFranke
 
JFranke's Avatar
 
Nov 2012
Bonn University

23 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
(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 View Post
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 is offline   Reply With Quote
Old 2012-12-13, 15:14   #10
JFranke
 
JFranke's Avatar
 
Nov 2012
Bonn University

23 Posts
Default

Quote:
Originally Posted by aketilander View Post
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.
JFranke is offline   Reply With Quote
Old 2012-12-13, 16:02   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

34×53 Posts
Default

Quote:
Originally Posted by JFranke View Post
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
xilman is offline   Reply With Quote
Reply

Thread Tools


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

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

Tue Oct 27 03:55:09 UTC 2020 up 47 days, 1:06, 0 users, load averages: 1.75, 1.73, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.