Guest User

split_using_lambda

a guest
Sep 17th, 2018
112
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×