 # split_using_lambda

a guest
Sep 17th, 2018
112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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