View Single Post
Old 2007-01-18, 17:13   #3

153E16 Posts

Originally Posted by R.D. Silverman View Post
I am not sure I know what you mean by

OTOH, computing Fib(k)*P over Q is a purely exponential problem
because the heights of the points explode exponentially.

Please clarify your question.
The point P is bounded mod N.
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(K-2)*P + FIB(K-1)*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 r-1 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.
  Reply With Quote