I Basic Math

This chapter explains the basic mathematical components of number theory: group, field, order, roots of unity, cyclotomic polynomial, polynomial ring, and decomposition. These are essential building blocks for post-quantum cryptography.

A-1 Modulo Arithmetic
A-1.1 Overview
A-1.2 Modulo Arithmetic
A-2 Group
A-2.1 Definitions
A-2.2 Examples
A-3 Field
A-3.1 Definitions
A-3.2 Examples
A-3.3 Theorems
A-4 Order
A-4.1 Definitions
A-4.2 Theorems
A-5 Polynomial Ring
A-5.1 Overview
A-5.2 Coefficient Rotation
A-6 Decomposition
A-6.1 Number Decomposition
A-6.2 Polynomial Decomposition
A-6.3 Approximate Decomposition
A-6.4 Gadget Decomposition
A-7 Roots of Unity
A-7.1 Definitions
A-7.2 Theorems
A-8 Cyclotomic Polynomial
A-8.1 Definitions
A-8.2 Theorems
A-9 Roots of Unity and Cyclotomic Polynomial over Rings
A-10 Vector and Matrix
A-10.1 Vector Arithmetic
A-10.2 Various Types of Matrix
A-10.3 Matrix Arithmetic
A-10.4 Projection
A-10.5 Basis of a Polynomial Ring
A-10.6 Isomorphism between Polynomials and Vectors over Integers
A-10.7 Isomorphism between Polynomials and Vectors over Complex Numbers
A-10.8 Transforming Basis between Polynomial Ring and Vector Space
A-11 Euler’s Formula
A-11.1 Pythagorean Identity
A-11.2 Imaginary Number
A-11.3 Euler’s Formula
A-11.4 Vandermonde Matrix with Roots of Cyclotomic Polynomial over Complex Numbers
A-11.5 Vandermonde Matrix with Roots of Cyclotomic Polynomial over Rings (

ℤ_{p}

)
A-12 Modulo Rescaling
A-12.1 Rescaling Modulo of Congruence Relations
A-13 Chinese Remainder Theorem
A-13.1 Application: Residue Number System (RNS)
A-14 Taylor Series
A-15 Lagrange’s Polynomial Interpolation
A-16 Efficient Polynomial Multiplication by FFT and NTT
A-16.1 Background and Motivation
A-16.2 Forward FFT (or NTT)
A-16.3 Point-wise Multiplication
A-16.4 Inverse FFT (or NTT)

Part IBasic Math

Part I
Basic Math