How to speed up a python program which verifies prime numbers?

Question

I wrote this simple python 3.7 code for verifying prime numbers however I'm seeing bottlenecks with numbers over 10 digits long. I know that's weak, but I think there is hope for this piece of code with your help.

Is it possible to speed up this program to make it run super fast?

The program states False for composites and True for prime numbers. For instance this number (1235468711) takes 16 seconds to report False which equals a composite number.

By the way (a) has to remain in that state for the code to work.

I have tried compact mapping and no speed enhancement was found.

Here is the code:

p = int(input('Enter a prime number and if True its prime: '))

def prime(*kwargs):
    for i in kwargs:
        yield i 
k = (2 * p)

a = prime((2 ** (p + 1) - 1) % k)

for i in a:
    if i == 3:
        print(i is not False, "| If True number is prime!")
    else:
        print(False, "| If False number is not prime!")

I am assuming you know that this is a [probable prime test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test), and for example, 341, will mistakenly be reported as prime? — Kent Shikama, Dec 06 '19 at 04:37
Isn’t the line `i is not False` invalid syntax? In any case, that should just be written `i`. Can you explain how you’re actually testing primality? I don’t understand your code. — AMC, Dec 06 '19 at 04:38
See https://stackoverflow.com/q/8019343/2750819 for various implementations. — Kent Shikama, Dec 06 '19 at 04:42
@Alexander, I sort of just came across this while I was messing with numbers while coding. It's sort of an off shoot of 2^n-1 with a twist as you can see 2^p+1 with -1 mod 2*p — Edward, Dec 06 '19 at 04:49
@Kent,Thanks for pointing out 341 seems to be an annoying composite! — Edward, Dec 06 '19 at 04:52
@Edward I was throw off by the insane amount of parentheses. What are they for? — AMC, Dec 06 '19 at 04:56
@Alexander, I believe it maintains the True and False statement to be correct since you can't change (a) or it will cease to function correctly, except for 341 as it is a probable prime test as stated by Kent. — Edward, Dec 06 '19 at 05:01
Does this answer your question? [How to create the most compact mapping n → isprime(n) up to a limit N?](https://stackoverflow.com/questions/1801391/how-to-create-the-most-compact-mapping-n-%e2%86%92-isprimen-up-to-a-limit-n) — Shaun Lowis, Dec 06 '19 at 05:05

norok2 · Accepted Answer · 2019-12-06T08:17:44.607

The issue with this pseudo-prime primality test is in the line:

a = prime(((2**(((((p+1)))))-1))%k)

because it needs to compute an expensive power only to take its modulus afterwards.

However, Python does provide pow(), which can compute a ** b % c more efficiently as pow(a, b, c).

In your case, this is not exactly the same formula as you have an extra -1 around. Since (a ** b - 1) % c is in general different from a ** b % c - 1, you need some extra computation to reproduce your exact same formula. For example you could make use of an extra if i.e.:

x = pow(a, b, c)
x += -1 if x > 0 else c - 1

or add an additional modulus operation:

(pow(a, b, c) - 1) % c

To give you some benchmarks, on my machine I observe a +200x speed-up with the proposed approach:

p = 123456

print(((2**(((((p+1)))))-1))%(2 * p))
# 127999
print((pow(2, p + 1, 2 * p) - 1) % (2 * p))
# 127999

%timeit ((2**(((((p+1)))))-1))%(2 * p)
# 1000 loops, best of 3: 466 µs per loop
%timeit (pow(2, p + 1, 2 * p) - 1) % (2 * p)
# 1000000 loops, best of 3: 1.75 µs per loop

Note that there are more efficient (pseudo-)primality tests around.

How to speed up a python program which verifies prime numbers?

1 Answers1