SageMath Basics for Post-Quantum Cryptography

Every code listing from this chapter of Applied Post-Quantum Cryptography — 27 in total, 27 runnable here. Edit any cell and press Run.

The book's snippets build on each other down the chapter, but a Sage Cell kernel runs one cell and keeps no state afterwards, so each cell replays the earlier listings with apqc_book. That call is the only thing added to the book's own code.

← the playground

Listing 1 — SageMath and Python

SageMath is built on top of Python, but it adds richer mathematical types and objects. A plain Python integer and a Sage integer are not the same thing.

Listing 2 — SageMath and Python

In Python, the result is an ordinary integer. In Sage, the corresponding object may carry algebraic meaning.

Listing 3 — SageMath and Python

To inspect the type, use:

Listing 4 — Integers ℤ

The integer ring is available as ZZ.

Listing 5 — Integers ℤ

You can create integers explicitly:

Listing 6 — Integers ℤ

Basic arithmetic works as expected:

Listing 7 — Integers ℤ

Division behaves more carefully than in Python because Sage keeps symbolic and exact arithmetic whenever possible:

Listing 8 — Integers ℤ

The result is the rational number 10/3. Integer division is available through:

Listing 9 — Integers ℤ

and modular arithmetic through:

Listing 10 — Rationals ℚ

The rational field is QQ.

Listing 11 — Reals ℝ and complexes ℂ

SageMath also supports real and complex domains.

Listing 12 — Reals ℝ and complexes ℂ

For example:

Listing 13 — Creating a finite field

For example, the field with seven elements is:

Listing 14 — Creating a finite field

Elements are created by coercing values into the field:

Listing 15 — Creating a finite field

Arithmetic is performed modulo the prime:

Listing 16 — Inverses

In cryptography, inverses appear constantly. For a field element a, the inverse a^-1 satisfies a a^-1 = 1.

Listing 17 — Linear algebra over a finite field

Finite-field linear algebra is the starting point for many lattice-based constructions.

Listing 18 — Linear algebra over a finite field

The inverse can be computed as:

Listing 19 — Linear algebra over a finite field

and one can verify the identity matrix:

Listing 20 — Vectors and matrices

Vectors are convenient for representing secret values and noise terms.

Listing 21 — Vectors and matrices

Matrix-vector multiplication is then straightforward:

Listing 22 — Building a polynomial ring

Listing 23 — Building a polynomial ring

Now x is a formal variable in the ring.

Listing 24 — Building a polynomial ring

Addition and multiplication are performed in the usual algebraic way:

Listing 25 — Quotient rings

A quotient ring is created by imposing a polynomial relation. For example:

Listing 26 — A first cryptographic experiment

As a first experiment, we can verify the behavior of modular inverses.

Listing 27 — A first LWE-style example

To foreshadow later chapters, we can create a simple linear system over a finite field: