homework3
system:sage


<h2> Problem 4 </h2>

Here is the curve $E(\mathbb{F}_p)$ and its order.

{{{id=1|
p = 1461501637330902918203684832716283019655973349331
E = EllipticCurve(GF(p),[1,0])
n = E.count_points()
factor(n)
///
2^2 * 3 * 41 * 2970531783192892110170091123407079308243848271
}}}

Here are two points $P$ and $Q$ on $E(\mathbb{F}_p)$ with $Q = [a]P$.

{{{id=2|
P = E(916695884547111349904583025841061270186986038721,
580841286046155102637492926195177127992061729856)
Q = E(1299635880259853636262044538415126323429627504320,
1120139906107476246466144743069490058897077692330)
///
}}}

Value of $a$ mod the largest factor of $\#E(\mathbb{F}_p)$.

{{{id=3|
t = 2970531783192892110170091123407079308243848271  # largest factor of #E(F_p)
s = 1864316221141791753837087178908449374069570910  # value of a mod t
///
}}}

<h2> Problem 6 </h2>

In this problem you will implement some variants of Pollard's rho method.  We will use the following elliptic curve and points.

{{{id=4|
p = 1048583
E = EllipticCurve(GF(p),[183801, 823458])
P = E(580655,963078)
Q = E(774292,954498)
///
}}}

The following function takes the two points $P$ and $Q$ in the discrete log problem and returns a random walk function.  (Note that in SAGE/Python functions can pass and/or return other functions.)

{{{id=5|
def walk_setup(P,Q):
    '''Compute a random walk function on E using 16 partitions.'''
    
    s = 16  # number of partitions

    A = [randint(1,P.order()) for i in range(s)]
    B = [randint(1,P.order()) for i in range(s)]
    PP = [A[i]*P+B[i]*Q for i in range(s)]
    
    # We define our random walk function
    def walk(T):
        '''Random walk function using parameters A,B,PP defined above.
           Input is a tuple T of the form T = (R, u, v), where R = u*P + v*Q.
           Output is of the same form, with updated values (R',u',v').
        '''
        
        # Choose partition by lifting x-coordinate to integers and reducing mod s
        k = ZZ(T[0][0])%s
        
        # Apply the walk function for the kth partition, keeping track of multipliers of P and Q      
        return (T[0]+PP[k],T[1]+A[k],T[2]+B[k])
        
    return walk
///
}}}

The following function implements Pollard's rho method in a naive way: at each step in the pseudorandom walk we store the computed point in a list and search the list for a collision.  While this is the fastest way to find a collision, it is space-intensive.

<p>Note that instead of using a Python list structure we use a dictionary structure, which allows for faster searching.  See the <a href="http://docs.python.org/tutorial/datastructures.html#dictionaries">Python tutorial</a> for details.

{{{id=8|
def collision_search(P,Q):
    '''Use the walk function to choose random points on E until a collision is found.
       output the discrete log of Q to the base P and the number of times the walk function is called.
    '''
    

    # Choose a random starting point P0; initialize u0, v0.
    b = randint(1,P.order())
    P0,u0,v0 = b*P,b,0
    
    # Set up the pseudorandom walk function
    walk = walk_setup(P,Q)
    X = (P0,u0,v0)        # first input to walk
    i = 0                 # number of steps in the walk
    D = {}                # list of points computed; we use a dictionary instead of a list for speed
        
    while(True):
        
        X = walk(X)       # step through the walk
        i += 1
        
        if X[0] in D:         # we found a collision
            u1,v1 = X[1],X[2] # u and v values of the current point
            u2,v2 = D[X[0]]   # u and v values of the collided point
            a = ((u1-u2)/(v2-v1)) % P.order()   # compute the discrete log
            return a,i
            
        else:
            D[X[0]] = (X[1],X[2])   # store u and v in the dictionary at index X[0]
///
}}}

{{{id=9|
collision_search(P,Q)
///
}}}

<h3>(a)</h3>

{{{id=10|
def floyd_rho(P,Q):
    '''Compute discrete log using Floyd cycle finding.'''
    
    
    # Initialize as above.

    # Repeat until P_i = P_{2i}
    
        # Compute P_{i+1} and P_{2i+1}

    # Output the discrete logarithm and the total number of times the walk function is called.
///
}}}

{{{id=11|
floyd_rho(P,Q)
///
}}}

<h3>(b,c)</h3>

{{{id=12|
def distpt_rho(P,Q,d):
    '''Compute discrete log of Q to the base P using distinguished points.
       1/d = probability of hitting a distinguished point'''
    
    # Initialize as above.
    
    while(True):
        # Iterate the random walk
        
        # Test for distinguished points
        if ZZ(x)%d == 0:   # here x is the x-coordinate of P_i

            # if P_i is in the list:
                # output the discrete log, number of distinguished points, and number of calls to walk.

            # else:               
                # Store P_i,u_i,v_i in a list (or dictionary).
         
        else:
            # (for part (c)): make sure we're not in a useless cycle
///
}}}

{{{id=13|
distpt_rho(P,Q,32)
///
}}}

<h3>(d)</h3>

Compute the average number of calls to <tt>walk</tt> in each of the three algorithms above over 1000 trials.

{{{id=14|

///
}}}

<!-- 
<h2> Problem #7 </h2>

Here is the curve $E(\mathbb{F}_p)$ and two points $P$ and $Q$ on $E(\mathbb{F}_p)$ with $Q = [a]P$.

{{{id=25|
p = 206163935269
E = EllipticCurve(GF(p),[0,2])
P = E(114953679480,165174358647)
Q = E(156479156240,45230029890)
///
}}}

Complete this procedure for part (b)

{{{id=21|
def anomalous_attack(E,P,Q):
    '''Computes discrete logarithm on anomalous curves.
       Uses algorithm on p. 162-163 of Washington.
       Outputs a such that Q = [a]P.
    '''

    # Field of definition of E
    F = E.base_field()
    p = F.order()

    # Step 1: Lift E,P,Q to Z to obtain EE, PP = (x1,y1), QQ = (x2,y2), as in Proposition 5.6.
    # Instead of lifting to Z we will lift to Z mod p^2.'''
       
    # Compute a random curve EE over Z_{p^2} that reduces to E mod p.
    A = [Integers(p^2)(E.a4()) + p*randint(1,p), Integers(p^2)(E.a6()) + p*randint(1,p)]    
    EE = EllipticCurve(A)
    
    # Compute a random point PP on EE that reduces to P mod p.
    
    # Compute a random point QQ on EE that reduces to Q mod p.
    
    # Step 2: Compute (p-1)*PP.
    
    # Step 3: Compute (p-1)*QQ.
    
    # Step 4: Compute m1 and m2 as on p. 163.  (Use integer arithmetic to avoid problems with inverses.)
    
    # Step 5: If v_p(m2) < 0 or v_p(m1) < 0, then try another EE. 
    
    # Otherwise, Q = aP, where a = m1/m2 mod p.
///
}}}

-->

{{{id=28|

///
}}}