d = 0 when solving discrete logarithms with x = 1

[LukasMansour]

Hi again,

when I try to solve DLPs with x = 1, e.g. 3^d = 1 mod 7 .

I would expect d = 6 as it is the smallest positive integer for r.

However, I receive d = 0.

Example output from my DLP circuit (3^d = 1 mod 7): {'000 001': 125, '000 100': 209, '000 101': 122, '000 111': 130, '000 011': 127, '000 110': 52, '000 010': 67, '000 000': 168}

My code (it uses g^x = b convention):

from quaspy.logarithmfinding.general.postprocessing import solve_j_k_for_d_given_r

fail_count = 0
success_count = 0
x = -1

for (j, k, freq) in result_list: # note I converted it to [(j,k,freq)] correctly.
    x_cand = solve_j_k_for_d_given_r(j, k, n, 0, n, IntegerModRingMulSubgroupElement(g, p),
                                     IntegerModRingMulSubgroupElement(b, p), r)
    print(x_cand) # All solutions are 0 from Quaspy??
    if x_cand is not None and ((g ** x_cand) % p) == b:
        if x != -1:
            x = min(x, int(x_cand))
        else:
            x = int(x_cand)
        success_count += freq
    else:
        fail_count += freq

print("num_fail:", fail_count)
print("num_success:", success_count)
print({"x": x, "success_probability": success_count / shots})
print(f"x={x}")

[ekera]

Unfortunately, I am very busy at the moment with research-related work, so I am quite limited in how much time I can spend on providing support for Quaspy. This being said, the logarithm returned is on the interval $[0, r)$, for $r = 6$ the order of $g = 3$ modulo $p = 7$, so Quaspy will return $0$ in this case. Hence, I believe that what you observe is correct.

If you wish to find the order of $3$ modulo $7$, you should use order finding instead of logarithm finding.

[LukasMansour]

Using order finding for the special case when b == 1, solved the issue, thank you :).

I think there is avenue to argue the logarithm should be in the interval [1, r], but this solution is perfectly fine.

Thank you for your timely responses and good luck with your research!

[ekera]

Sure!

I think there is avenue to argue the logarithm should be in the interval [1, r], but this solution is perfectly fine.

The post-processing requires the order $r$ to be known, and it works modulo $r$, so it is natural that the interval would be $[0, r)$. This is also the case for Shor's original post-processing.

If you wish, you can of course check if the solution is $0$, and if so instead return $r$, but since $r$ is assumed known here it would in that case be easier to check whether $x = 1$ before running the quantum algorithm in the first place, and if so return $0$ or $r$ according to your preference. In short, it is a fairly special case that you are considering here — given that the algorithm assumes the order $r$ to be known.