Discrete Logarithm

View on GitHub

Open this notebook in GitHub to run it yourself

The Discrete Logarithm Problem [1] was shown by Shor [2] to be solved in a polynomial time using quantum computers, while the fastest classical algorithms take a superpolynomial time. The problem is at least as hard as the factoring problem. In fact, the hardness of the problem is the basis for the Diffie-Hellman [3] protocol for key exchange. The algorithm is a specific instance of the Abelian Hidden Subgroup Problem [4]. The algorithm treats the following problem:

Input: A cyclic group $G = \langle g \rangle$ with a generator $g\in G$ , an element $x\in G$ and the order of the group is known $r=|G|$ . A quantum oracle $U_f$ applying the transformation

U_f|\alpha\rangle |\beta\rangle |0\rangle = |\alpha\rangle |\beta\rangle |f(\alpha, \beta)\rangle~~,

where

f(\alpha, \beta) = x^\alpha g^\beta

with

\alpha, \beta \in \mathbb{Z}_r

Promise: There is a positive integer $s\in \mathbb{N}$ such that $g^s = x$ .

Output: The least positive integer $s = \log_g x$ , i.e, the discrete logarithm.

Complexity: A single application of the algorithm succeeds with probability $O(\log \log r)$ and requires $O((\log t)^2)$ time, where $t = \lceil \log r +\log(1/\epsilon) \rceil$ and $1-\epsilon$ is success probability. Hence, boosting the success probability to a constant $O(1)$ via repetition yields a total expected runtime of

O((\log t)^2 \log \log r)~.

Keywords: Abelain Hidden subgroup problem, quantum Fourier transform, period finding.

Algorithm Steps

We first consider the case where

r=2^m

and later generalize. We begin by introducing an input state

|\psi_0\rangle = |0^m\rangle|0^m\rangle|0^R\rangle~~,

where

R

is the number of bits required to represent

f

‘s image. In addition, we note that

f(\alpha,\beta) = x^\alpha g^\beta = g^{\alpha\log_g x + \beta}

is constant on lines satisfying

\{(\alpha,\beta)\in \mathbb{Z}_r^2, \alpha\log_g x + \beta = \lambda \mod r\}~.

The algorithm includes four main steps, and has a similar structure to the other quantum algorithms for the hidden subgroup problem.

We first prepare a uniform superposition over the input states of the first two registers:

|0^m\rangle|0^m\rangle|0^m\rangle \xrightarrow{H^{\otimes m}} \frac{1}{r}\sum_{\alpha,\beta \in \mathbb{Z}_r}|\alpha \rangle |\beta \rangle |0^m\rangle ~~.

Perform a query to the oracle

\xrightarrow{U_f} \frac{1}{r}\sum_{\alpha, \beta \in \mathbb{Z}_r}|\alpha \rangle |\beta \rangle |f(\alpha, \beta)\rangle~~.

Utilizing the periodicity of

f

, we can express the state as

= \frac{1}{r}\sum_{\alpha, \lambda \in \mathbb{Z}_r}|\alpha \rangle |\lambda -\alpha \log_g x \rangle |g^{\lambda}\rangle~~.

Perform a double inverse Fourier transform over the group $\mathbb{Z}_r$

\xrightarrow{\text{QFT}_{\mathbb{Z}_r}^\dagger \times \text{QFT}_{\mathbb{Z}_r}^\dagger } \frac{1}{r^2}\sum_{\lambda, \mu, \nu \in \mathbb{Z}_r}\left(\sum_\alpha e^{-i 2\pi \alpha(\mu - \nu \log_g x)/r}\right)e^{-i 2\pi \lambda \nu/r}|\mu \rangle |\nu \rangle |g^{\lambda}\rangle

= \frac{1}{r}\sum_{\lambda, \nu \in \mathbb{Z}_r}e^{i 2\pi \lambda \nu/r}|\nu \log_g x \rangle |\nu \rangle |g^{\lambda}\rangle~~,

where the Fourier transform over

\mathbb{Z}_r

\text{QFT}_{\mathbb{Z}_r} |\alpha \rangle = \frac{1}{\sqrt{r}}\sum_{\mu\in \mathbb{Z}_r} e^{i 2\pi \alpha \mu/r}|\mu \rangle

and in the second line we utilized the identity

