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: