mersenneforum.org Linear recurrence on elliptic curve
 Register FAQ Search Today's Posts Mark Forums Read

 2007-01-18, 15:31 #1 Unregistered   84916 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 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. 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*(r-1)) 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".
2007-01-18, 16:20   #2
R.D. Silverman

Nov 2003

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

2007-01-18, 17:13   #3
Unregistered

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

 Similar Threads Thread Thread Starter Forum Replies Last Post burrobert GMP-ECM 6 2012-11-08 13:05 fivemack Math 0 2010-08-22 14:52 Raman Math 8 2009-04-13 19:20 Dirac Factoring 11 2007-11-01 14:01 bongomongo Factoring 5 2006-12-21 18:19

All times are UTC. The time now is 21:39.

Fri May 20 21:39:39 UTC 2022 up 36 days, 19:40, 0 users, load averages: 1.03, 2.47, 2.36