Safe Haskell | None |
---|

This module implements the classical operations on ideals used in Hallgren’s algorithm (including also classical versions of the quantum operations required).

- unit_ideal :: CLIntP -> Ideal
- unit_idealRed :: CLIntP -> IdealRed
- c_of_ideal :: Ideal -> CLInt
- gamma_of_ideal :: Ideal -> AlgNum
- rho :: Ideal -> Ideal
- rho_inv :: Ideal -> Ideal
- rho_red :: IdealRed -> IdealRed
- rho_inv_red :: IdealRed -> IdealRed
- rho_d :: IdDist -> IdDist
- rho_inv_d :: IdDist -> IdDist
- rho_num :: (Ideal, AlgNum) -> (Ideal, AlgNum)
- rho_red_num :: (IdealRed, AlgNum) -> (IdealRed, AlgNum)
- reduce :: Ideal -> IdealRed
- bounded_reduce :: IdDist -> IdDist
- bounded_step :: (IdDist -> Bool) -> (IdDist -> IdDist) -> IdDist -> IdDist
- bounded_step_delta :: (CLReal -> Bool) -> (IdDist -> IdDist) -> IdDist -> IdDist
- dot :: IdDist -> IdDist -> IdDist
- dot' :: IdDist -> IdDist
- star :: IdDist -> IdDist -> IdDist
- compute_injl :: Integral int => CLInt -> int -> CLInt -> int -> CLReal
- fN :: Integral int => CLInt -> CLInt -> int -> int -> CLIntP -> (Ideal, CLInt)
- fN_d :: Integral int => CLInt -> CLInt -> int -> int -> CLIntP -> (IdDist, CLInt)
- fJN :: IdDist -> CLInt -> CLInt -> CLInt -> CLInt -> CLIntP -> (Ideal, CLInt)
- fJN_d :: IdDist -> CLInt -> CLInt -> CLInt -> CLInt -> CLIntP -> (IdDist, CLInt)
- order :: Eq a => (a -> a) -> a -> Int
- order_with_projection :: Eq b => (a -> b) -> (a -> a) -> a -> Int
- first_return_with_projection :: Eq b => (a -> b) -> (a -> a) -> a -> a
- first_return_with_proj_bdd :: Eq b => Int -> (a -> b) -> (a -> a) -> a -> Maybe a
- period :: (Eq a, Integral int) => (int -> a) -> int
- regulator :: CLIntP -> FPReal
- fundamental_unit :: CLIntP -> AlgNum
- fundamental_solution :: CLIntP -> (Integer, Integer)
- regulator_fixed_prec :: Int -> CLIntP -> Maybe FPReal

# Basic operations on ideals

unit_ideal :: CLIntP -> Ideal Source #

: the unit ideal `unit_ideal`

*bigD* *l**O*, for Δ = *bigD*, with the ideal’s coefficients given as *l*-bit integers.
([Jozsa 2003], Prop. 14.)

unit_idealRed :: CLIntP -> IdealRed Source #

Like `unit_ideal`

, but considered as a reduced ideal.

c_of_ideal :: Ideal -> CLInt Source #

