Large prime tester

[Thisisnotanid]

Hi everyone! I've built prime testers and prime listers before, but they only work sufficiently fast for values <= 1e6. I was thinking about all the prime tester projects they have going on, how do they test very large numbers for primality? I'm talking numbers on the order 1e12, 1e13, or perhaps even larger (I don't know the currently feasible upper limit). Are there special numerical methods, algorithms, or tests to check large numbers? If so, please share. I'm very interested in how this works. Thanks! To get started, I'll list my own prime lister (I don't know if something similar's been done before, so forgive me if it's treading on intellectual property):

n = int(raw_input("Num: ")) 
s = range(3, n+1, 2) 

i = 1 

a = len(s) - 1

for l in xrange(0, a + 1): 
	a1 = i
	j = (l + (s[l]*i))
	while (j <= a) and s[l] != 0: 
		s[j] = 0
		i += 1 
		j = (l + (s[l]*i)) 
	i = a1 + 1

s = list(set(s))
s.sort()
s.remove(0)
s = [2] + s
print s

[TrustyTony]

Read this http://www.daniweb.com/forums/post319401.html#post319401 especially the response with pseudo-prime test.

[Thisisnotanid]

Read this http://www.daniweb.com/forums/post319401.html#post319401 especially the response with pseudo-prime test.

Anything with a bit more certainty? I know of the first solution, and the second is probabilistic. Thanks for the link though!

[slate]

More certain in what sense?
You can raise the certainty to a level that is higher than hardware error...
If you mean the mean the correctness of the implementation, than you can do testing on prime lists. Or try to proof the code, good luck with that:)

If you want something more serious you have to implement it in C/C++ anyway.

[Thisisnotanid]

More certain in what sense?
You can raise the certainty to a level that is higher than hardware error...
If you mean the mean the correctness of the implementation, than you can do testing on prime lists. Or try to proof the code, good luck with that:)

If you want something more serious you have to implement it in C/C++ anyway.

Can you explain a little more? When you say I can raise the certainty higher than hardware error, what is the theory behind that? I remember reading somewhere, perhaps incorrectly, that proving the correctness of code is near to impossible. Are you implying the implementation of the algorithm might need verification or the algorithm itself? I believe the latter lends itself to a rather trivial "proof." Finally, what advantages does C++ offer that provide for a more "serious" implementation? Thanks!

[vegaseat]

C (or its OOP cousin C++) is a compiled language and will be faster than an interpreted language like Python.

[Thisisnotanid]

Takes too long for 73465414651314146513116546432131 :/ In fact, it gives a memory error (for my comp. anyway).

[Thisisnotanid]

Though, Mathematica tells me it isn't a prime! :) And rather quickly at that. Any ideas how they might do it (as long as it's legal to discuss it of course)?

[vegaseat]

Mathematica may use a Miller Rabin type algorithm ...

def miller_rabin_isprime(a, i, n):
    """
    Miller-Rabin primality test
    returns a 1 if n is a prime
    usually i = n - 1
    """
    if i == 0:
        return 1
    x = miller_rabin_isprime(a, i // 2, n)
    if x == 0:
        return 0
    y = (x * x) % n
    if ((y == 1) and (x != 1) and (x != (n - 1))):
        return 0
    if (i % 2) != 0:
        y = (a * y) % n
    return y

print('-'*50)

n = 73465414651314146513116546432131
i = n - 1
p = miller_rabin_isprime(2, i, n)
if p == 1:
    print n, "is a prime"
else:
    print n, "is not a prime"

print('-'*50)

n = 73465414651314146513116546432133
i = n - 1
p = miller_rabin_isprime(2, i, n)
if p == 1:
    print n, "is a prime"
else:
    print n, "is not a prime"

print('-'*50)

'''result -->
--------------------------------------------------
73465414651314146513116546432131 is not a prime
--------------------------------------------------
73465414651314146513116546432133 is a prime
--------------------------------------------------
'''

[Thisisnotanid]

Mathematica may use a Miller Rabin type algorithm ...

def miller_rabin_isprime(a, i, n):
    """
    Miller-Rabin primality test
    returns a 1 if n is a prime
    usually i = n - 1
    """
    if i == 0:
        return 1
    x = miller_rabin_isprime(a, i // 2, n)
    if x == 0:
        return 0
    y = (x * x) % n
    if ((y == 1) and (x != 1) and (x != (n - 1))):
        return 0
    if (i % 2) != 0:
        y = (a * y) % n
    return y

print('-'*50)

n = 73465414651314146513116546432131
i = n - 1
p = miller_rabin_isprime(2, i, n)
if p == 1:
    print n, "is a prime"
else:
    print n, "is not a prime"

print('-'*50)

n = 73465414651314146513116546432133
i = n - 1
p = miller_rabin_isprime(2, i, n)
if p == 1:
    print n, "is a prime"
else:
    print n, "is not a prime"

print('-'*50)

'''result -->
--------------------------------------------------
73465414651314146513116546432131 is not a prime
--------------------------------------------------
73465414651314146513116546432133 is a prime
--------------------------------------------------
'''

Wow, thanks for writing a program! It runs very fast on my computer! I just have to get to reading the theory behind the test now. :)