20070528, 08:49  #1 
Aug 2002
2^{6}·5 Posts 
Pseudorandom maps over an elliptic curve
Anyone have any idea how exactly pseudorandom 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 pollardrho attack on ecc2k130. I know the mapping function used by pollardrho 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 bitslicing and a normal basis to do 32 point operations in parallel). 
20070528, 13:22  #2 
"Bob Silverman"
Nov 2003
North of Boston
7508_{10} Posts 

20070528, 16:25  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
The first couple of doublings will send you into the subgroup of <P> 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 <P> is probably not divisible by a large power of 2, the subgroup will be large as well (almost as large as <P>) so finding a cycle takes O(N) iterations instead of the O(sqrt(N)) you wanted. Frequent reseeding may help, but it's better to choose a proper random map instead.
Alex 
20070528, 18:04  #4 
Aug 2002
500_{8} Posts 
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.

20070529, 21:30  #5 
Aug 2002
500_{8} Posts 
I've decided to use a set of 8 (possibly 16) different point additions as the map (with no doubling).

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Elliptic curve arithmetic  burrobert  GMPECM  6  20121108 13:05 
Elliptic Curve Arithmetic  Raman  Math  8  20090413 19:20 
Elliptic curve method  Dirac  Factoring  11  20071101 14:01 
Linear recurrence on elliptic curve  Unregistered  Information & Answers  2  20070118 17:13 
Elliptic factoring with points *NOT* on the curve  bongomongo  Factoring  5  20061221 18:19 