Discrete Log (DLog)

Dlog algorithms for Quantum Threat Tracker.

class DLogSafePrimeEH(crypt_params: CryptParams, alg_params: DLogSafePrimeEHParams | None = None)[source]

Bases: QuantumAlgorithm

Class for the implementation of Ekerå-Håstad algorithm.

for dlog problems in safe prime groups.

Method based on Ekerå-Håstad’s improvements to Shor’s algorithm.

Initialize the quantum algorithm.

Parameters:

  • crypt_params (CryptParams) – Cryptographic parameters.

  • alg_params (Optional[DLogSafePrimeEHParams], optional) – Algorithmic parameters for discrete logarithm problems.

static generate_search_space() → list[DLogSafePrimeEHParams][source]

Generate a search space for algorithm parameters.

Returns:

List of parameters for different window size combinations.

Return type:

list[DLogSafePrimeEHParams]

get_algorithm_summary(alg_params: AlgParams | None = None) → AlgorithmSummary[source]

Compute logical resource estimates for the circuit.

Parameters:

alg_params (Optional[AlgParams], optional) – Algorithm parameters

Returns:

Logical resource estimates.

Return type:

AlgorithmSummary

Raises:

  • NameError – If the protocol is not “DH-SP”.

  • TypeError – If alg_params is not of type DLogSafePrimeEHParams.

class DLogSafePrimeEHParams(window_size_exp: int, window_size_mul: int)[source]

Bases: AlgParams

Parameters for discrete logarithm implementation using Ekerå-Håstad algorithm.

In discrete logarithm problems with safe-prime groups, the order is n-1 where n is the modulus bit length. With short exponent: nd = 2z.

Note: This implementation focuses only on short exponents in safe-prime groups using the Ekerå-Håstad approach.

window_size_exp: int
window_size_mul: int
class DLogSafePrimeShor(crypt_params: CryptParams, alg_params: DLogSafePrimeShorParams | None = None)[source]

Bases: QuantumAlgorithm

Class for the implementation of Shor’s algorithm for dlog problems.

Method from https://github.com/Strilanc/efficient-quantum-factoring-2019/.

Initialize the quantum algorithm.

Parameters:

  • crypt_params (CryptParams) – Cryptographic parameters.

  • alg_params (Optional[DLogSafePrimeShorParams], optional) – Algorithmic parameters for discrete logarithm problems.

static generate_search_space() → list[DLogSafePrimeShorParams][source]

Generate a search space for algorithm parameters.

Returns:

List of parameters for different window size combinations.

Return type:

list[DLogSafePrimeShorParams]

get_algorithm_summary(alg_params: AlgParams | None = None) → AlgorithmSummary[source]

Compute logical resource estimates for the circuit.

Parameters:

alg_params (Optional[AlgParams], optional) – Algorithm parameters

Returns:

Logical resource estimates.

Return type:

AlgorithmSummary

Raises:

  • NameError – If the protocol is not “DH-SC”.

  • TypeError – If alg_params is not of type DLogSafePrimeShorParams.

class DLogSafePrimeShorParams(window_size_exp: int, window_size_mul: int)[source]

Bases: AlgParams

Parameters for discrete logarithm implementation using Shor’s algorithm.

In discrete logarithm problems, we have two main group types: - Schnorr group: order r with nd = nr = 2z (where z is bits of classical security) - Safe-prime group: order n-1 where n is the modulus bit length with short exponent: nd = 2z

Note: This implementation focuses only on short exponents in safe-prime groups.

window_size_exp: int
window_size_mul: int
class DLogSchnorrEH(crypt_params: CryptParams, alg_params: DLogSchnorrEHParams | None = None)[source]

Bases: QuantumAlgorithm

Class for the implementation of Ekerå-Håstad algorithm.

for dlog problems in Schnorr groups.

Method based on Ekerå-Håstad’s improvements to Shor’s algorithm.

Initialize the quantum algorithm.

Parameters:

  • crypt_params (CryptParams) – Cryptographic parameters.

  • alg_params (Optional[DLogSchnorrEHParams], optional) – Algorithmic parameters for discrete logarithm problems.

static generate_search_space() → list[DLogSchnorrEHParams][source]

Generate a search space for algorithm parameters.

Returns:

List of parameters for different window size combinations.

Return type:

list[DLogSchnorrEHParams]

get_algorithm_summary(alg_params: AlgParams | None = None) → AlgorithmSummary[source]

Compute logical resource estimates for the circuit.

Parameters:

alg_params (Optional[AlgParams], optional) – Algorithm parameters

Returns:

Logical resource estimates.

Return type:

AlgorithmSummary

Raises:

  • NameError – If the protocol is not “DH-SCH”.

  • TypeError – If alg_params is not of type DLogSchnorrEHParams.

class DLogSchnorrEHParams(window_size_exp: int, window_size_mul: int)[source]

Bases: AlgParams

Parameters for discrete logarithm implementation using Ekerå-Håstad algorithm.

In discrete logarithm problems with Schnorr groups, the order r with nd = nr = 2z (where z is bits of classical security).

Note: This implementation focuses on Schnorr groups using the Ekerå-Håstad approach.

window_size_exp: int
window_size_mul: int
class DLogSchnorrShor(crypt_params: CryptParams, alg_params: DLogSchnorrShorParams | None = None)[source]

Bases: QuantumAlgorithm

Class for the implementation of Shor’s algorithm for dlog problems.

Method from https://github.com/Strilanc/efficient-quantum-factoring-2019/.

Initialize the quantum algorithm.

Parameters:

  • crypt_params (CryptParams) – Cryptographic parameters.

  • alg_params (Optional[DLogSchnorrShorParams], optional) – Algorithmic parameters for discrete logarithm problems.

static generate_search_space() → list[DLogSchnorrShorParams][source]

Generate a search space for algorithm parameters.

Returns:

List of parameters for different group types with short exponents.

Return type:

list[DLogSchnorrShorParams]

get_algorithm_summary(alg_params: AlgParams | None = None) → AlgorithmSummary[source]

Compute logical resource estimates for the circuit.

Parameters:

alg_params (Optional[AlgParams], optional) – Algorithm parameters

Returns:

Logical resource estimates.

Return type:

AlgorithmSummary

Raises:

  • NameError – If the protocol is not “DH-SCH”.

  • TypeError – If alg_params is not of type DLogSchnorrShorParams.

class DLogSchnorrShorParams(window_size_exp: int, window_size_mul: int)[source]

Bases: AlgParams

Parameters for discrete logarithm implementation using Shor’s algorithm.

In discrete logarithm problems, we have two main group types: - Schnorr group: order r with nd = nr = 2z (where z is bits of classical security) - Safe-prime group: order n-1 where n is the modulus bit length with short exponent: nd = 2z

Note: This implementation focuses only on short exponents.

window_size_exp: int
window_size_mul: int