Diophantine Equation Solver
The qdecomp.utils.diophantine subpackage provides a set of tools for solving the Diophantine equation
\(\xi = t \cdot t^\dagger\) for \(t \in \mathbb{D}\left[ \omega \right]\) where \(\xi \in \mathbb{D} \left[ \sqrt{2} \right]\) is given.
Diophantine Equation Module
This module solves the Diophantine equation \(\xi = t \cdot t^\dagger\) for \(t \in \mathbb{D}[\omega]\) where \(\xi \in \mathbb{D}[\sqrt{2}]\) is given. The solution \(t\) is returned if it exists, or None otherwise. This module is an implementation of the algorithm presented in Section 6 and Appendix C of [Ross and Selinger, 2014].
Example:
>>> from qdecomp.rings import *
>>> from qdecomp.utils.diophantine import solve_xi_eq_ttdag_in_d
# Solve a Diophantine equation that has a solution
>>> xi = Dsqrt2(D(13, 1), D(4, 1)) # Input
>>> t = solve_xi_eq_ttdag_in_d(xi) # Compute the solution
>>> print(f"{xi = }")
xi = 13/2^1+2/2^0√2
>>> print(f"{t = }")
t = -2/2^0ω3 + 1/2^1ω2 + 0/2^0ω + 3/2^1
# Check the solution
>>> xi_calculated_in_Domega = t * t.complex_conjugate() # Calculate (t * t†)
>>> xi_calculated = Dsqrt2.from_ring(xi_calculated_in_Domega) # Convert the result from D[omega] to D[sqrt(2)]
>>> print(f"{xi_calculated = }")
xi_calculated = 13/2^1+2/2^0√2
>>> print(f"{xi == xi_calculated = }")
xi == xi_calculated = True
# Solve a Diophantine equation that doesn't have any solution
>>> xi = Dsqrt2(D(9, 1), D(3, 1)) # Input
>>> t = solve_xi_eq_ttdag_in_d(xi) # Compute the solution
>>> print(f"{xi = }")
xi = 9/2^1+3/2^1√2
>>> print(f"{t = }")
t = None
- qdecomp.utils.diophantine.diophantine_equation.gcd_Zomega(x: Zomega, y: Zomega) Zomega[source]
Find the greatest common divider (or \(gcd\)) of \(x\) and \(y\) in the ring \(\mathbb{Z}[\omega]\). \(x\) and \(y\) are elements of the ring \(\mathbb{Z}[\omega]\). The algorithm implemented is the Euler method extended to the ring \(\mathbb{Z}[\omega]\).
- qdecomp.utils.diophantine.diophantine_equation.euclidean_div_Zomega(num: Zomega, div: Zomega) tuple[Zomega, Zomega][source]
Compute the euclidean division of \(num\) by \(div\), where \(num\) and \(div\) are elements of \(\mathbb{Z}[\omega]\). This function return \(q\) and \(r\) such that \(num = q \cdot div + r\).
- qdecomp.utils.diophantine.diophantine_equation.euclidean_div_Zsqrt2(num: Zsqrt2, div: Zsqrt2) tuple[Zsqrt2, Zsqrt2][source]
Perform the euclidean division of num in \(\mathbb{Z}[\sqrt{2}]\). This function returns \(q\) and \(r\) such that \(num = q \cdot div + r\).
- qdecomp.utils.diophantine.diophantine_equation.are_sim_Zsqrt2(x: Zsqrt2, y: Zsqrt2) bool[source]
Determine if \(x \sim y\). Equivalently, \(x \sim y\) if there exists a unit \(u\) such that \(x = u \cdot y\). \(x\), \(y\) and \(u\) are elements of \(\mathbb{Z}[\sqrt{2}]\).
- qdecomp.utils.diophantine.diophantine_equation.is_unit_Zsqrt2(x: Zsqrt2) bool[source]
Determine if \(x\) is a unit in the ring \(\mathbb{Z}[\sqrt{2}]\).
- Parameters:
x (Zsqrt2) – The number to test
- Returns:
True if \(x\) is a unit, False otherwise
- Return type:
bool
- qdecomp.utils.diophantine.diophantine_equation.is_square(n: int) bool[source]
Check if \(n\) is a perfect square.
- Parameters:
n (int) – An integer
- Returns:
True if \(n\) is a perfect square, False otherwise
- Return type:
bool
- qdecomp.utils.diophantine.diophantine_equation.solve_usquare_eq_a_mod_p(a: int, p: int) int[source]
Solve the diophantine equation \(u^2 = -a\ (\text{mod p})\) where \(a\), \(p\) and \(u\) are integers. This function returns the first integer solution of the equation. \(p\) is a prime. This problem is solved using the Tonelli-Shanks algorithm.
- Parameters:
a (int) – An integer
p (int) – A prime integer
- Returns:
The first positive integer solution \(u\) to the equation \(u^2 = -a\ (\text{mod p})\)
- Return type:
int
- qdecomp.utils.diophantine.diophantine_equation.integer_fact(p: int) list[tuple[int, int]][source]
Find the factorization of an integer \(p\). This function returns a list of tuples \((p_i, m_i)\) where \(p_i\) is a prime factor of \(p\) and \(m_i\) is its power.
- Parameters:
p (int) – Number to factorize
- Returns:
The prime factors of n and their powers. Each tuple is of the form \((p_i, m_i)\) where \(p_i\) is a prime factor of \(p\) and \(m_i\) is its power.
- Return type:
list of tuples
- Raises:
ValueError – If the number is less than 2.
ValueError – If the number is not an integer.
- qdecomp.utils.diophantine.diophantine_equation.xi_fact(xi: Zsqrt2) list[tuple[Zsqrt2, int]][source]
Finds the factorization of \(\xi\) (up to a prime) in the ring \(\mathbb{Z}[\sqrt{2}]\) where \(\xi\) is an element of \(\mathbb{Z}[\sqrt{2}]\). This function returns a list of tuples \((\xi_i, m_i)\), where \(\xi_i\) is a prime factor of \(\xi\) in \(\mathbb{Z}[\sqrt{2}]\) and \(m_i\) is its power.
- Parameters:
xi (Zsqrt2) – An element of \(\mathbb{Z}[\sqrt{2}]\)
- Returns:
The prime factors of \(\xi\) and their powers. Each tuple is of the form \((\xi_i, m_i)\) where \(\xi_i\) is a prime factor of \(\xi\) and \(m_i\) is its power.
- Return type:
list of tuples
- qdecomp.utils.diophantine.diophantine_equation.pi_fact_into_xi(pi: int) Zsqrt2 | None[source]
Solve the equation \(p_i = \xi_i \cdot \xi_i^{\bullet} = a^2 - 2 \cdot b^2\) where \(^{\bullet}\) denotes the \(\sqrt{2}\) conjugate. \(p_i\) is a prime integer and \(\xi_i = a + b \sqrt{2}\) is an element of \(\mathbb{Z}[\sqrt{2}]\). \(p_i\) has a factorization only if \(p_i\ \%\ 8 = 1 \text{ or } 7\) or if \(p_i = 2\). In any other case, the function returns None.
- Parameters:
pi (int) – A prime integer
- Returns:
A number \(\xi_i\) for which \(p_i = \xi_i \cdot \xi_i^{\bullet}\), or None if \(p_i\ \%\ 8 \neq 1 \text{ or } 7\)
- Return type:
Zsqrt2 or None
- qdecomp.utils.diophantine.diophantine_equation.xi_i_fact_into_ti(xi_i: Zsqrt2, check_prime: bool = False) Zomega | None[source]
Solve the equation \(\xi_i = t_i \cdot t_i^\dagger\) where \(^\dagger\) denotes the complex conjugate. \(\xi_i\) is a prime element in \(\mathbb{Z}[\sqrt{2}]\) and \(t_i\) is an element of \(\mathbb{Z}[\omega]\). \(\xi_i\) has a factorization only if \(p_i\ \%\ 8 = 1, 3 \text{ or } 5\), where \(p_i = \xi_i \cdot \xi_i^{\bullet}\) or if \(p_i = 2\).
Note: this function assumes \(\xi_i\) is a prime element in \(\mathbb{Z}[\sqrt{2}]\). No check is performed to verify this assumption unless specified by the check_prime argument.
- Parameters:
xi_i (Zsqrt2) – A prime element in \(\mathbb{Z}[\sqrt{2}]\)
check_prime (bool) – If set to True, the function will check if \(\xi_i\) is a prime in \(\mathbb{Z}[\sqrt{2}]\)
- Returns:
A number \(t_i\) for which \(\xi_i = t_i \cdot t_i^\dagger\), or None if \(\xi_i\ \%\ 8 = 7\)
- Return type:
Zomega or None
- Raises:
ValueError – If the input argument is not a prime in \(\mathbb{Z}[\sqrt{2}]\) (only if check_prime is True, because this verification is computationally expensive)
- qdecomp.utils.diophantine.diophantine_equation.solve_xi_sim_ttdag_in_z(xi: Zsqrt2) Zomega | None[source]
Solve the equation \(\xi \sim t \cdot t^\dagger\) for \(t\) where \(^\dagger\) denotes the complex conjugate. \(\xi\) is an element of \(\mathbb{Z}[\sqrt{2}]\) and \(t\) is an element of \(\mathbb{Z}[\omega]\). This function returns the first solution of the equation. If no solution exists, the function returns None.
- qdecomp.utils.diophantine.diophantine_equation.solve_xi_eq_ttdag_in_d(xi: Dsqrt2) Domega | None[source]
Solve the equation \(\xi = t \cdot t^\dagger\) for \(t\) where \(^\dagger\) denotes the complex conjugate. \(\xi\) is an element of \(\mathbb{D}[\sqrt{2}]\) and \(t\) is an element of \(\mathbb{D}[\omega]\). This function returns the first solution of the equation. If no solution exists, it returns None.
Tonelli-Shanks Module
This module implements the Tonelli-Shanks algorithm to find square roots modulo a prime number.
The problem is stated as follows: Given a prime number \(p\) and an integer \(a\), find an integer \(r\) such that \(r^2 \equiv a\ (\text{mod p})\). The complexity of this algorithm is \(O(\log^2 p)\). Its efficiency is due to the fact that it exploits the decomposition of \(p-1\) into the form \(p-1 = q \cdot 2^s\), where \(q\) is odd and \(s\) is a non-negative integer.
More information on this algorithm and implementation can be found in [Code, 2025].
- qdecomp.utils.diophantine.tonelli_shanks.legendre_symbol(a: int, p: int) int[source]
Compute the Legendre symbol \((a/p)\) using Euler’s criterion.
The Legendre symbol is defined as follows:
- \((a/p)\) = 0 if \(a\) is divisible by \(p\)- \((a/p)\) = 1 if \(a\) is a quadratic residue modulo \(p\) (i.e., there exists an integer \(x\) such that \(x^2 \equiv a\ (\text{mod p})\))- \((a/p)\) = -1 if \(a\) is not a quadratic residue modulo \(p\)- Parameters:
a (int) – The integer for which the Legendre symbol is computed.
p (int) – A prime number.
- Returns:
The Legendre symbol \((a/p)\).
- Return type:
int
- qdecomp.utils.diophantine.tonelli_shanks.tonelli_shanks_algo(a, p)[source]
Tonelli-Shanks algorithm to find the smallest square root of \(a\) modulo \(p\).
The problem solved by this function is stated as follows: Given a prime number \(p\) and an integer \(a\), find an integer \(r\) such that \(r^2 \equiv a\ (\text{mod p})\). If no solution exists, a ValueError is raised.
- Parameters:
a (int) – The integer for which the square root is computed.
p (int) – A prime number.
- Returns:
The smallest non-negative integer \(r\) such that \(r^2 \equiv a\ (\text{mod p})\).
- Return type:
int
- Raises:
ValueError – If \(a\) is not a quadratic residue modulo \(p\), i.e. no solution exists.
References
Rosetta Code. Tonelli-shanks algorithm. 2025. URL: https://rosettacode.org/wiki/Tonelli-Shanks_algorithm.
N. J. Ross and P. Selinger. Optimal ancilla-free clifford+t approximation of z-rotations. Quantum Information & Computation, 2014. URL: https://arxiv.org/abs/1403.2975.