home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / var / lib / python-support / python2.6 / gdata / Crypto / Util / number.pyc (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2009-04-20  |  5.4 KB  |  232 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.6)
  3.  
  4. __revision__ = '$Id: number.py,v 1.13 2003/04/04 18:21:07 akuchling Exp $'
  5. bignum = long
  6.  
  7. try:
  8.     from Crypto.PublicKey import _fastmath
  9. except ImportError:
  10.     _fastmath = None
  11.  
  12.  
  13. def size(N):
  14.     '''size(N:long) : int
  15.     Returns the size of the number N in bits.
  16.     '''
  17.     (bits, power) = (0, 0x1L)
  18.     while N >= power:
  19.         bits += 1
  20.         power = power << 1
  21.     return bits
  22.  
  23.  
  24. def getRandomNumber(N, randfunc):
  25.     '''getRandomNumber(N:int, randfunc:callable):long
  26.     Return an N-bit random number.'''
  27.     S = randfunc(N / 8)
  28.     odd_bits = N % 8
  29.     if odd_bits != 0:
  30.         char = ord(randfunc(1)) >> 8 - odd_bits
  31.         S = chr(char) + S
  32.     
  33.     value = bytes_to_long(S)
  34.     value |= 0x2L ** (N - 1)
  35.     if not size(value) >= N:
  36.         raise AssertionError
  37.     return value
  38.  
  39.  
  40. def GCD(x, y):
  41.     '''GCD(x:long, y:long): long
  42.     Return the GCD of x and y.
  43.     '''
  44.     x = abs(x)
  45.     y = abs(y)
  46.     while x > 0:
  47.         x = y % x
  48.         y = x
  49.     return y
  50.  
  51.  
  52. def inverse(u, v):
  53.     '''inverse(u:long, u:long):long
  54.     Return the inverse of u mod v.
  55.     '''
  56.     u3 = long(u)
  57.     v3 = long(v)
  58.     (u1, v1) = (0x1L, 0x0L)
  59.     while v3 > 0:
  60.         q = u3 / v3
  61.         u1 = v1
  62.         v1 = u1 - v1 * q
  63.         u3 = v3
  64.         v3 = u3 - v3 * q
  65.     while u1 < 0:
  66.         u1 = u1 + v
  67.     return u1
  68.  
  69.  
  70. def getPrime(N, randfunc):
  71.     '''getPrime(N:int, randfunc:callable):long
  72.     Return a random N-bit prime number.
  73.     '''
  74.     number = getRandomNumber(N, randfunc) | 1
  75.     while not isPrime(number):
  76.         number = number + 2
  77.     return number
  78.  
  79.  
  80. def isPrime(N):
  81.     '''isPrime(N:long):bool
  82.     Return true if N is prime.
  83.     '''
  84.     if N == 1:
  85.         return 0
  86.     if N in sieve:
  87.         return 1
  88.     for i in sieve:
  89.         if N % i == 0:
  90.             return 0
  91.     
  92.     if _fastmath is not None:
  93.         return _fastmath.isPrime(N)
  94.     N1 = N - 0x1L
  95.     n = 0x1L
  96.     while n < N:
  97.         n = n << 0x1L
  98.         continue
  99.         _fastmath is not None
  100.     n = n >> 0x1L
  101.     for c in sieve[:7]:
  102.         a = long(c)
  103.         d = 0x1L
  104.         t = n
  105.         while t:
  106.             x = d * d % N
  107.             if x == 0x1L and d != 0x1L and d != N1:
  108.                 return 0
  109.             t = t >> 0x1L
  110.             continue
  111.             N in sieve if N1 & t else N % i == 0
  112.         if d != 0x1L:
  113.             return 0
  114.     
  115.     return 1
  116.  
  117. sieve = [
  118.     2,
  119.     3,
  120.     5,
  121.     7,
  122.     11,
  123.     13,
  124.     17,
  125.     19,
  126.     23,
  127.     29,
  128.     31,
  129.     37,
  130.     41,
  131.     43,
  132.     47,
  133.     53,
  134.     59,
  135.     61,
  136.     67,
  137.     71,
  138.     73,
  139.     79,
  140.     83,
  141.     89,
  142.     97,
  143.     101,
  144.     103,
  145.     107,
  146.     109,
  147.     113,
  148.     127,
  149.     131,
  150.     137,
  151.     139,
  152.     149,
  153.     151,
  154.     157,
  155.     163,
  156.     167,
  157.     173,
  158.     179,
  159.     181,
  160.     191,
  161.     193,
  162.     197,
  163.     199,
  164.     211,
  165.     223,
  166.     227,
  167.     229,
  168.     233,
  169.     239,
  170.     241,
  171.     251]
  172. import struct
  173.  
  174. def long_to_bytes(n, blocksize = 0):
  175.     '''long_to_bytes(n:long, blocksize:int) : string
  176.     Convert a long integer to a byte string.
  177.  
  178.     If optional blocksize is given and greater than zero, pad the front of the
  179.     byte string with binary zeros so that the length is a multiple of
  180.     blocksize.
  181.     '''
  182.     s = ''
  183.     n = long(n)
  184.     pack = struct.pack
  185.     while n > 0:
  186.         s = pack('>I', n & 0xFFFFFFFFL) + s
  187.         n = n >> 32
  188.     for i in range(len(s)):
  189.         if s[i] != '\x00':
  190.             break
  191.             continue
  192.     else:
  193.         s = '\x00'
  194.         i = 0
  195.     s = s[i:]
  196.     if blocksize > 0 and len(s) % blocksize:
  197.         s = (blocksize - len(s) % blocksize) * '\x00' + s
  198.     
  199.     return s
  200.  
  201.  
  202. def bytes_to_long(s):
  203.     '''bytes_to_long(string) : long
  204.     Convert a byte string to a long integer.
  205.  
  206.     This is (essentially) the inverse of long_to_bytes().
  207.     '''
  208.     acc = 0x0L
  209.     unpack = struct.unpack
  210.     length = len(s)
  211.     if length % 4:
  212.         extra = 4 - length % 4
  213.         s = '\x00' * extra + s
  214.         length = length + extra
  215.     
  216.     for i in range(0, length, 4):
  217.         acc = (acc << 32) + unpack('>I', s[i:i + 4])[0]
  218.     
  219.     return acc
  220.  
  221. import warnings
  222.  
  223. def long2str(n, blocksize = 0):
  224.     warnings.warn('long2str() has been replaced by long_to_bytes()')
  225.     return long_to_bytes(n, blocksize)
  226.  
  227.  
  228. def str2long(s):
  229.     warnings.warn('str2long() has been replaced by bytes_to_long()')
  230.     return bytes_to_long(s)
  231.  
  232.