### PROBLEM LINK:

**Author:** Tom Chen

**Tester:** Jingbo Shang

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

MEDIUM-HARD

### PREREQUISITES:

Quadratic residue, Tonelli-Shanks algorithm, Baby-step giant-step algorithm

### PROBLEM:

Given a prime P of the form 5k + 1 or 5k - 1, and and integer C, find, if exists, the smallest non-negative integer n such that F_{n} = C (mod P), where F_{n} is the n-th fibonacci number.

### QUICK EXPLANATION:

Based on the condition that (P mod 5) is either 1 or -1, we can deduce that 5 is a quadratic residue modulo P. Tonelli-Shanks algorithm can be used to find the integer x such that x^{2} = 5 (mod P). Using the value of x, we can find the explicit formula for n-th fibonacci number modulo P.

// Golden ratio modulo P

y = (1 + x) / 2

F_{n} = (y^{n} - (-1/y)^{n}) / x

Since we know the values of F_{n} and x, the above equation can be used to find the value of y^{n} by solving a quadratic equation modulo P.

Now, we know the value of y and y^{n}, and want to calculate the value of n. This is the classical Discrete Log problem and can be solved efficiently using Baby-step giant-step algorithm.

### EXPLANATION:

The value of the n-th fibonacci number can be calculated using the explicit formula:

F_{n} = (y^{n} - (-1/y)^{n}) / √5,

where y is the golden ratio, i.e.,

y = (1 + √5) / 2

Let us see, how this formula looks for fibonacci number modulo a prime P.

First, we need to check if √5 exists modulo P, i.e., if there is an integer x such that x^{2} = 5 (mod P).

### Legendre Symbol and golden ratio computation:

In order to check whether for a given integer a, there exist an integer x such that x^{2} = a (mod P), one needs to compute the legendre symbol (a | P). Here, we want to compute (5 | P).

Using quadratic reciprocity, we can write

(5 | P) = (-1)^{((5 - 1)/2 * (P - 1)/2)} * (P | 5) = (P | 5)

= (P mod 5 | 5)

Based on the constraints (P mod 5) is either 1 or 4, both of them are a quadratic residue modulo 5 (This is because 1^{2} = 1 (mod 5), and 2^{2} = 4 (mod 5)). Hence, (5 | P) = (P mod 5 | P) = 1, i.e., 5 is a quadratic residue modulo P.

This means that there exist an integer x such that x^{2} = 5 (mod P).

We will discuss later how to compute such x. For the time being let us assume that we have an oracle who computes the square root modulo a prime for us.

Hence, the expresison for golden ratio can be written as

y = (1 + x)/2 mod P.

Since P is an odd prime, 2 * (P + 1)/2 = 1 (mod 1), i.e., 2^{-1} = (P + 1)/2. Therefore,

y = (P + 1)/2 * (1 + x).

Note that, (1 + x)/2 * (-1 + x)/2 = (x^{2} - 1)/4 = 1 mod P.

Hence, y^{-1} mod P exists.

### Explicit formula for fibonacci number and bound on the answer (if exists):

Now that we know the value of golden ratio y, and √5 = x, we can write

F^{n} = (y^{n} - (-1/y)^{n}) / x

Note that x and P are relatively prime (this is because gcd(x^{2} = 5, P) = 1). Hence, x^{-1} mod P must exist. Therefore, we can write the expression for n-th fibonacci number explicitly as

F^{n} = x^{-1} * (y^{n} - (-1/y)^{n}).

According to Fermat’s little theorem (a^{P} = a (mod P)). Hence, both y^{n} and (-1/y)^{n} are periodic, with a period of at most P.

This implies that F_{n} mod P is also periodic with period at most P. Hence, for a given C, if there exist an n such that F_{n} = C, then also once such n exist, which is <= P. Hence, we only look for candidate n which are smaller than P.

### Reduction into discrete log problem:

Now, we want the n-th fibonacci number to be C. This gives us the following equation:

