0

I understand that my code's complexity isn't the best, and I thought it might take 3 - 6 minutes running, but I gave it 15 minutes and it didn't stop. How do I know if it got stuck somewhere or it's just still running? and How can I improve it?

import random
import time 
def is_prime(m):
    """ probabilistic test for compositeness of m>30
    adds a trivial sieve to quickly eliminate divisibility
    by small primes. """
    if m in [2,3,5,7,11,13,17,19,23,29]:
        return True    # treats small primes separately
    for prime in [2,3,5,7,11,13,17,19,23,29]:
        if m % prime == 0:
            return False
    for i in range(0,100):
        a = random.randint(1,m-1) # a is a random integer in [1..m-1]
        if pow(a,m-1,m) != 1:
                return False
    return True


def order_safe_prime(g,p):

    """ computes the order of g modulo a safe prime, p """
    if g<1 or g>p-1:
        return str.format("g={} is out of range", g)
    elif not is_prime(p):
        return str.format("{} is not a prime", p)
    q=(p-1)//2
    if not is_prime(q):
        return str.format("q={} is not a prime", (p-1)//2)
    else:
        if g==1:
            return 1
        if g==p-1:
            return 2
        if pow(g,q,p)==1:
            return q
        if pow(g,p-1,p)==1:
            return p-1



def stats_ord_secure(p,times=10000):
    cnt1=0
    cnt2=0
    for i in range(times):
        g=random.randint(2,p-2)
        if order_safe_prime(g,p)==(p-1)/2:
            cnt1+=1
        if order_safe_prime(g,p)==(p-1):
            cnt2+=1
    return ((cnt1/times,cnt2/times))

For example running :

>>>stats_ord_secure((2**1001)+188151)

would take more than 15 minutes !

Tam211
  • 723
  • 5
  • 10
  • 27
  • please give us `is_prime` – emesday Apr 26 '14 at 14:01
  • You can use [a profiler](https://docs.python.org/2/library/profile.html) to check what’s taking the most time. However, I would guess that your `is_prime` is very expensive (because prime number tests always are). – poke Apr 26 '14 at 14:02
  • I tried omitting the is_prime and running the code, nothing improved. I'm not really familiar with profiles, what is profiling exactly ? – Tam211 Apr 26 '14 at 14:04
  • 1
    @user3369309 did you bother to read the linked question and its selected answer? – jonrsharpe Apr 26 '14 at 14:05
  • "How do I know if it got stuck somewhere or it's just still running" sounds a lot like http://en.wikipedia.org/wiki/Halting_problem – Jasper Apr 26 '14 at 14:21

1 Answers1

1

Apart from profiling, you could also simply add a print statement somewhere to see when certain code is reached. For example, in stats_ord_secure, you could put a print at the beginning of the loop to get a feeling of how long each iteration takes:

for i in range(times):
    print('loop')

Doing that, you can quickly see that a single iteration takes a few seconds. If you multiply that by times, which is 10000, you can easily see why it’s taking so long.

For a single iteration, this is what the profiler gives me:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      402    2.129    0.005    2.129    0.005 {pow}
      401    0.002    0.000    0.006    0.000 random.py:173(randrange)
        4    0.002    0.001    2.128    0.532 profile-test.py:4(is_prime)
        1    0.002    0.002    2.144    2.144 profile-test.py:1(<module>)
        1    0.002    0.002    0.004    0.004 random.py:40(<module>)
        1    0.001    0.001    0.001    0.001 {nt.urandom}
      401    0.001    0.000    0.003    0.000 random.py:242(_randbelow)
      768    0.001    0.000    0.001    0.000 {method 'getrandbits' of '_random.Random' objects}
      403    0.001    0.000    0.001    0.000 {math.log}
        1    0.001    0.001    0.001    0.001 hashlib.py:55(<module>)
      401    0.001    0.000    0.006    0.000 random.py:236(randint)
        1    0.000    0.000    2.138    2.138 profile-test.py:42(stats_ord_secure)
        1    0.000    0.000    0.000    0.000 __future__.py:48(<module>)
        2    0.000    0.000    2.138    1.069 profile-test.py:20(order_safe_prime)

As you can see, the most time is spent on pow which you call with very large numbers.

poke
  • 369,085
  • 72
  • 557
  • 602