\sum_\alpha e^{i 2\pi \alpha \eta} = r \delta_{0\eta}

(easily derived by use of a sum over a geometric series). 4. Measure the three quantum variables. The measurement of the third variable collapses the quantum state to

|g^\lambda \rangle

with a uniform distribution. After the collapse, the resulting state is independent of

\lambda

, therefore, we can discard this measurement outcome. From the measurement of the second quantum variable, we obtain with a uniform distribution over

\nu

the outcome

\nu \log_g x

. With a probablility of order

O(\log \log r)

, the obtained result

\nu

is co-prime to

r

, and there exists a modular

r

multiplicative inverse

\nu^{-1}

. Under this condition, we can multiply the outcome of the second register to obtain the discrete log

s=\log_g x

. Hence, repeating the experiment

O(\log \log r)

times leads to a success probability of order

O(1)

Building the Algorithm with Classiq

We begin by importing software packages

import matplotlib.pyplot as plt
import numpy as np

from classiq import *
from classiq.qmod.symbolic import ceiling, log

We consider two exemplary cases. First, we study the group

\mathbb{Z}_5^\times

, where the order is a power of

r=4=2^2

. For this case, quantum variables with only

\log r = m

qubits are required. Following, the group

\mathbb{Z}_{13}^\times

exemplifies the alternative case where the order

r\neq 2^m

for an integer

m

. For these examples, we denote the modulus by

N

. Since, these are cyclic groups, we have

N = r+1

, therefore

R = \lceil \log N\rceil

. In the following examples, the third register, containing the function

f(\alpha, \beta )

after the second step, is represented by

\lceil \log N\rceil

. The heart of the algorithm’s logic is the implementation of the function

|\alpha \rangle|\beta \rangle|0\rangle \rightarrow |\alpha \rangle|\beta \rangle|x^{\alpha } g^{\beta}\rangle~.

This is done using two applications of the modular exponentiation function, described in detail in the Shor’s Factoring Algorithm notebook. So here we import it from the Classiq library. The modular_exponentiation function defined below accepts these arguments:

N: CInt - modulo number
a: CInt - base of the exponentiation
x: QArray[QBit] - unsigned integer to multiply by the exponentiation
pw: QArray[QBit]- power of the exponentiation

So the function implements

|pw\rangle|x\rangle \rightarrow |pw\rangle|x \cdot a ^ {pw}\mod N\rangle

from classiq import *


@qfunc
def modular_exponentiation(N: CInt, a: CInt, x: QArray, pw: QArray):
    repeat(
        count=pw.len,
        iteration=lambda index: control(
            pw[index],
            # lambda: inplace_modular_multiply(N, (a ** (2**index)) % N, x),  #modular_multiply_constant_inplace
            lambda: modular_multiply_constant_inplace(N, a ** (2**index), x),
        ),
    )


@qfunc
def discrete_log_oracle(
    g_generator: CInt,
    x_element: CInt,
    N_modulus: CInt,
    alpha: QArray,
    beta: QArray,
    func_res: Output[QNum],
) -> None:
    allocate(ceiling(log(N_modulus, 2)), func_res)

    func_res ^= 1
    modular_exponentiation(N_modulus, x_element, func_res, alpha)
    modular_exponentiation(N_modulus, g_generator, func_res, beta)

Full Algorithm

Prepare a uniform superposition over the first two quantum variables alpha, beta.

Each variable has size

\lceil \log r\rceil + \log({1/{\epsilon}})

. In the special case where

r

is a power of 2,

\log r

is enough.

Compute discrete_log_oracle on the func_res variable. func_res is of size $\lceil \log N\rceil$ .
Apply the inverse Fourier transform alpha, beta.
Measure.

@qfunc
def discrete_log(
    g: CInt,
    x: CInt,
    N: CInt,
    order: CInt,
    alpha: Output[QArray],
    beta: Output[QArray],
    func_res: Output[QArray],
) -> None:
    reg_len = ceiling(log(order, 2))
    allocate(reg_len, alpha)
    allocate(reg_len, beta)

    hadamard_transform(alpha)
    hadamard_transform(beta)

    discrete_log_oracle(g, x, N, alpha, beta, func_res)

    invert(lambda: qft(alpha))
    invert(lambda: qft(beta))

After the inverse QFTs (under the assumption of

r=2^m

for some

m

, therefore

t=2^r

), the variables become

