View Single Post
Old 2007-01-18, 15:31   #1

3×1,549 Posts
Default Linear recurrence on elliptic curve

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

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

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):
Mentions "rate doubling formula".
  Reply With Quote