View Single Post
 2007-01-18, 15:31 #1 Unregistered   2·3·5·163 Posts 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 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".