C = x^{-1} * (y^{n} - (-1/y)^{n})

C * x = y^{n} - (-1/y)^{n}

Now we should consider two cases: One when n is odd, and the other one when n is even. For each case we should solve the above equation and compute the value of n. If the parity of computed n matches with the case that we are considering, then we have a solution, otherwise we do not have an n at which fibonacci sequence takes value C modulo P.

Here, we only consider the case when n is even, and leave the other one as an exercise for the reader. In case of even n

y^{n} - (1/y)^{n} = C * x = z

This is a quadratic equation in y^{n}. Solving this equation we get

y^{n} = (z ± √(z^{2} + 4))/2.

Once again we use our oracle to compute the square root of (z^{2} + 4) if exists. We have two possible values of y^{n}, we consider both values and compute the value of n from it.

In other words, now our problem has been reduced to the following problem: Given integer y, u and prime P, find the smallest even number n such that

y^{n} = u mod P

If we remove the constraint that n is even, then this problem is known as discrete log problem. In the next section, we discuss how to solve the discrete log problem, and the following section shows how to extend the discrete log problem when the extra constraint of n being even is enforced.

### Discrete log problem (Baby step giant step algorithm):

We know that if the equation (y^{n} = u) has a solution, it must have a solution smaller than P. If we have an integer Q whose value is approximately √P, then we can write the integer n as

n = Qa + b, where both a and b are smaller than Q.

y^{n} = y^{Qa + b}

u = y^{Qa + b}

u * (y^{-Q})^{a} = y^{b}

We compute the values of y^{0}, y^{1}, …, y^{Q - 1} and store them in a map. This can be done in O (√P) time. If the map contains u, then we have already found a solution of the above equation. Otherwise we compute w = y^{-Q}, and iterate through its powers.

For the a-th power of w we have w^{a} = y^{-Qa}

Next we compute u * w^{a}, and search for it in the map, if this value is found in the map, that means we have y^{b} = u * y^{-Qa}, i.e., y^{Qa + b} = u, which is a solution of the equation we are looking for.

If we have iterated through all values of a from 1 to Q, and did not find a solution, that means the equation has no solution.

### Family of solution for y^{n} = u mod P:

Let us say that we have two solutions n1 and n2 of the above equation, that means

y^{n1} = y^{n2} = u mod P

y^{(n1 - n2)} = 1 mod P

i.e., (n1 - n2) is a multiple of the order of y, Ord(y).

Ord(y) is the smallest integer m such that y^{m} = 1 (mod P). Based on Fermat’s little theorem y^{P - 1} = 1, Hence Ord(y) must divide (P - 1).

We can iterate thorough divisors of (P - 1), and for each divisor d check if y^{d} = 1. The smallest such d will be Ord(y).

Since there are O (√P) divisors of (P - 1), and computation of (y^{d} mod P) can be done in O (lg P) time, we can compute Ord(y) in O (√P lg P) time.

Once we have computed Ord(y) = m, the family of solution of the above equation can be represented as

n = n1 + k * m

where n1 is the smallest solution found by Baby step giant step algorithm.

If n1 is even, then we already have a solution of the discrete log problem with even constraint. If n1 is odd, and m is even, then we can see that the family of solution will consist of odd integers only. In this case we have no even solution of the discrete log. On the other hand, if both n1 and m is odd, then the smallest even solution of the discrete log problem is (n1 + m).

### Square root modulo a prime computation:

Finally we discuss the oracle that we have been using to compute the square root modulo a prime P. This is in fact the Tonelli Shanks algorithm. The algorithm is well explained here Tonelli Shanks algorithm, and requires finding a quadratic nonresidue modulo the prime. Since there are (P + 1)/2 quadratic non-residues, a randomized algorithm will find find a quadratic non-reside in O (1) steps with high probability.

The overall complexity of the Tonelli Shanks algorithm is O (lg^{2} P).

### Time Complexity:

O (√P lg P)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.

Tester’s solution can be found here.