Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

split_using_lambda

a guest Sep 17th, 2018 57 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top