|\psi\rangle = \frac{1}{r}\sum_{\lambda, \nu \in \mathbb{Z}_r}e^{i 2\pi \lambda \nu/r}|\nu \log_g x \rangle_{\alpha} |\nu \rangle_{\beta} |g^{\lambda}\rangle_{\text{res}}

where we added a subscript to the quantum variables for clarity, and

| \rangle_{\text{res}}

designates the func_res variable. If

\nu\in \mathbb{Z}_r

has an inverse,

\nu^{-1}\in\mathbb{Z}_r

we can extract

s=\log_x g

from variable

\alpha

by multiplying by

\nu^{-1}

. See the second example for the general case, for which

r \neq 2^m

Example: $G = \mathbb{Z}_5^\times$

For this specific demonstration, we choose

G = \mathbb{Z}_5^\times

, with

g=3

and

x=2

. With this setting,

\log_gx=3

. We choose this specific example because the order of the group

r=4

is a power of

2

, so we can get the exact discrete logarithm without continued-fractions postprocessing. In other cases, we use a larger quantum variable for the exponents so the continued fractions postprocessing converges.

MODULU_NUM = 5
G_GENERATOR = 3
X_LOG_ARG = 2
ORDER = MODULU_NUM - 1  # as 5 is prime


@qfunc
def main(
    alpha: Output[QNum],
    beta: Output[QNum],
    func_res: Output[QNum],
) -> None:
    discrete_log(G_GENERATOR, X_LOG_ARG, MODULU_NUM, ORDER, alpha, beta, func_res)

qmod_Z5 = create_model(
    main,
    constraints=Constraints(max_width=13),
    preferences=Preferences(optimization_level=1),
)

qprog_Z5 = synthesize(qmod_Z5)
show(qprog_Z5)

Output:

Quantum program link: https://platform.classiq.io/circuit/3IivFINb5QCLsF8uvcO5VOPSALJ
  

Output:

https://platform.classiq.io/circuit/3IivFINb5QCLsF8uvcO5VOPSALJ?login=True&version=22
  

df_Z5 = sample(qprog_Z5, num_shots=4000)
df_Z5

Output:


Submitting job to simulator

Output:


Job: https://platform.classiq.io/jobs/58813779-befe-414d-888b-c4c44b0cd9e1

	alpha	beta	func_res	counts	probability	bitstring
0	1	3	1	271	0.06775	0011101
1	3	1	2	269	0.06725	0100111
2	0	0	3	269	0.06725	0110000
3	3	1	1	267	0.06675	0010111
4	1	3	3	260	0.06500	0111101
5	0	0	4	258	0.06450	1000000
6	1	3	4	258	0.06450	1001101
7	1	3	2	255	0.06375	0101101
8	2	2	2	248	0.06200	0101010
9	3	1	3	244	0.06100	0110111
10	2	2	4	243	0.06075	1001010
11	0	0	2	238	0.05950	0100000
12	0	0	1	234	0.05850	0010000
13	2	2	3	231	0.05775	0111010
14	3	1	4	230	0.05750	1000111
15	2	2	1	225	0.05625	0011010

Note that func_res is uncorrelated to the other variables, and we get uniform distribution, as expected. We take only the beta that are co-prime to

r=4

, so they have a multiplicative-inverse. Hence beta=1,3 are the relevant results. So we get two relevant results (for all different

\lambda

s):

|1\rangle|3\rangle

|3\rangle|1\rangle

. All that remains to get the logarithm is to multiply alpha by the inverse of beta:

for _, res in df_Z5.iterrows():
    if res["beta"] in [1, 3]:
        logarithm = res["beta"] * pow(res["alpha"], -1, 4)
        assert logarithm == 3

Verify we received the correct discrete logarithm:

log_arg = (G_GENERATOR**logarithm) % MODULU_NUM
print(log_arg)
assert log_arg == X_LOG_ARG

Output:

And, indeed, both cases give the same result, which is exactly the discrete logarithm:

\log_32 \mod 5 = 3

Generalization for the Case Where $r\neq 2^m$

For an arbitrary

r\in \mathbb{N}

, we employ two

t=\lceil \log r\rceil + \log (1/\epsilon)

qubit quantum variables and a third

R

-qubit register, initialized to the state

|\psi_0\rangle = |0^t\rangle|0^t\rangle|0^R\rangle

