| Safe Haskell | None |
|---|---|
| Language | Haskell98 |
Quantum.Synthesis.Diophantine
Description
This module provides some number-theoretic functions, particularly functions for solving the Diophantine equation
where ξ ∈ ℤ[√2] and t ∈ ℤ[ω], or ξ ∈ D[√2] and t ∈ D[ω].
In general, solving this equation can be hard, as it depends on the ability to factor the integer n = ξ•ξ into primes. We formulate the solution as a step computation (see Quantum.Synthesis.StepComp), so that the caller can dynamically determine how much time to spend on solving the equation, or can attempt to solve several such equations in parallel.
In many cases, even a partial factorization of n is sufficient to determine that no solution exists. This implementation is written to take advantage of such cases.
- diophantine :: RandomGen g => g -> ZRootTwo -> StepComp (Maybe ZOmega)
- diophantine_dyadic :: RandomGen g => g -> DRootTwo -> StepComp (Maybe DOmega)
- diophantine_associate :: RandomGen g => g -> ZRootTwo -> StepComp (Maybe ZOmega)
- find_factor :: RandomGen g => g -> Integer -> StepComp Integer
- relatively_prime_factors :: EuclideanDomain a => a -> a -> (a, [(a, Integer)])
- power_mod :: Integer -> Integer -> Integer -> Integer
- root_of_negative_one :: RandomGen g => g -> Integer -> StepComp Integer
- root_mod :: RandomGen g => g -> Integer -> Integer -> StepComp Integer
Diophantine solvers
diophantine :: RandomGen g => g -> ZRootTwo -> StepComp (Maybe ZOmega) Source #
Given ξ ∈ ℤ[√2], find t ∈ ℤ[ω] such that t†t = ξ, if
such t exists, or return Nothing otherwise.
diophantine_dyadic :: RandomGen g => g -> DRootTwo -> StepComp (Maybe DOmega) Source #
Given an element ξ ∈ D[√2], find t ∈ D[ω] such
that t†t = ξ, if such t exists, or return Nothing
otherwise.
diophantine_associate :: RandomGen g => g -> ZRootTwo -> StepComp (Maybe ZOmega) Source #
Given ξ ∈ ℤ[√2], find t ∈ ℤ[ω] such that t†t ~ ξ, if
such t exists, or Nothing otherwise. Unlike diophantine, the
equation is only solved up to associates, i.e., up to a unit of the
ring.
Factoring
find_factor :: RandomGen g => g -> Integer -> StepComp Integer Source #
Given a positive composite integer n, find a non-trivial factor of n using a simple Pollard-rho method. The expected runtime is O(√p), where p is the size of the smallest prime factor. If n is not composite (i.e., if n is prime or 1), this function diverges.
relatively_prime_factors :: EuclideanDomain a => a -> a -> (a, [(a, Integer)]) Source #
Given a factorization n = ab of some element of a Euclidean domain, find a factorization of n into relatively prime factors,
where m ≥ 2, u is a unit, and c1, …, cm are pairwise relatively prime.
While this is not quite a prime factorization of n, it can be a useful intermediate step for computations that proceed by recursion on relatively prime factors (such as Euler's φ-function, the solution of Diophantine equations, etc.).
Computations in ℤn
power_mod :: Integer -> Integer -> Integer -> Integer Source #
Modular exponentiation, using the method of repeated squaring.
power_mod a k n computes ak (mod n).
root_of_negative_one :: RandomGen g => g -> Integer -> StepComp Integer Source #
Compute a root of −1 in ℤn, where n > 0. If n is a positive prime satisfying n ≡ 1 (mod 4), this succeeds within an expected number of 2 ticks. Otherwise, it probably diverges.
As a special case, if this function notices that n is not prime, then it diverges without doing any additional work.