Kangaroo Methods for Solving the Interval Discrete Logarithm Problem
https://www.math.auckland.ac.nz/~sgal018/AFhons.pdf
In that, the author attempts to find better running times than the 4-kangaroo method presented by Pollard et. all in 2011 or so, and claims to have found them, at least by using 5 kangaroos. Then he also presents a 7-kangaroo algorithm with an almost similar run-time (but not really better).
However I'm either stupid or missed something obvious. The author uses some smart approximation algorithms to find some constants that should be used for the exponents of the Tame and Wild kangaroos.
But these constants are not integers, so the author suggests to use the closest integer values when multiplied by N (interval size). The entire analysis is based on the assumption that these Wild kangaroos start off inside the interval.
What I do not understand is: if we are given a public key. and are told it is found in some interval of size N, then the only known points that we can tell for sure are in some interval are:
- the public key itself
- the opposite point (between -N and -1)
- integer multiples of either of the above two points
- added or subtracted known deltas of any point in the above three cases
So, how did the author reached the conclusion of finding better algorithms, given that we can't be sure that when we do an exponentiation of the form:
Code:
g**0.815N * h
then the resulting point will only ever lie in a known interval as the original only when both N and the private key are both divisible by 1000?
It is basically the same problem as when some guys attempt to divide some public key by 2, 4, 8 etc.
Every time we "divide" we cannot tell if the resulting point lies in the lower half of the interval, or whether it is offset by (groupOrder + 1)/2, because we don't know the parity of the private key.
So, is this study wrong? There are also no given experimental tests.