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 !

Improve this question
5
  • please give us is_prime Commented Apr 26, 2014 at 14:01
  • You can use a profiler 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). Commented Apr 26, 2014 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 ? Commented Apr 26, 2014 at 14:04
  • 1
    @user3369309 did you bother to read the linked question and its selected answer? Commented Apr 26, 2014 at 14:05
  • "How do I know if it got stuck somewhere or it's just still running" sounds a lot like en.wikipedia.org/wiki/Halting_problem Commented Apr 26, 2014 at 14:21

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

what profiler you are using?
@YasarArafath If memory serves right, this would be the built-in profiler.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.