Bug in `discrete_log(...,bounds=(1,p.isqrt()))`

[Georgi Guninski]

I think this is bug:

p=2**61-1;Kp=GF(p);g=Kp(3);X=p//3;a=g**X
dl=discrete_log(a,g,bounds=(1,p.isqrt()),algorithm="lambda",operation="*")
dl2=discrete_log(a,g,bounds=(1,p),algorithm="lambda",operation="*")
(g**dl==a,g**dl2==a)

#(False, True)

[Gareth Ma]

I think so too. Here's a more minimal version (note a == 1 in your example):

p = 31
g = GF(31)(3)
discrete_log(1, g, bounds=(1, 6), algorithm="lambda", operation="*")
# 6
g^6
# 16

It seems there's some serious bugs going on, as the return value isn't in the
bounds:

K = GF(2^61 - 1)
d = discrete_log(K(1), K(3), bounds=(1,2^30), algorithm="lambda", operation="*")
d <= 2^30
# False

Instead, the algorithm should error out, since number theory shows there's no
non-zero (mod 2^61 - 2) solution to 3^a = 1 mod (2^61 - 1)

[Georgi Guninski]

> Instead, the algorithm should error out, since number theory shows there's no
> non-zero (mod 2^61 - 2) solution to 3^a = 1 mod (2^61 - 1)

Why do you reduce (mod p-1)?
(p-1) is valid integer solution by Euler's theorem.

[Georgi Guninski]

I think the problem is abusing the factorization of the group order
and later doing CRT.

The following code correctly raises exception:

dl3=discrete_log_lambda(a,g,bounds=(1,p.isqrt()))
ValueError: Pollard Lambda failed to find a log

[dmo...@deductivepress.ca]

I opened an issue at github #38316. Let's continue the discussion there.

[Georgi Guninski]

I don't want to log to github, but the expected behavior of raising
exception if there is no solution in the bound is entirely correct
despite the doubtful comment.
The running times of some of the algorithms heavily depend on the
bounds and it is significantly faster if the bound is small.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/cd319d22-e0ac-45fe-963e-5d6e481615f9n%40googlegroups.com.