Real Quadratic Fields and the Infrastructure Method

Executive summary

The principal cycle is almost a group — and that is enough

In a real quadratic field the unit group is infinite, so the class number cannot be separated from the regulator. The classical route computes the regulator from the continued fraction expansion of √D, but the period length grows like √D, making the method exponential in the input size. Shanks observed that the cycle of reduced principal ideals carries an almost-group structure — the infrastructure — permitting giant steps and reducing the cost to about D^1/4.

Learning objectives

Explain why the regulator must be computed alongside the class number.
Compute a regulator from a continued fraction expansion.
State why the classical method is exponential.
Describe the distance function and the infrastructure.
Explain how giant steps achieve the square-root speedup.

Section 01Units and the regulator

A real quadratic field has signature (2, 0), so the unit rank is 1: there is a fundamental unit ε > 1 with every unit of the form ±ε^k. The regulator is R = log ε.

The regulator can be enormous

ε may have on the order of √D digits. For D near 10¹⁰ the fundamental unit can have tens of thousands of digits, so it cannot be written down explicitly at all. Compact representation — storing ε as a product of powers of small elements — is not an optimisation but a necessity.

The fundamental unit is exactly the fundamental solution of Pell's equation x² − Dy² = ±4, which is why the classical algorithm is a continued fraction expansion.

Section 02The classical continued fraction method

AlgorithmRegulator by continued fraction expansionin: D > 0 → out: the regulator R and the fundamental unit

Expand √D by the exact integer triple recurrence, generating reduced forms (equivalently, reduced ideals) as it goes.
Accumulate the convergents p_i/q_i.
Detect the end of the period: the triple (P, Q) returns to its starting value.
The fundamental solution appears at the period boundary; set ε from it.
Return R = log ε, computed to the required precision.

Each step is a baby step

One step of the continued fraction moves from one reduced principal ideal to the next in the cycle. Shanks's insight was to ask whether it is possible to move a long way along the cycle in a single operation — and the answer is yes.

Section 03The infrastructure

The reduced principal ideals form a cycle of length equal to the period. Attach to each a distance, essentially the accumulated logarithm of the relative generator. Distances lie in [0, R) and behave almost additively under composition:

d(𝔼𝔽) ≈ d(𝔼) + d(𝔽) modulo R, with a small bounded error

So the cycle is not quite a group — composition followed by reduction lands near, but not exactly on, the ideal at the summed distance. The discrepancy is bounded by a small constant, and can be corrected by a few baby steps.

Baby stepMove one place in the cycle

One continued fraction step. Advances the distance by a small, variable amount — on average about log of a partial quotient.

Giant stepCompose two ideals and reduce

Advances the distance by approximately the sum of the two distances. This is what makes a square-root search possible.

An almost-group is enough

Baby-step giant-step needs only that giant steps land close to the intended position and that the error can be repaired cheaply. The infrastructure supplies exactly that, so the regulator is found in about R^1/2 ≈ D^1/4 operations rather than R.

Section 04Computing the regulator in practice

Stage 01Estimate hR analyticallyThe class number formula gives the product with a provable error bound.
Stage 02Search the principal cycleUse baby steps and giant steps in the infrastructure to locate the point at distance R.
Stage 03Separate h from RThe analytic value constrains the product; the search gives R, hence h — or reveals that a multiple was found.
Stage 04VerifyConfirm that the candidate unit satisfies the norm equation and that hR matches the analytic estimate within its bound.

The index-2 error again

Finding a unit that is a square of the fundamental unit gives a regulator exactly twice the true value, and every downstream quantity is then wrong by a factor of 2. The analytic comparison is the only reliable detector, which is why it is a required step rather than a confirmation.

ReferenceFrequently asked questions

Why is compact representation necessary?

Because the fundamental unit may have more digits than can be stored. Compact representation writes it as a product of powers of small algebraic numbers, so that its logarithm — the quantity actually needed — can be evaluated without ever expanding the element.

Is the infrastructure a group?

No. Composition followed by reduction is associative only up to a bounded error in distance, so the cycle is a group-like structure rather than a group. Later work embeds it in a genuine group of a slightly larger object, which is how the theory is usually presented now.

What replaces this for large discriminants?

Buchmann's sub-exponential algorithm, which collects relations over a factor base exactly as in the imaginary case and extracts both the class group and the regulator from the relation matrix and its kernel.

NavigateContinue in this stream

Curated next steps from this page. The site also surfaces algorithmically related reading below.

ProvenanceSources and further reading

This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.