mersenneforum.org > Math Pseudo-random maps over an elliptic curve
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-28, 08:49 #1 ColdFury     Aug 2002 26·5 Posts Pseudo-random maps over an elliptic curve Anyone have any idea how exactly pseudo-random the map F(P) = 2P behaves where P is a point on a Koblitz elliptic curve defined over GF(2^131)? I'm currently implementing a core used for a pollard-rho attack on ecc2k-130. I know the mapping function used by pollard-rho should behave randomly as possible, and most implementations partition the points and perform a different operation depending on where the input point lies. However, I can parallelize the core much easier if I use just the fixed function F(P) = 2P (actually any fixed function will work). So, I'm wondering, how far from random would this function actually behave? I'm not sure if the (possibly) additional distinguished points needed to be found would outweigh the faster core. I'm most worried about the repeated point doubling causing trivial cycles, but I can always have the core start from a new point at regular intervals, mitigitating this effect somewhat. (If I use a single fixed random map, then I can easily use bit-slicing and a normal basis to do 32 point operations in parallel).
2007-05-28, 13:22   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

Quote:
 Originally Posted by ColdFury Anyone have any idea how exactly pseudo-random the map F(P) = 2P behaves where P is a point on a Koblitz elliptic curve defined over GF(2^131)?

It will depend on whether 2 is co-prime to the group order.

 2007-05-28, 16:25 #3 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts The first couple of doublings will send you into the subgroup of

with all the 2's in the order removed. Further doublings will simply hop around that subgroup and will cyclically generate most (or even all? Hmm...) points there. Since the order of

is probably not divisible by a large power of 2, the subgroup will be large as well (almost as large as

) so finding a cycle takes O(N) iterations instead of the O(sqrt(N)) you wanted. Frequent re-seeding may help, but it's better to choose a proper random map instead. Alex

2007-05-28, 18:04   #4
ColdFury

Aug 2002

5008 Posts

Quote:
 Originally Posted by R.D. Silverman It will depend on whether 2 is co-prime to the group order.
The starting point has order 680564733841876926932320129493409985129, and the order of the entire curve is 4*680564733841876926932320129493409985129, so I don't believe that should not be a problem.

 2007-05-29, 21:30 #5 ColdFury     Aug 2002 5008 Posts I've decided to use a set of 8 (possibly 16) different point additions as the map (with no doubling).

 Similar Threads Thread Thread Starter Forum Replies Last Post burrobert GMP-ECM 6 2012-11-08 13:05 Raman Math 8 2009-04-13 19:20 Dirac Factoring 11 2007-11-01 14:01 Unregistered Information & Answers 2 2007-01-18 17:13 bongomongo Factoring 5 2006-12-21 18:19

All times are UTC. The time now is 02:52.

Sat Feb 4 02:52:13 UTC 2023 up 170 days, 20 mins, 1 user, load averages: 0.80, 0.83, 0.90