Let Po be a point on elliptic curve E over Zn, n=p*q composite.

Let Fib(k) be k-th fibonacci number or any other linear

recurrence.

Is it possible to efficiently compute Fib(big) * Point?

Or is it known to be a hard problem?

The usual doubling computing of Fib() gives integer explosion

and the group order of E is unknown, so direct reduction is

impossible.

Basic idea:

Consider E over Fp. The group order may be smooth * r, r not

large prime.

Compute Po2 = smooth2 * Po.

The period of k*Po2 is r.

Fib( m*(r-1)) mod r = 0 or Fib( m*(r+1) ) mod r = 0 so

Fib( m*(r +/-1)) * Po2 is the point at infinity.

r +/-1 may be smooth.

Hakmem ITEM 14 (Gosper & Salamin):

http://www.inwap.com/pdp10/hbaker/ha...ecurrence.html
Mentions "rate doubling formula".