Guest User

split_using_lambda

a guest
Sep 17th, 2018
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # https://groups.google.com/forum/#!topic/sci.crypt/wDV49EsAZQ0
  2.  
  3. def gcd(x, y):
  4.     """Return the GCD of x and y."""
  5.     while x>0:
  6.         x, y = y%x, x
  7.     return y
  8.  
  9. def split_using_lambda(n, s):
  10.     """Given a composite n and and a multiple of lambda(n),
  11.    return a non-trival factor of n.
  12.    Loops out or asserts false on bad inputs.
  13.    """
  14.     #  Divide factors of 2 out of exponent s
  15.     while s & 1 == 0:
  16.         s = s >> 1
  17.     #  Try bases until we find a factor
  18.     for base in xrange(1, 999, 2):
  19.         #  Realy we should set base randomly, but this works
  20.         a = pow(long(base), s, n)
  21.         if a == 1:
  22.             #  Darn, we got to 1 without finding a square root
  23.             continue
  24.         #  Keep squaring until we hit 1.
  25.         while a != 1 and a != n-1:
  26.             b = a
  27.             a = a * a % n
  28.         if a == 1:
  29.             #  Got it
  30.             return gcd(n, b + 1)
  31.         # Darn, the square root we found was -1.
  32.     assert(0), "Something is very wrong."
RAW Paste Data