Pollard Lambda fails to find valid discrete logarithm

[Georgi Guninski]

I think this is a bug:

```
#Author Georgi Guninski

p=90887;Kp=GF(p);g=Kp(2);X=46712;a=X*g
print(a==X*g)
Y=discrete_log_lambda(a,g,operation="+",bounds=(1,p))

-> 1076 raise ValueError("Pollard Lambda failed to find a log")
ValueError: Pollard Lambda failed to find a log
```

[Nils Bruin]

That's an ... interesting ... way to do a division, but sure: also in prime cyclic groups represented as an additive group discrete log algorithms should work.

When I try your example on a version that is reported as 10.3.beta3, I'm not getting an error, so you'll probably have to include version information and quite likely the random seed to make this error reliably reproducible.

Looking at the implementation, there is a low probability that the routine produces this error even if there is a discrete log to be found: it tries 10 random walks and then just errors out. That's by design, so one solution would be to just document the implementation as a random algorithm with a non-zero probability of failure.

[Georgi Guninski]

On second thought this is not a bug but a feature,
but I recommend the documentation should make it clear
that solution might exist.

Since the lambda log uses random integers, it depends on the
current state of the pseudo random generator and different
states might give result or a failure

I reproduced it on the sagecell web interface.

Can you reproduce it if try say 40 `set_random_seed(i)`
and try different primes `p` and `X`?

> That's an ... interesting ... way to do a division, but sure: also in prime cy> clic groups represented as an additive group discrete log algorithms should work.

Indeed, I make this on purpose :)
It doesn't need prime additive groups, works for composite `p`
and I find it interesting that the multiplicative inverse in a ring
gives solution to the additive log.

If A=X*g then A*g^-1=X mod p.