Pseudo-random maps over an elliptic curve

[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)?

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

[R.D. Silverman]

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.

[akruppa]

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 re-seeding may help, but it's better to choose a proper random map instead.

Alex

[ColdFury]

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.

[ColdFury]

I've decided to use a set of 8 (possibly 16) different point additions as the map (with no doubling).