@@ -35,20 +35,15 @@ class NegativeExponentError(Error):
35
35
pass
36
36
37
37
38
- def modular_exp (base , exponent , modulus ):
39
- "Raise base to exponent, reducing by modulus"
40
- if exponent < 0 :
41
- raise NegativeExponentError ("Negative exponents (%d) not allowed" \
42
- % exponent )
43
- return pow (base , exponent , modulus )
44
- # result = 1L
45
- # x = exponent
46
- # b = base + 0L
47
- # while x > 0:
48
- # if x % 2 > 0: result = (result * b) % modulus
49
- # x = x // 2
50
- # b = (b * b) % modulus
51
- # return result
38
+ def modular_exp (base , exponent , modulus ): # pragma: no cover
39
+ """Raise base to exponent, reducing by modulus"""
40
+ # deprecated in 0.14
41
+ warnings .warn ("Function is unused in library code. If you use this code, "
42
+ "change to pow() builtin." , DeprecationWarning )
43
+ if exponent < 0 :
44
+ raise NegativeExponentError ("Negative exponents (%d) not allowed"
45
+ % exponent )
46
+ return pow (base , exponent , modulus )
52
47
53
48
54
49
def polynomial_reduce_mod (poly , polymod , p ):
@@ -182,14 +177,14 @@ def square_root_mod_prime(a, p):
182
177
% (a , p ))
183
178
184
179
if p % 4 == 3 :
185
- return modular_exp (a , (p + 1 ) // 4 , p )
180
+ return pow (a , (p + 1 ) // 4 , p )
186
181
187
182
if p % 8 == 5 :
188
- d = modular_exp (a , (p - 1 ) // 4 , p )
183
+ d = pow (a , (p - 1 ) // 4 , p )
189
184
if d == 1 :
190
- return modular_exp (a , (p + 3 ) // 8 , p )
185
+ return pow (a , (p + 3 ) // 8 , p )
191
186
if d == p - 1 :
192
- return (2 * a * modular_exp (4 * a , (p - 5 ) // 8 , p )) % p
187
+ return (2 * a * pow (4 * a , (p - 5 ) // 8 , p )) % p
193
188
raise RuntimeError ("Shouldn't get here." )
194
189
195
190
if PY3 :
@@ -524,11 +519,11 @@ def is_prime(n):
524
519
r = r // 2
525
520
for i in xrange (t ):
526
521
a = smallprimes [i ]
527
- y = modular_exp (a , r , n )
522
+ y = pow (a , r , n )
528
523
if y != 1 and y != n - 1 :
529
524
j = 1
530
525
while j <= s - 1 and y != n - 1 :
531
- y = modular_exp (y , 2 , n )
526
+ y = pow (y , 2 , n )
532
527
if y == 1 :
533
528
miller_rabin_test_count = i + 1
534
529
return False
0 commit comments