![]() |
![]() |
#1 |
Nov 2012
Bonn University
108 Posts |
![]()
We have confirmed the primality of the Leyland numbers
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 |
![]() |
![]() |
![]() |
#2 |
"Åke Tilander"
Apr 2011
Sandviken, Sweden
10001101102 Posts |
![]()
When I go to your webpage and try to reach the link "description of their format" it says "403 - Forbidden".
![]() |
![]() |
![]() |
![]() |
#3 |
Nov 2012
Bonn University
108 Posts |
![]()
The pdf-file had the wrong permissions. It should be OK now.
|
![]() |
![]() |
![]() |
#4 |
Nov 2012
Canada
3·7 Posts |
![]()
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 |
![]() |
![]() |
![]() |
#5 |
∂2ω=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..." |
![]() |
![]() |
![]() |
#6 | |
Jun 2003
Ottawa, Canada
3·17·23 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 run-time/amount of work required to prove the same number? |
|
![]() |
![]() |
![]() |
#7 |
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88
160658 Posts |
![]()
Dang, that beats the current ECPP record by a fair amount. Impressive.
![]() |
![]() |
![]() |
![]() |
#8 | |
"Åke Tilander"
Apr 2011
Sandviken, Sweden
2×283 Posts |
![]() Quote:
Last fiddled with by aketilander on 2012-12-11 at 22:22 |
|
![]() |
![]() |
![]() |
#9 | ||
Nov 2012
Bonn University
108 Posts |
![]() Quote:
Quote:
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 |
||
![]() |
![]() |
![]() |
#10 | |
Nov 2012
Bonn University
23 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 |
|
![]() |
![]() |
![]() |
#11 | |
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2D8E16 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 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 |
|
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
Any CIDE Primality Test Implementations? | Stargate38 | Computer Science & Computational Number Theory | 4 | 2014-11-02 19:25 |