Safe Haskell | None |
---|

This module provides some number-theoretic functions, particularly functions for solving the Diophantine equation

*t*

^{†}

*t*= ξ,

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 IntegerSource

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,

*n*=

*u*

*c*

_{1}

^{k1}⋅ … ⋅

*c*

_{m}

^{km},

where *m* ≥ 2, *u* is a unit, and *c*_{1}, …, *c*_{m} 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 -> IntegerSource

Modular exponentiation, using the method of repeated squaring.
`power_mod`

*a* *k* *n* computes *a*^{k} (mod *n*).

root_of_negative_one :: RandomGen g => g -> Integer -> StepComp IntegerSource

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.