Cryptology Algorithms

Overview

unitarylab_algorithms.cryptology contains three quantum cryptography algorithms that demonstrate the advantages of quantum computing over classical methods for number-theoretic and hidden-period problems:

All three algorithms inherit from unitarylab_algorithms.algo_base.BaseAlgorithm, and the return value of .run() follows a unified structure:

{
    'status': 'ok' | 'failed',   # Whether it succeeded, determined by the algorithm's own validation logic
    'circuit_path': '/path/to/xxx_circuit.svg',  # Full path to the circuit diagram; None for branches of some algorithms that do not need to build a circuit
    'plot': [{'format': 'txt', 'filename': 'xxx_algorithm_result.txt'}],  # Result text file, filename is the **filename without the directory**
    'circuit': <Circuit object or None>,
    # ... The following are algorithm-specific fields appended via update_output() (see each section)
}

Shor’s Factoring Algorithm

Background

Shor’s algorithm factors a composite number $N$ into its prime factors in polynomial time. The best classical algorithms (such as the general number field sieve) require sub-exponential time, while Shor’s algorithm can complete the task in $O((\log N{)}^3)$ time on a quantum computer.

The algorithm combines:

1. Quantum period finding based on the Quantum Fourier Transform (QFT)
2. Classical post-processing to extract the prime factors from the period

Import

from unitarylab_algorithms import ShorAlgorithm

.run() Parameters

def run(self, N: int, method: str = "matrix", max_retries: int = 15,
        backend='torch', device='cpu', dtype=np.complex128) -> Dict[str, Any]

parameters.json (the web-side parameter panel) only exposes the two parameters N (range 2–300) and method, it does not provide a UI input for max_retries; to customize the retry count you must call the Python API directly.

Execution Flow

