20070118, 15:31  #1 
1E52_{16} 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 kth 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*(r1)) 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". 
20070118, 16:20  #2  
"Bob Silverman"
Nov 2003
North of Boston
2·3·29·43 Posts 
Quote:
I don't follow you. Given a large integer k, one can compute Fib(k) in O(log(k)) multiplications. If we are computing over Z, the numbers get exponentially large, so the entire computation takes exponentially many bit operations (even with FFT's to do the multiplication). However, computing Fib(k) mod N (or Fib(k)*P where P is an EC point over Z/NZ) has *bounded* intermediate values. Computing M*P on an elliptic curve over Z/NZ is a polynomial time computation because the intermediate values are bounded in size and only polynomially many multiplications are required. OTOH, computing Fib(k)*P over Q is a purely exponential problem because the heights of the points explode exponentially. Please clarify your question. 

20070118, 17:13  #3  
2·3,733 Posts 
Quote:
All computations are mod N and they involve just point additions. P + P = 2*P P + 2*P = 3*P 2*P + 3*P = 5*P ... FIB(K2)*P + FIB(K1)*P= FIB(K)*P so if the group order is r, r prime, FIB(K) should be taken mod r and FIB(K)*P hits the point at infinity for K multiples of r1 or r+1. The question is may FIB(K)*P (this bounded mod N) be computed efficiently for large K product of small primes. The value of FIB(K) is not needed. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Elliptic curve arithmetic  burrobert  GMPECM  6  20121108 13:05 
Ellipticcurve Lfunction question  fivemack  Math  0  20100822 14:52 
Elliptic Curve Arithmetic  Raman  Math  8  20090413 19:20 
Elliptic curve method  Dirac  Factoring  11  20071101 14:01 
Elliptic factoring with points *NOT* on the curve  bongomongo  Factoring  5  20061221 18:19 