, where

R = \lceil \log N\rceil

. The derivation follows a similar structure, where the initial sums are now

\alpha, \beta \in \mathbb Z_T

, with

T=2^t

, while the period of

f

remains

r

, i.e.,

\lambda\in \mathbb{Z}_r

. Therefore, after the second step we obtain the state

\frac{1}{T}\sum_{\alpha,\beta \in \mathbb{Z}_T}|\alpha\rangle|\beta\rangle|0^R\rangle\xrightarrow{U_f} \frac{1}{T}\sum_{\alpha,\beta\in \mathbb{Z}_T}|\alpha \rangle |\beta\rangle |g^{\alpha \log_g x + \beta}\rangle~~.

Next, we express the periodic state in an alternative form. We introduce the operator

U_g

, which satisfies

U_g |h\rangle= |h g\rangle

, where

e

is the identity element of the group. Therefore

|{g^\lambda}\rangle = U_g^\lambda |e \rangle

. The state

|e\rangle

can be expressed as a uniform superposition of the eigenstates of

U_g

|e \rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1} |\Psi_k\rangle~~,

where

| \Psi_k \rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{i2\pi k k'/r}| g^{k'}\rangle

, which satisfy

U_g | \Psi_k \rangle = e^{i 2\pi k/r}| \Psi_k\rangle

. These relations allow writing the state after the oracle operation as

\frac{1}{T}\sum_{\alpha,\beta\in \mathbb{Z}_T}|\alpha \rangle |\beta\rangle \sum_{k=0}^{r-1}e^{i 2\pi (\alpha \log_g x + \beta) k/r }|\Psi_k\rangle~~.

Applying the inverse quantum Fourier transform leads to the state

\xrightarrow{\text{QFT}_T^\dagger \times \text{QFT}_T^\dagger}\frac{1}{T}\sum_{k=0}^{r-1}\sum_{\mu,\nu\in \mathbb{Z}_T}\left(\sum_{\alpha\in \mathbb{Z}_T} e^{i 2\pi \alpha (\log_g x k/r-\mu/T) }| \mu\rangle\right)\left( \sum_{\beta\in \mathbb{Z}_T} e^{i 2\pi \beta (k/r-\nu /T) }| \nu \rangle \right)|\Psi_k\rangle~~.

Utilizing the geometric sum, one can show that the functions are peaked (with a width

O(1/T)

) around

\mu \approx T\log_g x k/r

and

\nu \approx T k / r

, correspondingly. To evaluate the values of

k \log_g x

and

k

we measure alpha and beta registers, multiply by

r/N

and round. For sufficiently large

T

, we obtain the correct value for

s=\log_g x

with high probability. Alternatively, one can apply the continued fraction algorithm [5] to evaluate

s

, see [6] for further details. Note: Alternatively, you could implement the $\text{QFT}_{\mathbb{Z}_r}$ over general $r$ , and instead of the uniform superposition, prepare the states: $\frac{1}{\sqrt{r}}\sum_{x\in\mathbb{r}}|x\rangle$ in alpha, beta. Then, again, no continued fractions postprocessing is required.

Example: $G = \mathbb{Z}_{13}^\times$

MODULU_NUM = 13
G_GENERATOR = 7
X_LOG_ARG = 3
ORDER = 12


@qfunc
def discrete_log(
    g: CInt,
    x: CInt,
    N: CInt,
    order: CInt,
    alpha: Output[QNum],
    beta: Output[QNum],
    func_res: Output[QNum],
) -> None:
    reg_len = ceiling(log(order, 2)) + 1
    # we define the variables with fraction places to ease the postprocessing
    allocate(reg_len, False, reg_len, alpha)
    allocate(reg_len, False, reg_len, beta)

    hadamard_transform(alpha)
    hadamard_transform(beta)

    discrete_log_oracle(g, x, N, alpha, beta, func_res)

    invert(lambda: qft(alpha))
    invert(lambda: qft(beta))


@qfunc
def main(
    alpha: Output[QNum],
    beta: Output[QNum],
    func_res: Output[QNum],
) -> None:
    discrete_log(G_GENERATOR, X_LOG_ARG, MODULU_NUM, ORDER, alpha, beta, func_res)

