## Pollard’s Rho Algorithm For Discrete Logarithms

### May 27, 2016

We studied discrete logarithms in two previous exercises. Today we look at a third algorithm for computing discrete algorithms, invented by John Pollard in the mid 1970s. Our presentation follows that in the book *Prime Numbers: A Computational Perspective* by Richard Crandall and Carl Pomerance, which differs somewhat from other sources.

Our goal is to compute *l* (some browsers mess that up; it’s a lower-case ell, for “logarithm”) in the expression *g ^{l}* ≡

*t*(mod

*p*); here

*p*is a prime greater than 3,

*g*is an integer generator on the range 1 ≤

*g*<

*p*, and

*t*is an integer target on the range 1 ≤

*g*<

*p*. Pollard takes a sequence of integer pairs (

*a*,

_{i}*b*) modulo (

_{i}*p*− 1) and a sequence of integers

*x*modulo

_{i}*p*such that

*x*=

_{i}*t*g

^{ai}^{bi}(mod

*p*), beginning with

*a*

_{0}=

*b*

_{0}= 0 and

*x*

_{0}= 1. Then the rule for deriving the terms of the various sequences is:

- If 0 <
*x*<_{i}*p*/3, then*a*_{i+1}= (*a*+ 1) mod (_{i}*p*− 1),*b*_{i+1}=*b*, and_{i}*x*_{i+1}=*t x*(mod_{i}*p*). - If
*p*/3 <*x*< 2_{i}*p*/3, then*a*_{i+1}= 2*a*mod (_{i}*p*− 1),*b*_{i+1}= 2*b*mod (_{i}*p*− 1), and*x*_{i+1}=*x*_{i}^{2}mod*p*. - If 2
*p*/3 <*x*<_{i}*p*, then*a*_{i+1}=*a*,_{i}*b*_{i+1}= (*b*+ 1) mod (_{i}*p*− 1), and*x*_{i+1}=*g x*mod_{i}*p*.

Splitting the computation into three pieces “randomizes” the calculation, since the interval in which *x _{i}* is found has nothing to do with the logarithm. The sequences are computed until some

*x*=

_{j}*x*, at which point we have

_{k}*t*

^{aj}*g*=

^{bj}*t*

^{ak}*g*. Then, if

^{bk}*a*−

_{j}*a*is coprime to

_{j}*p*− 1, we compute the discrete logarithm

*l*as (

*a*−

_{j}*a*)

_{k}*l*≡

*b*−

_{k}*b*(mod (

_{j}*p*− 1)). However, if the greatest common divisor of

*a*−

_{j}*a*with

_{j}*p*− 1 is

*d*> 1, then we compute (

*a*−

_{j}*a*)

_{k}*l*

_{0}≡

*b*−

_{k}*b*(mod (

_{j}*p*− 1) /

*d*), and

*l*=

*l*

_{0}+

*m*(

*p*− 1) /

*d*for some

*m*= 0, 1, …,

*d*− 1, which must all be checked until the discrete logarithm is found.

Thus, Pollard’s rho algorithm consists of iterating the sequences until a match is found, for which we use Floyd’s cycle-finding algorithm, just as in Pollard’s rho algorithm for factoring integers. Here are outlines of the two algorithms, shown side-by-side to highlight the similarities:

# find d such that d | n # find l such that g**l = t (mod p) function factor(n) function dlog(g, t, p) func f(x) := (x*x+c) % n func f(x,a,b) := ... as above ... t, h, d := 1, 1, 1 j := (1,0,0); k := f(1,0,0) while d == 1 while j.x <> k.x t = f(t) j(x,a,b) := f(j.x, j.a, j.b) h = f(f(h)) k(x,a,b) := f(f(k.x, k.a, k.b)) d = gcd(t-h, n) d := gcd(j.a-k.a, p-1) return d return l ... as above ...

Please pardon some abuse of notation; I hope the intent is clear. In the factoring algorithm, it is possible that *d* is the trivial factor *n*, in which case you must try again with a different constant in the *f* function; the logarithm function has no such possibility. Most of the time consumed in the computation is the modular multiplications in the calculations of the *x* sequence; the algorithm itself is O(sqrt *p*), the same as the baby-steps, giant-steps algorithm of a previous exercise, but the space requirement is only a small constant, rather than the O(sqrt *p*) space required of the previous algorithm. In practice, the random split is made into more than 3 pieces, which complicates the code but speeds the computation, as much as a 25% improvement on average.

Your task is to write a program that computes discrete logarithms using Pollard’s rho algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Test Scores

### May 24, 2016

The high school two blocks from me just had their annual picnic, my youngest daughter just graduated from college, and my primarily academic readership suddenly dropped in half (history suggest it will stay low until mid-August), so it seems to be the right season to have a simple data-processing task involving student test scores.

Given a list of student names and test scores, compute the average of the top five scores for each student. You may assume each student has as least five scores.

