View Single Post
2007-01-18, 16:20   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Unregistered 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.
I am not sure I know what you mean by "direct reduction"?

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.