Edit Question - KnowledgeHub

Title Body

I was trying to implement a Miller-Rabin primality test , and was puzzled why it was taking so long (> 20 seconds) for midsize numbers (~7 digits). I eventually found the following line of code to be the source of the problem: x = a**d % n (where a , d , and n are all similar, but unequal, midsize numbers, ** is the exponentiation operator, and % is the modulo operator) I then I tried replacing it with the following: x = pow(a, d, n) and it by comparison it is almost instantaneous. For context, here is the original function: from random import randint def primalityTest(n, k): if n < 2: return False if n % 2 == 0: return False s = 0 d = n - 1 while d % 2 == 0: s += 1 d >>= 1 for i in range(k): rand = randint(2, n - 2) x = rand**d % n # offending line if x == 1 or x == n - 1: continue for r in range(s): toReturn = True x = pow(x, 2, n) if x == 1: return False if x == n - 1: toReturn = False break if toReturn: return False return True print(primalityTest(2700643,1)) An example timed calculation: from timeit import timeit a = 2505626 d = 1520321 n = 2700643 def testA(): print(a**d % n) def testB(): print(pow(a, d, n)) print("time: %(time)fs" % {"time":timeit("testA()", setup="from __main__ import testA", number=1)}) print("time: %(time)fs" % {"time":timeit("testB()", setup="from __main__ import testB", number=1)}) Output (run with PyPy 1.9.0): 2642565 time: 23.785543s 2642565 time: 0.000030s Output (

Tags (comma-separated) Cancel