Your task is to compute student scores as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## No Exercise Today

### May 20, 2016

I’ve been busy at work and haven’t had time to prepare an exercise for today. I apologize.

Your task is to solve a previous exercise that you haven’t yet solved. Have fun!

## Conditional Heap Insertion

### May 17, 2016

This is an Amazon interview question:

Given a heap (priority queue), insert an element into the heap if the element is not already present in the heap. Your solution must work in O(

n) time, wherenis the number of items in the heap.

Your task is to write a program to insert an element into a heap if the element is not already present in the heap, in logarithmic time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Interleaved Increasing-Decreasing Sort

### May 13, 2016

This must be somebody’s homework:

Given an array of integers, rearrange the elements of the array so that elements in even-indexed positions are in ascending order and elements in odd-indexed positions are in descending order. For instance, given the input 0123456789, the desired output is 0927456381, with the even-indexed positions in ascending order 02468 and the odd-indexed positions in descending order 97531.

Your task is to write a program that performs the indicated rearrangement of its input. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Concatenate N N Times

### May 10, 2016

A number like 7777777 consists of the number 7 concatenated to itself 7 times. A number like 121212121212121212121212 consists of the number 12 concatenated to itself 12 times.

Your task is to write a program that calculates the number that is concatenated to itself the number of times as the number is (that’s hard to say). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Baby Steps, Giant Steps

### May 6, 2016

In a previous exercise we discussed the discrete logarithm problem, which is to compute the exponent *y* in the expression *x ^{y}* ≡

*n*(mod

*m*), given

*x*,

*n*, and

*m*; the modulus

*m*is usually taken as prime. Today we look at an algorithm, known as baby steps, giant steps, that was developed by Daniel Shanks in 1971:

1. Compute limits:

*b* = ⌈ √*m* ⌉

*h* = (*x*^{−1})^{b}

2. Construct lists:

*A* = { *x ^{i}* :

*i*= 0, 1, …,

*b*− 1 } // giant steps

*B* = { *n h ^{j}* :

*j*= 0, 1, …,

*b*− 1 } // baby steps

3. Sort and find intersection:

Sort the lists *A* and *B*

Find an intersection, say *x ^{i}* =

*n h*

^{j}Return *y* = *i* + *j b*

Since *m* is prime, there must be some *y* ∈ [0, *m*) for which *x*^{y} ≡ *n* (mod *m*). Write *y* = *i* + *j b*, where *b* = ⌈ √*m* ⌉. Since *y* must exist, so too *i* (which counts the giant steps) and *j* (which counts the baby steps) must exist, and there must be an intersection between the baby steps and the giant steps.

Time complexity is obviously O(sqrt *m*), which beats the O(*m*) time complexity of the brute-force algorithm of the previous exercise. There are better algorithms for computing discrete logarithms, which we will study in future exercises.

Your task is to write a program that calculates discrete logarithms using the baby steps, giant steps algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Discrete Logarithms

### May 3, 2016

The discrete logarithm problem is to compute the exponent *y* in the expression *x ^{y}* ≡

*n*(mod

*m*), given

*x*,

*n*, and

*m*;

*x*and

*m*must be relatively prime, which is usually enforced by taking the modulus

*m*as prime. For instance, in the expression 3

^{y}≡ 13 (mod 17), the discrete logarithm

*y*= 4, since 3

^{4}≡ 13 (mod 17). The discrete logarithm problem is of fundamental importance in some branches of cryptography, and bears many similarities to factoring integers. Although we have states the discrete logarithm problem using integers, in many cases some other group is used, for instance calculating discrete logarithms on an elliptic curve.

The simplest algorithm for finding the discrete logarithm is simply to try each *y* from 0 to *m*; if *m* is prime, one of the *y* is certain to work. Unfortunately, this algorithm is very slow, taking time O(*m*). We’ll see better algorithms in future exercises; our purpose today is to introduce the concept of the discrete logarithm, and to provide a known good algorithm as a base for testing future algorithms.

Your task is to write a program that computes discrete logarithms by trying each possible value in succession until the answer is found. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Binary Search

### April 29, 2016

I goofed.

While writing a program (it may appear in a future exercise) I needed to search a sorted array for a target value. I should have copied an existing binary search, but instead I wrote my own, since I’m a good programmer and can certainly write a simple function like that. You won’t have any trouble guessing what happened next.

Your task is to write a binary search function; do it yourself, without looking at any library implementations or searching the internet. You might also want to write a test script to give you confidence in your function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## An Integer Formula For Fibonacci Numbers

### April 26, 2016

Today’s exercise isn’t really an exercise but an astonishing integer formula for computing the *n*th Fibonacci number; here it is in Python:

def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) − (2 << n) − 1) & ((2 << n) − 1)

You can see an explanation here and discussion here.

Your task is to translate the program to your favorite language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.