constraints = Constraints(max_width=23)
preferences = Preferences(optimization_level=1)
qmod_Z13 = create_model(
    main,
    constraints=constraints,
    preferences=preferences,
    out_file="discrete_log",
)

qprog_Z13 = synthesize(qmod_Z13)
show(qprog_Z13)

Output:

Quantum program link: https://platform.classiq.io/circuit/3IivJLlJ303vMCfFXfvqLBIj2zs
  

Output:

https://platform.classiq.io/circuit/3IivJLlJ303vMCfFXfvqLBIj2zs?login=True&version=22
  

df = sample(qprog_Z13, num_shots=10000)
df.head(10)

Output:


Submitting job to simulator

Output:


Job: https://platform.classiq.io/jobs/c559a7ae-41ba-4329-9337-abc77ed6f24f

	beta	func_res	counts	probability	bitstring
0	0.75	1	92	0.0092	00011100000000
1	0.00	4	86	0.0086	01000000000000
2	0.50	2	85	0.0085	00101000000000
3	0.00	7	80	0.0080	01110000000000
4	0.50	7	78	0.0078	01111000000000
5	0.25	9	78	0.0078	10010100000000
6	0.25	6	77	0.0077	01100100000000
7	0.75	6	76	0.0076	01101100000000
8	0.50	9	76	0.0076	10011000000000
9	0.00	6	75	0.0075	01100000000000

Postprocessing

We now have an additional step in postprocessing. We translate each result to the closest fraction with a denominator, which is the order:

def closest_fraction(x, denominator):
    return round(x * denominator)


df["alpha_rounded"] = closest_fraction(df.alpha, ORDER)
df["beta_rounded"] = closest_fraction(df.beta, ORDER)
df.head(10)

	beta	func_res	counts	probability	bitstring	beta_rounded
0	0.75	1	92	0.0092	00011100000000	9.0
1	0.00	4	86	0.0086	01000000000000	0.0
2	0.50	2	85	0.0085	00101000000000	6.0
3	0.00	7	80	0.0080	01110000000000	0.0
4	0.50	7	78	0.0078	01111000000000	6.0
5	0.25	9	78	0.0078	10010100000000	3.0
6	0.25	6	77	0.0077	01100100000000	3.0
7	0.75	6	76	0.0076	01101100000000	9.0
8	0.50	9	76	0.0076	10011000000000	6.0
9	0.00	6	75	0.0075	01100000000000	0.0

Now, we take a sample where beta is co-prime to the order, such that we can get the logarithm by multiplying alpha by the modular inverse. If the alpha, beta registers are large enough, we are guaranteed to sample it with a good probability:

import numpy as np


def modular_inverse(x):
    return [pow(a, -1, ORDER) for a in x]


df = df[np.gcd(df.beta_rounded.astype(int), ORDER) == 1].copy()
df["beta_inverse"] = modular_inverse(df.beta_rounded.astype("int"))
df["logarithm"] = df.alpha_rounded * df.beta_inverse % ORDER
df.head(10)

	alpha	beta	func_res	counts	probability	bitstring	alpha_rounded	beta_rounded	beta_inverse	logarithm
48	0.65625	0.09375	5	47	0.0047	01010001110101	8.0	1.0	1	8.0
52	0.34375	0.90625	10	42	0.0042	10101110101011	4.0	11.0	11	8.0
53	0.34375	0.40625	3	41	0.0041	00110110101011	4.0	5.0	5	8.0
54	0.34375	0.40625	6	41	0.0041	01100110101011	4.0	5.0	5	8.0
56	0.65625	0.09375	9	40	0.0040	10010001110101	8.0	1.0	1	8.0
58	0.34375	0.90625	8	39	0.0039	10001110101011	4.0	11.0	11	8.0
60	0.34375	0.90625	1	38	0.0038	00011110101011	4.0	11.0	11	8.0
61	0.34375	0.90625	2	38	0.0038	00101110101011	4.0	11.0	11	8.0
64	0.34375	0.90625	5	37	0.0037	01011110101011	4.0	11.0	11	8.0
65	0.65625	0.59375	8	37	0.0037	10001001110101	8.0	7.0	7	8.0

print(f"The descrite logarithm is: {df.logarithm[:1].iloc[0]}")

Output:


The descrite logarithm is: 8.0

To verify the results, we check whether

g^s \mod N = g^{\log_g x}\mod N = x

