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

3·23·137 Posts

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(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.