Viewing file:  number.py (7.57 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
#
# number.py : Number-theoretic functions
#
# Part of the Python Cryptography Toolkit
#
# Written by Andrew M. Kuchling, Barry A. Warsaw, and others
#
# ===================================================================
# The contents of this file are dedicated to the public domain. To
# the extent that dedication to the public domain is not available,
# everyone is granted a worldwide, perpetual, royalty-free,
# non-exclusive license to exercise all rights associated with the
# contents of this file for any purpose whatsoever.
# No rights are reserved.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
# ===================================================================
#
__revision__ = "$Id$"
bignum = long
try:
from Crypto.PublicKey import _fastmath
except ImportError:
_fastmath = None
# New functions
from _number_new import *
# Commented out and replaced with faster versions below
## def long2str(n):
## s=''
## while n>0:
## s=chr(n & 255)+s
## n=n>>8
## return s
## import types
## def str2long(s):
## if type(s)!=types.StringType: return s # Integers will be left alone
## return reduce(lambda x,y : x*256+ord(y), s, 0L)
def size (N):
"""size(N:long) : int
Returns the size of the number N in bits.
"""
bits, power = 0,1L
while N >= power:
bits += 1
power = power << 1
return bits
def getRandomNumber(N, randfunc=None):
"""getRandomNumber(N:int, randfunc:callable):long
Return a random N-bit number.
If randfunc is omitted, then Random.new().read is used.
NOTE: Confusingly, this function does NOT return N random bits; It returns
a random N-bit number, i.e. a random number between 2**(N-1) and (2**N)-1.
This function is for internal use only and may be renamed or removed in
the future.
"""
if randfunc is None:
_import_Random()
randfunc = Random.new().read
S = randfunc(N/8)
odd_bits = N % 8
if odd_bits != 0:
char = ord(randfunc(1)) >> (8-odd_bits)
S = chr(char) + S
value = bytes_to_long(S)
value |= 2L ** (N-1) # Ensure high bit is set
assert size(value) >= N
return value
def getRandomRange(a, b, randfunc=None):
"""getRandomRange(a:int, b:int, randfunc:callable):long
Return a random number n so that a <= n < b.
If randfunc is omitted, then Random.new().read is used.
This function is for internal use only and may be renamed or removed in
the future.
"""
range_ = b - a - 1
bits = size(range_)
value = getRandomNumber(bits, randfunc)
while value > range_:
value = getRandomNumber(bits, randfunc)
return a + value
def GCD(x,y):
"""GCD(x:long, y:long): long
Return the GCD of x and y.
"""
x = abs(x) ; y = abs(y)
while x > 0:
x, y = y % x, x
return y
def inverse(u, v):
"""inverse(u:long, u:long):long
Return the inverse of u mod v.
"""
u3, v3 = long(u), long(v)
u1, v1 = 1L, 0L
while v3 > 0:
q=u3 / v3
u1, v1 = v1, u1 - v1*q
u3, v3 = v3, u3 - v3*q
while u1<0:
u1 = u1 + v
return u1
# Given a number of bits to generate and a random generation function,
# find a prime number of the appropriate size.
def getPrime(N, randfunc=None):
"""getPrime(N:int, randfunc:callable):long
Return a random N-bit prime number.
If randfunc is omitted, then Random.new().read is used.
"""
if randfunc is None:
_import_Random()
randfunc = Random.new().read
number=getRandomNumber(N, randfunc) | 1
while (not isPrime(number, randfunc=randfunc)):
number=number+2
return number
def isPrime(N, randfunc=None):
"""isPrime(N:long, randfunc:callable):bool
Return true if N is prime.
If randfunc is omitted, then Random.new().read is used.
"""
_import_Random()
if randfunc is None:
randfunc = Random.new().read
randint = StrongRandom(randfunc=randfunc).randint
if N == 1:
return 0
if N in sieve:
return 1
for i in sieve:
if (N % i)==0:
return 0
# Use the accelerator if available
if _fastmath is not None:
return _fastmath.isPrime(N)
# Compute the highest bit that's set in N
N1 = N - 1L
n = 1L
while (n<N):
n=n<<1L
n = n >> 1L
# Rabin-Miller test
for c in sieve[:7]:
a=long(c) ; d=1L ; t=n
while (t): # Iterate over the bits in N1
x=(d*d) % N
if x==1L and d!=1L and d!=N1:
return 0 # Square root of 1 found
if N1 & t:
d=(x*a) % N
else:
d=x
t = t >> 1L
if d!=1L:
return 0
return 1
# Small primes used for checking primality; these are all the primes
# less than 256. This should be enough to eliminate most of the odd
# numbers before needing to do a Rabin-Miller test at all.
sieve=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239, 241, 251]
# Improved conversion functions contributed by Barry Warsaw, after
# careful benchmarking
import struct
def long_to_bytes(n, blocksize=0):
"""long_to_bytes(n:long, blocksize:int) : string
Convert a long integer to a byte string.
If optional blocksize is given and greater than zero, pad the front of the
byte string with binary zeros so that the length is a multiple of
blocksize.
"""
# after much testing, this algorithm was deemed to be the fastest
s = ''
n = long(n)
pack = struct.pack
while n > 0:
s = pack('>I', n & 0xffffffffL) + s
n = n >> 32
# strip off leading zeros
for i in range(len(s)):
if s[i] != '\000':
break
else:
# only happens when n == 0
s = '\000'
i = 0
s = s[i:]
# add back some pad bytes. this could be done more efficiently w.r.t. the
# de-padding being done above, but sigh...
if blocksize > 0 and len(s) % blocksize:
s = (blocksize - len(s) % blocksize) * '\000' + s
return s
def bytes_to_long(s):
"""bytes_to_long(string) : long
Convert a byte string to a long integer.
This is (essentially) the inverse of long_to_bytes().
"""
acc = 0L
unpack = struct.unpack
length = len(s)
if length % 4:
extra = (4 - length % 4)
s = '\000' * extra + s
length = length + extra
for i in range(0, length, 4):
acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc
# For backwards compatibility...
import warnings
def long2str(n, blocksize=0):
warnings.warn("long2str() has been replaced by long_to_bytes()")
return long_to_bytes(n, blocksize)
def str2long(s):
warnings.warn("str2long() has been replaced by bytes_to_long()")
return bytes_to_long(s)
def _import_Random():
# This is called in a function instead of at the module level in order to avoid problems with recursive imports
global Random, StrongRandom
from Crypto import Random
from Crypto.Random.random import StrongRandom
|