Quote:
Originally Posted by R.D. Silverman
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(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.