Recitation 13a (Jan 30, 2012)

Code examples

Example 1: Pollard's Rho

See also wikipedia's explanation.

» show Python code »

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

» show Python code »

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
>>>