23

Using the probabilistic version of the Miller-Rabin test, I have generated a list of medium-large (200-300 digit) probable primes. But probable ain't good enough! I need to know these numbers are prime. Is there a library -- preferably wrapped or wrappable in Python -- that implements one of the more efficient primality proving algorithms?

Alternatively, does anyone know where I can find a clear, detailed, and complete description of ECPP (or a similarly fast algorithm) that does not assume a great deal of prior knowledge?

Update: I've found a Java implementation of another test, APRT-CLE, that conclusively proves primality. It verified a 291-digit prime candidate in under 10 minutes on an atom processor. Still hoping for something faster, but this seems like a promising start.

senderle
  • 145,869
  • 36
  • 209
  • 233
  • Which descriptions of ECPP have you read that are not clear, detailed, or complete or assume too much prior knowledge? We have no idea what your standard for "prior knowledge" could possibly be. Please provide some background on what you've tried so far. – S.Lott Jan 20 '11 at 20:29
  • 1
    I see you want a python library, but have you considered checking out the Java method http://download.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html#isProbablePrime(int)? I think they also implement the Miller-Rabin algorithm, and from my personal experience for up to 500 digit numbers it's quite precise. – Ilya Saunkin Jan 20 '11 at 20:34
  • Actually, I've already got the Miller-Rabin algorithm implemented in python -- easy peasy, and surprisingly fast. But I want just a bit more certainty. (Or infinitely more, depending on how you look at it.) – senderle Jan 20 '11 at 20:41
  • 1
    I don't know for you, but my google query 'elliptic curve python implementation' returned like a million results. Including this recipe http://code.activestate.com/recipes/577544-elliptic-curve-prime-factorisation/ – Ilya Saunkin Jan 20 '11 at 20:42
  • Yes lots of results for factorization. But I don't want to factorize anything... – senderle Jan 20 '11 at 20:49
  • "some gaps in it that I can't fill." I wonder what those are? I wonder how I could find out what gaps you can't fill? Any hints? – S.Lott Jan 20 '11 at 22:14
  • 1
    @S.Lott -- I'm not sure what you're looking for. I don't know anything about elliptic curves. If I have to learn about elliptic curves to do this then I will; but stackoverflow cannot help me with that problem. However, if I can find a sufficiently detailed description of the algorithm (i.e. at the level of pseudocode) then I won't need to learn all about elliptic curves to implement it. Stackoverflow might be able to help me with that problem. – senderle Jan 20 '11 at 23:02
  • @senderle: What **specific** gaps do **you** have? You must precisely state the things you do not understand. We cannot guess at your gaps. We cannot possibly understand what thing you don't understand. Please **update** the question listing -- specifically -- the specific things you don't understand. Please be **specific** or we can't help. – S.Lott Jan 21 '11 at 02:33
  • 1
    This completely sidesteps your question, but many algorithms that need large primes (such as asymmetric encryption) fail if a probably-prime number is not prime. It might be more efficient to check the result of the algorithm (ie with a checksum in case of encryption) than making sure you have a prime. – Jochen Ritzel Jan 21 '11 at 02:46
  • @Jochen Ritzel: +1; although it doesn't help me directly in this instance, I am very glad to know that; thanks! – senderle Jan 21 '11 at 03:22
  • 1
    @S.Lott: My **specific** need is an implementation of a primality test that can handle large numbers, and that can be called from a python program. If you can't think of a way to help me towards that goal, fine; others seem to be doing ok. – senderle Jan 21 '11 at 03:39
  • @senderle: So, you can't update the question to explain "there are some gaps in it that I can't fill". Is that your claim? Interesting point. I understand, now. – S.Lott Jan 21 '11 at 10:51
  • 4
    @Jochen: Good idea, but I can't believe that the algorithms you mention will *always* fail for non-primes -- since if they did, they would be very efficient primality tests! :) IOW, I think at best these give you another probable-prime test a la Miller-Rabin. – j_random_hacker Jan 26 '11 at 04:36

2 Answers2

9

As an algorithm that gives a reliable polynomial primality test, consider AKS. There is an older SO article referencing implementations and presentations of the algorithm.

Community
  • 1
  • 1
Martin v. Löwis
  • 124,830
  • 17
  • 198
  • 235
  • Interesting, I'll take a look at that. My understanding is that it is not the fastest test, but perhaps it's fast enough for numbers in my size range. Thanks! – senderle Jan 20 '11 at 21:09
  • @senderle: it's also my understanding that this is the only test that is fully reliable, in the sense that it is not an approximation and that it doesn't rely on unproven-but-widely-believed assumptions (such as the Riemann hypothesis). – Martin v. Löwis Jan 21 '11 at 00:12
  • @Martin v. Löwis: Not to be argumentative, but [wikipedia appears to disagree](http://en.wikipedia.org/wiki/AKS_primality_test): "ECPP and APR conclusively prove or disprove that a given number is prime, but are not known to have polynomial time bounds for all inputs." Still, wikipedia has been known to be wrong. – senderle Jan 21 '11 at 00:28
  • @senderle: ah, ok - I should have put "polynomial" into my statement on uniqueness. There are, of course, many more conclusive tests (including the naive one), but they may not be (or are known not to be) polynomial. – Martin v. Löwis Jan 21 '11 at 01:03
  • @Martin v. Löwis: I understand now -- yes, what I meant in my first comment was that I gather it's faster than AKS in most cases, though not provably for all. Seems like we're on the same page then. – senderle Jan 21 '11 at 01:32
  • Accepted -- This will be useful as I explore ways to create my own implementation of a primality test. In the meanwhile, see below for the answer I have found. – senderle Jan 22 '11 at 22:10
7

I've found that the Pari/GP library and language use APR-CL to prove primality, which is actually the preferred algorithm for numbers in this size range, as it turns out. GP proves a 291-digit candidate prime in under 20 seconds on an atom processor, which is sufficient for my needs, and it comes with a c library that I can access using ctypes.

import ctypes

def pari_isprime(self, n):
    try: pari = ctypes.cdll.LoadLibrary("libpari.so")
    except OSError:
        print "pari_isprime: couldn't load libpari!"
        exit()
    int(n)
    pari.pari_init(4000000, 2)
    ret = bool(pari.isprime(pari.gp_read_str(str(n))))
    pari.pari_close()
    return ret

I could also use the instant module. Here's a simple c function that runs a string through pari's parser and returns the result as a string: 

from instant import inline

runpari_code = """
PyObject* runpari(PyObject *args) {
    pari_init(40000000, 2);
    char *pari_code;
    char *outstr;

    if (!PyArg_Parse(args, "s", &pari_code)) { return NULL; } // instant uses old-style args; for a module, use PyArg_ParseTuple
    outstr = GENtostr(gp_read_str(pari_code));
    pari_close();
    return Py_BuildValue("s", outstr);
}
"""
runpari = inline(runpari_code, system_headers=['pari/pari.h'], libraries=['pari'])

The above can also be used as the basis of a proper CPython extension.

senderle
  • 145,869
  • 36
  • 209
  • 233