• API
• FAQ
• Tools
• Archive
SHARE
TWEET split_using_lambda a guest Sep 17th, 2018 65 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
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.

Top