• API
• FAQ
• Tools
• Archive
A Pastebin account makes a great Christmas gift
SHARE
TWEET

# split_using_lambda

a guest Sep 17th, 2018 57 Never
ENDING IN00days00hours00mins00secs

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