mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2007-01-18, 15:31   #1
Unregistered
 

2·3·1,493 Posts
Default 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".
  Reply With Quote
Old 2007-01-18, 16:20   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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.

Please clarify your question.
R.D. Silverman is offline   Reply With Quote
Old 2007-01-18, 17:13   #3
Unregistered
 

2·3·173 Posts
Default

Quote:
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
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Elliptic curve arithmetic burrobert GMP-ECM 6 2012-11-08 13:05
Elliptic-curve L-function question fivemack Math 0 2010-08-22 14:52
Elliptic Curve Arithmetic Raman Math 8 2009-04-13 19:20
Elliptic curve method Dirac Factoring 11 2007-11-01 14:01
Elliptic factoring with points *NOT* on the curve bongomongo Factoring 5 2006-12-21 18:19

All times are UTC. The time now is 18:32.

Fri May 7 18:32:29 UTC 2021 up 29 days, 13:13, 0 users, load averages: 2.59, 2.77, 3.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.