Recitation 13a (Jan 30, 2012)
Welcome (Fall 2011/2012) » Recitation Logs (Fall 2011/2012) » Recitation 13a (Jan 30, 2012)
Code examples
Example 1: Pollard's Rho
See also wikipedia's explanation.
import random def gcd(a,b): while a and b: a,b=b,a%b return a+b def is_prime(m): for i in range(100): a = random.randrange(2,m) if pow(a,m-1,m) != 1: return False return True def generate_prime(k): while True: p = random.randrange(2**k,2**(k+1)) if is_prime(p): return p def pollard_rho(n): c = random.randrange(3, n) f = lambda x: (x**2 + c)%n # a "random" function x0 = 0 a = b = x0 for i in range(5*int(n**.25)): a = f(a) # turtle goes once b = f(f(b)) # rabbit goes twice d = gcd(abs(a-b), n) # have they met modulo p (or modulo q)? if d == 1: continue # not yet if d == n: return "d=n :(" # darn, it happened both at the same time return (d, n//d) # all went according to the master plan, muhahaha return "time's up :(" # probably the size of the loop is too large, let's call it a day def naive_factor(n): for p in range(2, int(n**.5)+2): if n%p: continue return (p, n//p)
Download (right click -> save link as "rho.py")
Interpreter session log
Python 3.2 (r32:88445, Feb 20 2011, 21:29:02) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
>>> ================================ RESTART ================================
>>>
>>> generate_prime(10)
1747
>>> generate_prime(10)
1171
>>> generate_prime(10)
1297
>>> generate_prime(10)
1847
>>> p = 1297; q=1847; n = p*q
>>> ================================ RESTART ================================
>>>
>>> p = 1297; q=1847; n = p*q
>>> pollard_rho(n)
(1847, 1297)
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
False
>>> ================================ RESTART ================================
>>>
>>> p = 1297; q=1847; n = p*q
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
"time's up :("
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
"time's up :("
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
"time's up :("
>>> pollard_rho(n)
(1297, 1847)
>>> ================================ RESTART ================================
>>>
>>> pollard_rho(n)
Traceback (most recent call last):
File "<pyshell#36>", line 1, in <module>
pollard_rho(n)
NameError: name 'n' is not defined
>>> p = 1297; q=1847; n = p*q
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1297, 1847)
>>> pollard_rho(n)
(1847, 1297)
>>> pollard_rho(n)
(1847, 1297)
>>> import timeit
>>> n
2395559
>>> timeit.timeit('pollard_rho(2395559)', number=1000)
Traceback (most recent call last):
File "<pyshell#46>", line 1, in <module>
timeit.timeit('pollard_rho(2395559)', number=1000)
File "C:\Python32\lib\timeit.py", line 228, in timeit
return Timer(stmt, setup, timer).timeit(number)
File "C:\Python32\lib\timeit.py", line 194, in timeit
timing = self.inner(it, self.timer)
File "<timeit-src>", line 6, in inner
NameError: global name 'pollard_rho' is not defined
>>> timeit.timeit(lambda: pollard_rho(n), number=1000)
0.2946671812136472
>>> timeit.timeit(lambda: pollard_rho(n), number=10000)
2.9489073615439736
>>> ================================ RESTART ================================
>>>
>>> p = 1297; q=1847; n = p*q
>>> import timeit
>>> timeit.timeit(lambda: naive_factor(n), number=10000)
3.1682785703571605
>>> p = generate_prime(20)
>>> q = generate_prime(20)
>>> n=p*q
>>> n
4186108378597
>>> timeit.timeit(lambda: naive_factor(n), number=10)
Traceback (most recent call last):
File "<pyshell#56>", line 1, in <module>
timeit.timeit(lambda: naive_factor(n), number=10)
File "C:\Python32\lib\timeit.py", line 228, in timeit
return Timer(stmt, setup, timer).timeit(number)
File "C:\Python32\lib\timeit.py", line 194, in timeit
timing = self.inner(it, self.timer)
File "C:\Python32\lib\timeit.py", line 100, in inner
_func()
File "<pyshell#56>", line 1, in <lambda>
timeit.timeit(lambda: naive_factor(n), number=10)
File "C:/Documents and Settings/ranihod/Desktop/r13-rho.py", line 40, in naive_factor
if n%p: continue
KeyboardInterrupt
>>> timeit.timeit(lambda: naive_factor(n), number=1)
0.9415343000949932
>>> timeit.timeit(lambda: naive_factor(n), number=5\)
SyntaxError: unexpected character after line continuation character
>>> timeit.timeit(lambda: naive_factor(n), number=5)
4.203114390426826
>>> timeit.timeit(lambda: pollard_rho(n), number=100)
1.8886902694955126
>>> pollard_rho(n)
(1996529, 2096693)
>>> pollard_rho(n)
(1996529, 2096693)
>>> pollard_rho(n)
(1996529, 2096693)
>>> 1996529*2096693
4186108378597
>>> n
4186108378597
>>>