So it works in the full range of 2^256 so what would be the expected operations?
- 1 point addition to have Point (x1, y1)
- 1 subtraction to get y2
- 2 multiplications to get x2 and x3
- comparisions to get lowest x and lowest y
Then you will have all x and y coordinates for all 6 points with the effort of less than 2 point additions, what will increase the speed enormously.
- 1 point addition to have Point (x1, y1)
- 2 subtractions to get y2 and the corresponding private key
- 4 multiplications to get x2 and x3, and their corresponding private keys
- 3 comparisions to get lowest x and lowest y
The speedup works only on Pollard Rho, at most sqrt(6) = 2.44 times. For Kangaroo only the negation (y) is applicable, with speedup at most 1.41 times (and bigger variance?) - AFAIK Jean-Luc uses it already.
All this is well known:
if we have a point (x,y) = k*G, the 6 points are
(a
ix, b
jy) = c
id
j*(k*G)
with
a
3 = 1 mod p (matching the chosen value of c)
b
2 = 1 mod p
c
3 = 1 mod n (matching the chosen value of a)
d
2 = 1 mod n
i∈{0,1,2}
j∈{0,1}.
One can calculate the numbers by finding the primitive roots mod p and n
I.E.
r
p = 77643668876891235360856744073230947502707792537156648322526682022085734511405
r
n = 106331823171076060141872636901030920105366729272408102113527681246281393517969
a = (r
p(p-1)/3)
2 = 55594575648329892869085402983802832744385952214688224221778511981742606582254
b = r
p(p-1)/2 = 115792089237316195423570985008687907853269984665640564039457584007908834671662 = -1
c = r
n(n-1)/3 = 37718080363155996902926221483475020450927657555482586988616620542887997980018
d = r
n(n-1)/2 = 115792089237316195423570985008687907852837564279074904382605163141518161494336 = -1