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

Like unit_ideal, but considered as a reduced ideal.

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

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

The reduction function ρ on ideals. ([Jozsa 2003], Sec. 6.2.)

The ρ^-1 function on ideals. Inverse to rho. ([Jozsa 2003], Sec. 6.4.)

The ρ operation on reduced ideals.

The ρ^–1 operation on reduced ideals.

The ρ operation on ideals-with-distance.

The ρ^–1 operation on ideals-with-distance.

The ρ operation on ideals-with-generator (i.e. pairs of an ideal I and an AlgNumGen x such that I is the principal ideal (x)).

Apply ρ to an reduced-ideals-with-generator

Reduce an ideal, by repeatedly applying ρ.

Reduce an ideal within a bounded loop. Applies the ρ function until the ideal is reduced. Used in star and fJN algorithms.

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

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

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.

The dot-square I⋅I of an ideal-with-distance I.

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.

Compute the expression i/N + j/L.

fN i j n l Δ: find the minimal ideal-with-distance (J,δ_J) such that δ_J > x, where x = i/N + j/L, where N = 2ⁿ, 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⁻ⁿ, and perturbed by the jitter parameter j/L.

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

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

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

Find the order of an endofunction on an argument. That is, order f x returns the first n > 0 such that fⁿ(x) = x.

Method: simple brute-force search/comparison.

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

Method: simple brute-force search/comparison.

Given a function p, an endofunction f, and an argument x, return fⁿ(x), for the first n > 0 such that p(fⁿ(x)) = p(x).

Method: simple brute-force search/comparison.

Given a bound b, a function p, an endofunction f, and an argument x, return fⁿ(x), for the first n > 0 such that p(fⁿ(x)) = p(x), if there exists such an n ≤ b.

Method: simple brute-force search/comparison.

Find the period of a function on integers, assuming that it is periodic and injective on its period. That is, period f returns the first n > 0 such that f(n) = f(0). Method: simple brute-force search/comparison.

Find the regulator R = log ε₀ of a field, given the discriminant Δ, by finding (classically) the order of ρ.

Uses IdDist and rho_d.

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

Uses '(Ideal,Number)' and rho_num.

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 ε₀ for a unit of the desired form.

Find the regulator R = log ε₀ of a field, given the discriminant Δ, by finding (classically) the order of ρ using fixed-precision arithmetic: fix_sizes_Ideal for IdealXs, and given an assumed bound b on log₂ R.

Uses IdDist and rho_d.