assert len(df.logarithm) > 0
assert np.allclose(G_GENERATOR ** df.logarithm[:10] % MODULU_NUM, X_LOG_ARG)

Measurement Distribution Heuristic Plots

The expected measurement results are showcased by plotting the theoretical probability distributions of the

\alpha

and

\beta

quantum variables, for varying numbers of qubits

t=5

and

t=8

and the specific case of

k=5

. Since

r = 12 \neq 2^m

for some integer

m

, we obtain a probability distribution characterized by a narrow peak of width

\sim 1/T

. As the number of qubits is increased,

T=2^t

increases, the probability distribution becomes narrower. Therefore, improving the success probability.

MODULU_NUM = 13
X_LOG_ARG = 3

t = np.ceil(np.log2(ORDER)) + 1
T = 2**t
k = 5
r = ORDER
x_data = np.arange(T)

x0_mu = k * T / r
amplitudes_mu = np.sin(np.pi * (x_data - x0_mu)) / (
    T * np.sin(np.pi * (x_data - x0_mu) / T)
)
probabilities_mu = np.abs(amplitudes_mu) ** 2
probabilities_mu /= np.sum(probabilities_mu)


s = np.log(X_LOG_ARG) / np.log(G_GENERATOR)  # same as log_{G_GENERATOR}(X_LOG_ARG)
x0_nu = s * k * T / r
amplitudes_nu = np.sin(np.pi * (x_data - x0_nu)) / (
    T * np.sin(np.pi * (x_data - x0_nu) / T)
)
probabilities_nu = np.abs(amplitudes_nu) ** 2
probabilities_nu /= np.sum(probabilities_nu)

# Create figure and axis with custom size
fig, ax = plt.subplots(figsize=(8, 6))

# Plot data
ax.plot(x_data, probabilities_mu, label="alpha")
ax.plot(x_data, probabilities_nu, "r-.", label="beta")


# Customize axis labels and title font sizes
ax.set_xlabel("mu and nu values", fontsize=14)
ax.set_ylabel("", fontsize=14)
ax.set_title("Probabilities the Alpha and Beta Registers, t=5", fontsize=16)

# Increase tick label (axis numbers) size
ax.tick_params(axis="both", labelsize=12)


# Show legend
ax.legend(fontsize=12, loc="best")

# Display the plot
plt.show()

MODULU_NUM = 13
X_LOG_ARG = 3

t = np.ceil(np.log2(ORDER)) + 4
T = 2**t
k = 5
r = ORDER
x_data = np.arange(T)

x0_mu = k * T / r
amplitudes_mu = np.sin(np.pi * (x_data - x0_mu)) / (
    T * np.sin(np.pi * (x_data - x0_mu) / T)
)
probabilities_mu = np.abs(amplitudes_mu) ** 2
probabilities_mu /= np.sum(probabilities_mu)

s = np.log(X_LOG_ARG) / np.log(G_GENERATOR)  # same as log_{G_GENERATOR}(X_LOG_ARG)
x0_nu = s * k * T / r
amplitudes_nu = np.sin(np.pi * (x_data - x0_nu)) / (
    T * np.sin(np.pi * (x_data - x0_nu) / T)
)
probabilities_nu = np.abs(amplitudes_nu) ** 2
probabilities_nu /= np.sum(probabilities_nu)
# Create figure and axis with custom size
fig, ax = plt.subplots(figsize=(8, 6))

# Plot data
ax.plot(x_data, probabilities_mu, label="alpha")
ax.plot(x_data, probabilities_nu, "r-.", label="beta")


# Customize axis labels and title font sizes
ax.set_xlabel("mu and nu values", fontsize=14)
ax.set_ylabel("", fontsize=14)
ax.set_title("Probabilities the Alpha and Beta Registers, t=8", fontsize=16)

# Increase tick label (axis numbers) size
ax.tick_params(axis="both", labelsize=12)


# Show legend
ax.legend(fontsize=12, loc="best")

# Display the plot
plt.show()

Technical Notes

Equivalence with the Abelian Subgroup Problem

The discrete logarithm is a specific case of the Hidden Subgroup Problem (HSP) [4]. The HSP can be stated as follows: Let

G

be a group and

H

is subgroup of

G

. We are given an (oracle) function

f

with the promise that:

$f$ is constant on the right cosets of $H$ .
Elements of distinct cosets produce different oracle values.

