# How to implement birthday paradox continuation of elliptic curve factorization algorithm

I have already implemented Lenstra's algorithm for factoring integers using elliptic curves; it is shown below, or you can run it at http://ideone.com/QEDmMY. Beware that my code is optimized for simplicity and clarity, not for speed.

I would like to implement the second stage of elliptic curve factorization using the birthday paradox continuation, which I read about in Richard Brent's paper "Some Integer Factorization Algorithms Using Elliptic Curves."

However, I don't understand Brent's algorithm, or perhaps just his notation. In Section 6, what is $Q_j^2$ in the definition of $Q_{j+1}$? Likewise, what is $Q_j^2 * Q$? Since $Q$ is just a point on the elliptic curve, how can it be squared or multiplied by another point? And how is $r$ computed? Brent discusses $r$ but never defines it.

Many thanks,

Phil

# lenstra's algorithm

from random import randint
from fractions import gcd

def primes(n):
b, p, ps = [True] * (n+1), 2, []
for p in xrange(2, n+1):
if b[p]:
ps.append(p)
for i in xrange(p, n+1, p):
b[i] = False
return ps

def bezout(a, b):
if b == 0: return 1, 0, a
q, r = divmod(a, b)
x, y, g = bezout(b, r)
return y, x-q*y, g

def add(p, q, a, b, m):
if p[2] == 0: return q
if q[2] == 0: return p
if p[0] == q[0]:
if (p[1] + q[1]) % m == 0:
return 0, 1, 0 # infinity
n = (3 * p[0] * p[0] + a) % m
d = (2 * p[1]) % m
else:
n = (q[1] - p[1]) % m
d = (q[0] - p[0]) % m
x, y, g = bezout(d, m)
if g > 1: return 0, 0, d # failure
z = (n*x*n*x - p[0] - q[0]) % m
return z, (n * x * (p[0] - z) - p[1]) % m, 1

def mul(k, p, a, b, m):
r = (0,1,0)
while k > 0:
if p[2] > 1:
return p
if k % 2 == 1:
r = add(p, r, a, b, m)
k = k // 2
p = add(p, p, a, b, m)
return r

def lenstra(n, limit):
g = n
while g == n:
q = randint(0, n-1), randint(0, n-1), 1
a = randint(0, n-1)
b = (q[1]*q[1] - q[0]*q[0]*q[0] - a*q[0]) % n
g = gcd(4*a*a*a + 27*b*b, n)
if g > 1: return g # lucky factor
for p in primes(limit):
pp = p
while pp < limit:
q = mul(p, q, a, b, n)
if q[2] > 1:
return gcd(q[2], n)
pp = p * pp
return False

-

On the first line of page 4 Brent introduces a multiplicative notation for the group operation on the elliptic curve. This is a bit unusual in the context of elliptic curves, but it is difficult to think what else it might mean. Therefore his

1. $Q_j^2$ is the double of the point $Q_j$, many authors use the notation $2Q_j$ for this. IIRC $[2]Q_j$ is also in use, but I may be wrong.
2. Similarly his $Q_j^2*Q$ is more commonly denoted by $2Q_j+Q$.

In other words it sounds something like a step in a double-and-add -algorithm. I didn't read all the paper, so don't know for sure.

So as long as you have implemented the usual point doubling and point addition routines for the elliptic curve, you should be fine.

-
Thank you for your response. I thought that might be the answer, but wasn't sure. Can you please answer the remaining question: how can I compute r? –  user448810 Dec 20 '12 at 0:30
@user448810: I don't know with absolute certainty. It seems to me that $r$ is just a parameter. Something like the number of people present in the birthday paradox setting? My best guess is that you are to tune-up the value of this parameter for optimal performance or something. His table 9 seems to have typical values. –  Jyrki Lahtonen Dec 20 '12 at 9:40
Thanks for your help. I have a working program, though it's extremely slow and clearly not right. I've been reading a <a href="infoscience.epfl.ch/record/164495/files/…; by Bosma and Lenstra that provides more details, and I'll be implementing that next. I'll close out this question and ask again if I have other questions. Again, many thanks. Phil –  user448810 Dec 20 '12 at 13:39