The integer constant *c* of an ideal.
([Jozsa 2003], page 14 bottom: "Since 4*a* divides *b*^{2}-*D*
(cf. proposition 16) we introduce the integer *c* = |*D* − *b*^{2}|/(4*a*)")

gamma_of_ideal :: Ideal -> AlgNum Source #

γ(*I*) = (*b*+√Δ)/(2*a*) for a given ideal *I*.
([Jozsa 2003], Sec. 6.2.)

rho_inv :: Ideal -> Ideal Source #

The ρ^{-1} function on ideals. Inverse to `rho`

.
([Jozsa 2003], Sec. 6.4.)

rho_inv_red :: IdealRed -> IdealRed Source #

The ρ^{–1} operation on reduced ideals.

rho_num :: (Ideal, AlgNum) -> (Ideal, AlgNum) Source #

The ρ operation on ideals-with-generator (i.e. pairs of an ideal *I* and an `AlgNum`

*x* such that *I* is the principal ideal (*x*)).

rho_red_num :: (IdealRed, AlgNum) -> (IdealRed, AlgNum) Source #

Apply ρ to an reduced-ideals-with-generator

# Ideal reductions (bounded)

bounded_reduce :: IdDist -> IdDist Source #

bounded_step :: (IdDist -> Bool) -> (IdDist -> IdDist) -> IdDist -> IdDist Source #

Apply a function (like ρ,ρ^{-1},ρ^{2}) to an ideal, bounded
by 3*ln(Δ)/2*ln(2). Execute while satisfies condition function.

bounded_step_delta :: (CLReal -> Bool) -> (IdDist -> IdDist) -> IdDist -> IdDist Source #

Like `bounded_step`

, but the condition is checked against delta of the
current ideal.

# Products of ideals

dot :: IdDist -> IdDist -> IdDist Source #

The ordinary (not necessarily reduced) product of two reduced fractional ideals.

*I*⋅*J* of [Jozsa 2003], Sec 7.1, following the description
given in Prop. 34.

star :: IdDist -> IdDist -> IdDist Source #

The star-product of two ideals-with-distance.

This is *I***J* of [Jozsa 2003], Sec. 7.1, defined as the first reduced
ideal-with-distance following *I*⋅*J*.

# The function f_{N}, and variants

compute_injl :: Integral int => CLInt -> int -> CLInt -> int -> CLReal Source #

Compute the expression i/N + j/L.

fN :: Integral int => CLInt -> CLInt -> int -> int -> CLIntP -> (Ideal, CLInt) Source #

: find the minimal ideal-with-distance (`fN`

*i* *j* *n* *l* Δ*J*,δ_{J}) such that δ_{J} > *x*, where *x* = *i*/*N* + *j*/*L*, where *N* = 2^{n}, *L* = 2^{l}. Return (*i*,*J*,δ_{J}–*x*). Work under the assumption that *R* < 2^{s}.

This is the function *h* of [Jozsa 2003, Section 9], discretized with precision 1/*N* = 2^{−n},
and perturbed by the jitter parameter *j*/*L*.

fN_d :: Integral int => CLInt -> CLInt -> int -> int -> CLIntP -> (IdDist, CLInt) Source #

Like `fN`

, but returning an ideal-with-distance not just an ideal.

fJN :: IdDist -> CLInt -> CLInt -> CLInt -> CLInt -> CLIntP -> (Ideal, CLInt) Source #

Analogue of `fN`

, working within the cycle determined by a given ideal *J*.
([Hallgren 2006], Section 5.)

fJN_d :: IdDist -> CLInt -> CLInt -> CLInt -> CLInt -> CLIntP -> (IdDist, CLInt) Source #

Like `fJN`

, but returning an ideal-with-distance not just an ideal.

# Classical period-finding

Functions for classically finding the regulator and fundamental unit of a field using the period of *f_N*.

## Auxiliary functions

order_with_projection :: Eq b => (a -> b) -> (a -> a) -> a -> Int Source #

Given a function *p*, an endofunction *f*, and an argument *x*, returns the first *n* > 0 such that *p*(*f*sup /n/) = *p*(*x*).

Method: simple brute-force search/comparison.

first_return_with_projection :: Eq b => (a -> b) -> (a -> a) -> a -> a Source #

period :: (Eq a, Integral int) => (int -> a) -> int Source #

Find the period of a function on integers, assuming that it is periodic and injective on its period. That is,

returns the first `period`

*f**n* > 0 such that *f*(*n*) = *f*(0). Method: simple brute-force search/comparison.

## Haskell native arithmetic

The functions of this section use Haskell’s native integer and floating computation.

fundamental_unit :: CLIntP -> AlgNum Source #

Find the fundamental unit ε_{0} of a field, given the discriminant Δ,
by finding (classically) the order of ρ.

Uses '(Ideal,Number)' and `rho_num`

.

fundamental_solution :: CLIntP -> (Integer, Integer) Source #

Find the fundamental solution of Pell’s equation, given *d*.

Solutions of Pell’s equations are integer pairs (*x*,*y*) such that
*x*,*y* > 0, and (*x* + *y*√d)(*x* – *y*√d) = 1.

In this situation, (*x* + *y*√d) is a unit of the algebraic integers
of *K*, and is >1, so we simply search the powers of ε_{0} for a
unit of the desired form.

## Fixed-precision arithmetic

The functions of this section perform period-finding using fixed-precision arithmetic. This should parallel closely (though at present not exactly, due to the implementations of floating-point operations) the quantum circuit implementations, and hence allows testing of whether the chosen precisions are accurate.