That is for

g\in G

if and only if

x,y\in g H

f(x) = f(y)

. Goal: Identify a generating set for the subgroup

H

; that is, a collection of elements of

H

whose products yield every element of the subgroup. Note, that there is always a generating set of size

\Omega(\log(|H|))

. The discrete logarithm problem is an instance of the Abelian HSP.

$G$ is the additive group $\mathbb{Z}_N\times \mathbb{Z}_N$ .
The hidden subgroup is $H = \{(0,0), (1,-\log_g x),(2,-2\log_g x,\dots, (r-1,-(r-1)\log_g x))\}$ .
The cosets are the of the form $\{(\alpha, \lambda + \alpha\log_x g)\}$ , where $\lambda \in \mathbb{Z}_r$ . It is straightforward to show that $f(\alpha,\beta) = g^\lambda$ for all elements of the coset.

Solution of the HSP provides a generator of

(\nu, -\nu\log_g x)

, for

\nu

coprime to

r

, which allows evaluating the discrete logarithm by taking the modular inverse of

\nu

s=-\nu^{-1}\nu \log_g x

The Diffie-Hellman protocol enables two parties (“Alice” and “Bob”) to establish a shared secret key, and its security against an eavesdropper (“Eve”) relies on the computational hardness of the discrete logarithm problem. The protocol for sharing a secret key includes the following steps:

A prime $p$ and a generator $g$ of a multiplicative group mod $p$ , are published publicly.
Alice chooses a number $a\in \mathbb{Z}_p$ and computes $A = g^a$ . $a$ is known only to Alice.
Bob chooses a number $b\in \mathbb{Z}_p$ and computes $B = g^a$ . $b$ is known only to Bob.
Alice sends Bob a message over a public channel containing $A$ , Bob sends Alice a message containing $B$ .
Alice computes the secret key $K = B^a = g^{ab}$ , and similarly Bob computes the secret key $K=A^b = g^{ab}$ .

If the eavesdropper, Eve, can implement the discrete logarithm algorithm, she can evaluate

a=\log_g(A)

and

b = \log_g(B)

, by intercepting Alice’s and Bob’s messages,

A

and

B

. Knowledge of

a

b

and

g

allows her a straightforward calculation of

K=g^{ab}

. a

References

[1]: Discrete Logarithm (Wikipedia) [2]: Shor, Peter W. “Algorithms for quantum computation: discrete logarithms and factoring.” Proceedings 35th annual symposium on foundations of computer science. IEEE, 1994. [3]: Diffie-Hellman Key Exchange (Wikipedia) [4]: Hidden Subgroup Problem (Wikipedia) [5]: Continued Fraction (Wikipedia) [6]: Proos, J., & Zalka, C. (2003). Shor’s discrete logarithm quantum algorithm for elliptic curves. arXiv preprint quant-ph/0301141

Algorithms

Applications

Tutorials

View on GitHub

Algorithm Steps

Building the Algorithm with Classiq

Full Algorithm

Example: $G = \mathbb{Z}_5^\times$

Generalization for the Case Where $r\neq 2^m$

Example: $G = \mathbb{Z}_{13}^\times$

Postprocessing

Measurement Distribution Heuristic Plots

Technical Notes

Equivalence with the Abelian Subgroup Problem

References

View on GitHub

​Algorithm Steps

​Building the Algorithm with Classiq

​

​Full Algorithm

​Example: G=Z5×G = \mathbb{Z}_5^\timesG=Z5×​

​Generalization for the Case Where r≠2mr\neq 2^mr=2m

​Example: G=Z13×G = \mathbb{Z}_{13}^\timesG=Z13×​

​

​Postprocessing

​

​Measurement Distribution Heuristic Plots

​Technical Notes

​

​Equivalence with the Abelian Subgroup Problem

​

​Diffie-Hellman Secret Key Sharing Protocol

​References

Algorithm Steps

Building the Algorithm with Classiq

Full Algorithm

Example: $G = \mathbb{Z}_5^\times$

Generalization for the Case Where $r\neq 2^m$

Example: $G = \mathbb{Z}_{13}^\times$

Postprocessing

Measurement Distribution Heuristic Plots

Technical Notes

Equivalence with the Abelian Subgroup Problem

Diffie-Hellman Secret Key Sharing Protocol

References