Fix backward compatibility with PyCrypto 2.1 through 2.5:

- Replaced things like (1 << bits) with (1L << bits). See PEP 237:
    - In Python < 2.4, (1<<31) evaluates as -2147483648
    - In Python >= 2.4, it becomes 2147483648L

- Replaced things like (bits/2) with the equivalent (bits>>1).  This makes
  PyCrypto work when floating-point division is enabled (e.g. in Python 2.6
  with -Qnew)

- In Python < 2.2, expressions like 2**1279, 1007119*2014237, and
  3153640933 raise OverflowError.  Replaced them with it with 2L**1279,
  1007119L*2014237L, and 3153640933, respectively.

- The "//" and "//=" integer division operators are a syntax error in Python
  2.1 and below.  Replaced things like (m //= 2) with the equivalent
  (m >>= 1).

- Where integer division can't be replaced by bit shifting, replace (a/b) with
  (divmod(a, b)[0]).

- math.log takes exactly 1 argument in Python < 2.3, so replaced things like
  "-math.log(false_positive_prob, 4)" with
  "-math.log(false_positive_prob)/math.log(4)".

1 files changed, 10 insertions, 9 deletions

diff --git a/lib/Crypto/Util/number.py b/lib/Crypto/Util/number.py
index 3ae7ead..e4af717 100644
--- a/lib/Crypto/Util/number.py
+++ b/lib/Crypto/Util/number.py
@@ -176,7 +176,7 @@ def _rabinMillerTest(n, rounds, randfunc=None):
     m = n_1
     while (m & 1) == 0:
         b += 1
-        m //= 2
+        m >>= 1
 
     tested = []
     # we need to do at most n-2 rounds.
@@ -238,17 +238,17 @@ def getStrongPrime(N, e=0, false_positive_prob=1e-6, randfunc=None):
     if (N < 512) or ((N % 128) != 0):
         raise ValueError ("bits must be multiple of 128 and > 512")
 
-    rabin_miller_rounds = int(math.ceil(-math.log(false_positive_prob, 4)))
+    rabin_miller_rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))
 
     # calculate range for X
     #   lower_bound = sqrt(2) * 2^{511 + 128*x}
     #   upper_bound = 2^{512 + 128*x} - 1
-    x = (N - 512) // 128;
+    x = (N - 512) >> 7;
     # We need to approximate the sqrt(2) in the lower_bound by an integer
     # expression because floating point math overflows with these numbers
-    lower_bound = (14142135623730950489 * (2 ** (511 + 128*x)) /
-                   10000000000000000000)
-    upper_bound = (1 << (512 + 128*x)) - 1
+    lower_bound = divmod(14142135623730950489L * (2L ** (511 + 128*x)),
+                         10000000000000000000L)[0]
+    upper_bound = (1L << (512 + 128*x)) - 1
     # Randomly choose X in calculated range
     X = getRandomRange (lower_bound, upper_bound, randfunc)
 
@@ -268,7 +268,8 @@ def getStrongPrime(N, e=0, false_positive_prob=1e-6, randfunc=None):
 
         # look for suitable p[i] starting at y
         result = 0
-        for j, composite in enumerate (field):
+        for j in range(len(field)):
+            composite = field[j]
             # look for next canidate
             if composite:
                 continue
@@ -317,7 +318,7 @@ def getStrongPrime(N, e=0, false_positive_prob=1e-6, randfunc=None):
         X += increment
 		# abort when X has more bits than requested
 		# TODO: maybe we shouldn't abort but rather start over.
-        if X >= 1 << N:
+        if X >= 1L << N:
             raise RuntimeError ("Couln't find prime in field. "
                                 "Developer: Increase field_size")
     return X
@@ -345,7 +346,7 @@ def isPrime(N, false_positive_prob=1e-6, randfunc=None):
         if N % p == 0:
             return 0
 
-    rounds = int(math.ceil(-math.log(false_positive_prob, 4)))
+    rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))
     return _rabinMillerTest(N, rounds, randfunc)