1. Classical pre-check: if N is even, the factors [2, N//2] are returned directly; if the randomly sampled base a shares a common factor with N, classical factorization is done directly — in both of these cases no quantum circuit is built, and circuit_path is None.
2. Otherwise, a phase estimation circuit is built (method='matrix' uses a controlled permutation matrix; method='operator' uses a modular multiplier circuit, which uses more qubits but is a more “physical” circuit), and it is executed and measured.
3. Continued-fraction expansion is applied to the measurement result to extract the period $r$; if $r$ is even and $a^{r/2}\not\equiv \pm 1(\mathrm{mod}N)$, then $\gcd (a^{r/2}\pm 1,N)$ is computed to obtain the factors.
4. If a single attempt fails to extract a valid factor, the base $a$ is resampled and the process repeats, up to max_retries times.

Return Value

Consistent with other BaseAlgorithm subclasses, status truly reflects whether the algorithm succeeded in finding factors (both the classical shortcut branch and a successful quantum branch return 'ok'; if max_retries is exhausted without success it is 'failed'). The fields appended by update_output() vary by branch:

# Classical shortcut branch (N is even / the random base shares a common factor with N)
{'factors': [p, q], 'period': None, 'Selected base': a_or_None}

# Quantum branch succeeds
{
    'factors': [p, q], 'period': r, 'Selected base': a,
    'Computation time (s)': 0.1234, 'Measurement': 42, 'Total qubits': 12,
}

# Retries exhausted, still failed
{
    'factors': None, 'period': None, 'Selected base': a,
    'Computation time (s)': 0.1234, 'Measurement': 42, 'Total qubits': 12,
}

Example

from unitarylab_algorithms import ShorAlgorithm
 
algo = ShorAlgorithm()
result = algo.run(N=15)
print(result['status'])          # 'ok'
print(result['factors'])         # e.g. [3, 5]

Quick Demo

from unitarylab_algorithms.cryptology.shor.algorithm import test
test(N=15, method='matrix', max_retries=15)

Notes

• N must be a composite number with at least two distinct prime factors. Passing 1 will, on the very first attempt, cause the internal call random.randint(2, N - 1) (i.e. random.randint(2, 0)) to directly raise ValueError: empty range for randrange(), rather than entering the retry loop; passing 2 (or any other even number) will be short-circuited directly by the N % 2 == 0 branch, immediately returning status='ok' with factors=[2, N//2], and likewise will not enter the retry loop. Only passing an odd prime (such as 7) will actually enter the retry loop, ending with status='failed' after max_retries attempts are exhausted.
• The 'matrix' method directly constructs a controlled permutation matrix, using fewer qubits, suitable for small $N$; the 'operator' method uses a modular multiplier circuit, which uses more qubits.
• When N is even, or the random base happens to share a common factor with N, the algorithm takes the classical shortcut and returns directly, without building/saving a quantum circuit (circuit_path=None); in this case the return value cannot be used to judge “whether the quantum algorithm succeeded.”
• status truly reflects whether the factorization succeeded, and can be safely used for business logic decisions (this differs from the case in fundamental_algorithm where some algorithms have status that is “always 'ok'”).

Discrete Logarithm Algorithm

Background

The discrete logarithm problem: given $g$, $y$, and $P$, find $x$ such that $g^x\equiv y(\mathrm{mod}P)$. This is the security foundation of many classical cryptographic systems (such as Diffie–Hellman and DSA). The quantum algorithm uses quantum phase estimation and continued-fraction post-processing to solve it efficiently, and it executes the quantum circuit only once (unlike Shor’s algorithm, it has no retry mechanism).

Import

from unitarylab_algorithms import DiscreteLogAlgorithm

.run() Parameters

def run(self, g: int, y: int, P: int,
        backend='torch', device='cpu', dtype=np.complex128) -> Dict[str, Any]

g, y, and P have no default values in .run() and must be passed explicitly. If $\gcd (g,P)\ne 1$ or $\gcd (y,P)\ne 1$, a ValueError("g and y must be coprime with P") is raised directly.

The module-level test() function and the default example on the web-side parameters.json are inconsistent: test() defaults to g=3, y=6, P=7 (corresponding to $3^3\equiv 6(\mathrm{mod}7)$, answer $x=3$); while the default values in parameters.json are g=3, y=13, P=17. The example below uses g=3, y=6, P=7, consistent with test().

Return Value

status reflects true success/failure (is_success = found_x is not None):

{
    'status': 'ok',
    'circuit_path': '/path/to/discrete_logarithm_algorithm_circuit.svg',
    'plot': [{'format': 'txt', 'filename': 'discrete_logarithm_algorithm_result.txt'}],
    'circuit': <Circuit>,
    'Computation time (s)': 0.0456,
    'Detected period r': 3,
    'Found x': 3,
}

If the continued-fraction post-processing fails to find a solution satisfying $g^x\equiv y(\mathrm{mod}P)$, status='failed' and Found x' is None.

Example

from unitarylab_algorithms import DiscreteLogAlgorithm
 
# Solve 3^x ≡ 6 (mod 7), the answer is x = 3
algo = DiscreteLogAlgorithm()
result = algo.run(g=3, y=6, P=7)
print(result['status'])    # 'ok'
print(result['Found x'])   # 3

Quick Demo

from unitarylab_algorithms.cryptology.discrete_log.algorithm import test
test(g=3, y=6, P=7)

Notes

• g and y must both be coprime with P, otherwise a ValueError is raised directly during parameter preparation, and no circuit is built.
• Unlike Shor’s algorithm, this algorithm has no retry mechanism — if a single quantum measurement fails to find a solution via continued-fraction post-processing, status='failed' is returned directly.
• The default values in the web-side parameter panel (g=3, y=13, P=17) differ from the default values in the source code’s test()/__main__ (g=3, y=6, P=7); when calling the Python API, go by the arguments you actually pass.

Simon’s Periodic Mask Algorithm

Background

Simon’s problem: given a function $f:\{0,1{\}}^n\to \{0,1{\}}^n$, known to have a hidden mask $s$ satisfying $f(x)=f(x\oplus s)$, find $s$. Classical algorithms require an exponential number of queries, while Simon’s algorithm only needs $O(n)$ quantum queries plus classical Gaussian elimination to solve it.

Import

from unitarylab_algorithms import SimonAlgorithm

.run() Parameters

def run(self, s: str = "1010", backend='torch', device='cpu', dtype=np.complex128) -> Dict[str, Any]

The default value '1010' of .run() itself is inconsistent with the default value '1101' used by the module-level test() function and the web-side parameters.json. Calling SimonAlgorithm().run() directly (without passing s) uses '1010'; calling test() or running via the web side defaults to '1101'.

Return Value

{
    'status': 'ok',
    'circuit_path': '/path/to/simon_algorithm_circuit.svg',
    'plot': [{'format': 'txt', 'filename': 'simon_algorithm_result.txt'}],
    'circuit': <Circuit>,
    'Computed s': '1101',
    'Valid states': 8,
    'computation time (s)': 0.0321,   # Note: the key name is lowercase computation, and it is not rounded (unlike 'Computation time (s)' in the other two algorithms)
    'Register size': 4,
    'Equations': 3,
}

Example

from unitarylab_algorithms import SimonAlgorithm
 
algo = SimonAlgorithm()
result = algo.run(s='1101')
print(result['status'])       # 'ok'
print(result['Computed s'])   # '1101'

Quick Demo

from unitarylab_algorithms.cryptology.simon.algorithm import test
test(s='1101')

Notes

• s must be a binary string of length $n$ (e.g., '1010' corresponds to $n=4$), and must contain at least one '1' — an all-zero string (such as '0000') will directly trigger ValueError("Secret string s cannot be all zeros"), and the algorithm will not run to completion.
• The computation-time field in the output dictionary is named in lowercase, 'computation time (s)', and is a raw, unrounded floating-point number, differing from the capitalized, 4-decimal-rounded 'Computation time (s)' used in the Shor / Discrete Logarithm algorithms — be careful of the case when reading it.
• status is determined by the actual comparison result of found_s == s, and can be used to judge whether this particular measurement-and-solve run successfully recovered the mask $s$.