Introduction

Give a description of the topic, and what you hope the reader will get from this. For example, this page will cover addition of the natural numbers. Talk about how this relates to something in cryptography, either through a protocol, or an attack. This can be a single sentence, or verbose.

Laws of Addition

For all integers, the addition operation is

• Associative: $a + (b + c) = (a + b) + c$

• Commutative: $a + b = b + a$

• Distributive: $a(b + c) = ab + ac$

• Contains an identity element: $a + 0 = 0 + a = a$

• Has an inverse for every element: $a + (-a) = (-a) + a = 0$

• Closed: $\forall a, b \in \mathbb{Z}, a + b \in \mathbb{Z}$

Interesting Identity

Sage Example

sage: 1 + (2 + 3) == (1 + 2) + 3
True
sage: 1 + 2 == 2 + 1
True
sage: 5*(7 + 11) == 5*7 + 5*11
True
sage: sum(i for i in range(1000))^2 == sum(i^3 for i in range(1000))
True

Further Resources

• Links to

• Other interesting

• Resources

Thank you!

Our Writers

• ...

• You?

Join CryptoBook

If you would like to join the team, come over to our Discord Channel and talk with us about your ideas

Introduction

Although we have functions that can compute our $\gcd$easily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.

It's extended version will help us calculate modular inverses which we will define a bit later.

Euclidean Algorithm

Important Remark

If $a = b \cdot q + r$and $d = \gcd(a, b)$ then $d | r$. Therefore $\gcd(a, b) = \gcd(b, r)$

Algorithm

We write the following:

$a = q_0 \cdot b + r_0 \\ b = q_1 \cdot r_0 + r_1 \\ r_0 = q_2 \cdot r_1 + r_2 \\ \vdots \\ r_{n-2} = r_ {n-1} \cdot q_{n - 1} + r_n \\ r_n = 0$

Or iteratively $r_{k-2} = q_k \cdot r_{k-1} + r_k$ until we find a $0$. Then we stop

Now here's the trick:

If $d = \gcd(a, b)$ then $d$ divides $r_0, r_1, ... r_{n-1}$

Example:

Calculate $\gcd(24, 15)$

$24 = 1 \cdot 15 + 9 \\ 15 = 1 \cdot 9 + 6 \\ 9 = 1 \cdot 6 + 3 \\ 6 = 2 \cdot 3 + 0 \Rightarrow 3 = \gcd(24, 15)$

Code

def my_gcd(a, b):
    # If a < b swap them
    if a < b: 
        a, b = b, a
    # If we encounter 0 return a
    if b == 0: 
        return a
    else:
        r = a % b
        return my_gcd(b, r)

print(my_gcd(24, 15))
# 3

Exercises:

1. Pick 2 numbers and calculate their $\gcd$by hand.

2. Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

Bezout's identity

Let $d = \gcd(a, b)$. Then there exists $u, v$ such that $au + bv = d$

The extended euclidean algorithm aims to find $d = \gcd(a, b), \text{ and }u, v$given $a, b$

# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3 

print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3

Philosophy

The aim of CryptoBook is to have a consolidated space for all of the mathematics required to properly learn and enjoy cryptography. The focus of any topic should be to introduce a reader to a subject in a way that is fun, engaging and with an attempt to frame it as an applied resource.

The second focus should be to cleanly implement the various topics using SageMath, so that there is a clear resource for a new reader to gain insight on how SageMath might be used to create the objects needed.

Proposed topics

This list is not complete so please add to it as you see fit.

Mathematical Background

Fundamentals

• Congruences

• GCD, LCM

  • Bézout's Theorem

  • Gauss' Lemma and its ten thousand corollaries

• Euclid's algorithm

• Modular Arithmetic

• Morphisms et al.

• Frobenius endomorphism

Number Theory

Mainly thinking things like

• Prime decomposition and distribution

• Primality testing

• Euler's theorem

• Factoring

• Legendre / Jacobi symbol

Abstract Algebra

Mainly thinking things like:

• Groups, Rings, Fields, etc.

• Abelian groups and their relationship to key-exchange

• Lagrange's theorem and small subgroup attacks

Basilar Cryptanalysis forms

• Introduction to Cryptanalysis

• A linear Approach to Cryptanalysis

• Matsui's Best biases algorithm

• A Differential Approach to Cryptanalysis

Elliptic Curves

• Weierstrass

• Montgomery

• Edwards

• Counting points (Schoof's algorithm)

• Complex multiplication

  • Good reference, thanks Joachim

Generating Elliptic Curves

• Generating Anomalous curves

• Generating curves of prime order

• Generating supersingular curves Wikipedia

• Generating non-supersinular curves of low embedding degree

• Generating curves of arbitary order (hard)

  • Thesis on the topic

  • Sage implementation ChiCube's script

Hyperelliptic curves

• Generalization of elliptic curves

• Recovering a group structure using the Jacobian

• Example: genus one curves, jacobian is isomorphic to the set of points

• Mumford representation of divisors

• Computing the order of the Jacobian

  • For characteristic 2^n: Example 56

  • Hyper Metroid example

Security background

• Basic Concepts

  • Confidentiality, Integrity etc

  • Encryption, Key generation

• Attacker goals + Attack games

• Defining Security - Perfect security, semantic security

• Proofs of security + Security Reductions

Asymmetric Cryptography

RSA

• Textbook protocol

• Padding

  • Bleichenbacher's Attack

  • OAEP

• Coppersmith

  • Håstad's Attack

  • Franklin-Reiter Attack

• Wiener's Attack

• RSA's Integer fattorization Attacks

• • Fermat Factoring Attack

  • Quadratic Sieve Attack

  • Number Fielde Sieve Attack

• RSA Digital Signature Scheme

• Timing Attacks on RSA

• RSA with Chinese Remainder Theorem (CRT)

  • Fault Attack on RSA-CRT

  • Bellcore Attack (Low Voltage Attack)

Paillier Cryptosystem

• Textbook protocol

ElGamal Encryption System

• Textbook protocol

• ElGamal Digital Signature Scheme

Diffie-Hellman

• Textbook protocol

• Strong primes, and why

Elliptic Curve Cryptography

• ECDSA

• EdDSA

Symmetric Cryptography

One Time Pad

• XOR and its properties

• XOR as One Time Pad

• Generalized One Time Pad

Block Ciphers

• AES

Stream Ciphers

• Affine

• RC4

Hashes

• Introduction

• Trapdoor Functions

• MD family

• SHA family

• BLAKE Hash family

• // TODO: Insert Attacks

Isogeny Based Cryptography

• Isogenies

• Isogeny graphs

• Torsion poins

• SIDH

• SIKE

• BIKE

Cryptographic Protocols

Zero-knowledge proofs

• Schnorr proof of knowledge for dlog

• Core definitions

• Proof of equality of dlog

• Proof of knowledge of a group homomorphism preimage

Formal Verification of Security Protocols

• Definition of Formal Verification

• Uses of Formal Verification

• Handshake protocols, flawed protocols

• The external threat: Man-In-The-Middle attacks

• Attacking the (flawed) Needham-Shroeder public key exchange protocol

Usefull Resources ( Books, articles ..) // based on my material

• Cryptanalytic Attacks on RSA (Yan, Springer, 2008)

• Algorithmic Cryptanalysis (Antoine Joux, CRC Press, 2009)

• Algebraic Cryptanalysis (Brad, Springer, 2009)

• RC4 stream Cipher and its variants (H. Rosen, CRC Press, 2013)

• Formal Models and Techniques for Analyzing Security Protocols (Cortier, IOS Press, 2011)

• Algebraic Shift Register Sequences (Goresky && Klapper, Cambridge Press, 2012)

• The Modelling and Analysis of Security Protocols (Schneider, Pearson, 2000)

• Secure Transaction Protocol Analysis (Zhang && Chen, Springer, 2008)

About this project

CryptoBook is a community project, developed by members of to create a resource for people to learn cryptography. The focus of this project is to create a friendly resource for the mathematical fundamentals of cryptography, along with corresponding implementation.

Think of this as an alternative SageMath documentation source, where the focus is its application in solving cryptographic problems.

If you're interested in contributing, come chat to us in our

Working together

• If something doesn't make sense, make a comment using GitBook, or ask in the Discord.

• If you are confident that something is wrong, just fix it. There's no need to ask.

• If you think something doesn't have enough detail, expand on it, or leave a comment suggesting that.

• If a page is getting too long, break it down into new pages. If you're unsure, then leave a comment or talk in the discord

• If you want to write about something new and learn as you type, this is fine! But please leave a warning at the top that this is new to you and needs another pair of eyes.

• If there's big subject you're working on, claim the page and save it, show us that that's what you're doing so we don't overlap too much

General Tips

• Introduce new objects slowly, if many things need to be assumed, then try to plan for them to appear within the somewhere.

• It is better to cover less, and explain something well, than it is to quickly cover a lot. We're not racing

• When explaining anything, imagine you are introducing it for a first time. Summaries exist elsewhere online, the goal of CryptoBook is education

• Contribute as much or as little as you want, but try to only work on topics that

  • You are interested in

  • You have some experience of thinking about

• External resources should be included at the end of the page. Ideally the book should be self-contained (within reason) but other resources are great as they offer other ways to learn

• Try and use the hints / tips blocks to break up dense text, for example:

Page Structure

• A page should have a clear educational goal: this should be explained in the introduction. References to prerequisites should be kept within the book and if the book doesnt have this yet, it should be placed into .

• The topic should be presented initially with theory, showing the mathematics and structures we will need. A discussion should be pointed towards how this appears within Cryptography

• Within a discussion of a topic, a small snippet of code to give an example is encouraged

• If you write code better than you write maths, then just include what you can and the page will form around that

• An example page is given in

Formatting

Mathematics notation

There's no "right or wrong" but it's good to be consistent, I think?

• All maths must be presented using using either both block and inline

• We seem to be using mathbb for our fields / rings. So let's stick with that? Maybe someone has a good resource for notation we can work from?

Code Blocks

• Make sure all code blocks have the right language selected for syntax highlighting

• Preference is to SageMath, then to Python, then others.

• Code should be cope-pastable. So if you include print statement, include the result of the output as a comment

Algorithms

• Algorithms should be presented as??

Introduction

Throughout CryptoBook, discussions are made more concise by using various mathematical symbols. For some of you, all of these will feel familiar, while for others, it will feel new and confusing. This chapter is devoted to helping new readers gain insight into the notation used.

Mathematical Objects

Special Sets

• : denotes the set of complex numbers

• : denotes the set of real numbers

• : denotes the set of integers

• : denotes the set of rational numbers

• : denotes the set of natural numbers (non-negative integers)

• : denotes the set of integers mod

• We refer to unit groups by or . Example:

• We refer to finite fields with elements by

• We refer to a general field by

• We refer to the algebraic closure of this field by

Relation operators

• means is an element of (belongs to)

Logical Notation

• means for all

• means there exists. means uniquely exists

Operators

• means the probability of an event to happen. Sometimes denoted as or as

Introduction

Thinking not over the integers as a whole but modulo some integerinstead can prove quite useful in a number of situation. This chapter attempts to introduce to you the basic concepts of working in such a context.

Congruences

For the following chapter, we will assumeis a natural integer, andandare two integers. We say thatandare congruent modulowhen, or equivalently when there is an integersuch that. We denote this byor . I will use the first notation throughout this chapter.

Remark: When, we have, whereis the remainder in the euclidean division ofby

This relation has a number of useful properties:

• The proofs are left as an exercise to the reader :p (Hint: go back to the definition)

Seeing as addition and multiplication are well defined, the integers moduloform a ring, which we note. In sage, you can construct such ring with either of the following

Powering modulois relatively fast, thanks to the algorithm, so we needn't worry about it taking too much time when working with high powers

As a side note, remember that if an equality holds over the integers, then it holds modulo any natural integer. This can be used to prove that a relation is never true by finding a suitable modulus, or to derive conditions on the potential solutions of the equation.

Example: by choosing an appropriate modulus, show that not even god is able to find integersandsuch that

Modular Inverse

Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integeris the same as multiplying by its inverse; that is we want to find another integersuch that. Since, it is clear from that such an inverse exists if and only if. Therefore, the units moduloare the integers coprime to, lying in a set we call the unit group modulo:

Finding the modular inverse of a number is an easy task, thanks to the (that outputs solutions inandto the equationfrom above).

Introduction

Two of the skills a cryptographer must master are:

1. Knowing his way and being comfortable to work with numbers.

2. Understanding and manipulating abstract objects.

This chapter of fundamentals proposes to prepare you for understanding the basics of number theory and abstract algebra .We will start with the most basic concepts such as division and build up knowledge until you, future cryptographer, are able to follow and understand the proofs and intricacies of the cryptosystems that make our everyday life secure.

We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.

For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.

So what are we waiting for? Let's jump right in!

Division

Let be the set denoting the integers.

Definition - Divisibility

For we say that divides if there is some such that

Notation:

Example

For we have because we can find such that .

Properties

• and implies

  • Example: Let and

  • and . We can find such that

• and implies

• if and then

Definition - Division with remainder

Let with ,

There exists unique such that and

is called the quotient and the remainder

Examples:

• To find python offers us the divmod() function that takes as arguments

• If we want to find only the quotient we can use the // operator

• If we want to find the remainder we can use the modulo % operator

Exercises:

1. Now it's your turn! Play with the proprieties of the division in Python and see if they hold.

Greatest common divisor

Definition

Let be 2 integers. The greatest common divisor is the largest integer such that and

Notation:

Examples:

Remark:

• for all other common divisors of we have

Things to think about

What can we say about numbers with ? How are their divisors?

Example: Ideals of the integers

Definition - Ideal of

is an ideal we have

Example: - multiples of

Remarks:

1. we have

2. is an ideal

Example: Consider . This ideal contains

Greatest common divisor

Let be 2 integers. If

Wilson's Theorem

A positive integer is a prime if and only if:

Euler's Theorem

Let and s.t. , then:

Fermat's Little Theorem

Let be a prime and , then:

or equivalently:

Reference

Continued Fractions

Continued fractions are a way of representing a number as a sum of an integer and a fraction.

Mathematically, a continued fraction is a representation

$a_{i}, b_{i}$are complex numbers. The continued fraction with $b_{i} = 1\ \forall i$ is called a simple continued fraction and continued fractions with finite number of $a_{i}$ are called finite continued fractions.

Consider example rational numbers,

the continued fractions could be written as

Notation

A simple continued fraction is represented as a list of coefficients($a_{i}$) i.e

for the above example

Computation of simple continued fractions

Given a number $x$, the coefficients($a_{i}$) in its continued fraction representation can be calculated recursively using

The above notation might not be obvious. Observing the structure of continued fraction with few coefficients will make them more evident:

SageMath provides functions continued_fraction and continued_fraction_list to work with continued fractions. Below is presented a simple implementation of continued_fractions.

def continued_fraction_list(xi):
    ai = floor(xi)
    if xi == ai: # last coefficient
        return [ai]
    return [ai] + continued_fraction_list(1/(x - ai))

Convergents of continued fraction

The $k^{th}$convergent of a continued fraction$x = [a_{0}; a_{1},\ a_{2},\ a_{3},\ a_{4},\ldots]$is the numerical value or approximation calculated using the first$k - 1$coefficients of the continued fraction. The first$k$convergents are

One of the immediate applications of the convergents is that they give rational approximations given the continued fraction of a number. This allows finding rational approximations to irrational numbers.

Convergents of continued fractions can be calculated in sage

sage: cf = continued_fraction(17/11)
sage: convergents = cf.convergents()
sage: cf
[1; 1, 1, 5]
sage: convergents
[1, 2, 3/2, 17/11]

Continued fractions have many other applications. One such applicable in cryptology is based on Legendre's theorem in diophantine approximations.

Theorem: if$\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}$, then$\frac{a}{b}$is a convergent of$x$.

Wiener's attack on the RSA cryptosystem works by proving that under certain conditions, an equation of the form$\mid x - \frac{a}{b} \mid$could be derived where$x$is entirely made up of public information and$\frac{a}{b}$is made up of private information. Under assumed conditions, the inequality$\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}$is statisfied, and the value$\frac{a}{b}$(private information) is calculated from convergents of$x$(public information), consequently breaking the RSA cryptosystem.

Introduction

Since we can add, subtract, multiply, divide even... what would be missing? Powering! I'm not talking about some power fantasy here, but rather introduce some really really important theorems. Fermat little's theorem proves useful in a great deal of situation, and is along with Euler's theorem a piece of arithmetic you need to know. Arguably the most canonical example of using these is the RSA cryptosystem, whose decryption step is built around Euler's theorem.

Fermat's Little Theorem

Since we want to talk about powers, let's look at powers. And because I like 7, I made a table of all the powers of all the integers modulo 7.

On the last row, there is a clear pattern emerging, what's going on??? Hm, let's try again modulo 5 this time.

Huh, again?! Clearly, there is something going on... Sage confirms this!

p, itworks = 1, True
for _ in range(100):
    p = next_prime(p)
    Fp = GF(p) # Finite Field of size p
    itworks &= all(Fp(x)^(p-1) == 1 for x in range(1,p))

print(itworks)
# True

Claim (Fermat's Little Theorem): Let$p$a prime.$\forall a\in\mathbb Z, a^p\equiv a~[p]$

When$a\neq 0$, this is equivalent to what we observed:$a^{p-1}\equiv 1~[n]$. There are several proofs of Fermat's Little Theorem, but perhaps the fastest is to see it as a consequence of the Euler's Theorem which generalizes it. Still, let's look a bit at some applications of this before moving on.

A first funny thing is the following:$\forall a\in\mathbb Z, a\cdot a^{p-2}\equiv a^{p-1}\equiv 1~[p]$. When$p>2$, this means we have found a non-trivial integer that when multiplied to$a$yields 1. That is, we have found the inverse of$a$, wow. Since the inverse is unique modulo$p$, we can always invert non-zero integers by doing this. From a human point of view, this is really easier than using the extended euclidean algorithm.

Discrete log problem

Given any group$G$and elements$a,b$such that $a^n=b$, the problem of solving for$n$is known as the disctete log problem (DLP). In sage, this can be done for general groups by calling discrete_log

sage: G = DihedralGroup(99)
sage: g = G.random_element()
sage: discrete_log(g^9,g) # note that if the order of g is less than 9 we would get 9 mod g.order()
9

Discrete log over $\left(\mathbb Z/n\mathbb Z\right)^*$

Typically, one considers the discrete log problem in $\left(\mathbb Z/n\mathbb Z\right)^*$, i.e. the multiplicative group of integers$\text{mod }n$. Explicitly, the problem asks for$x$given $a^x=b\pmod n$. This can be done by calling b.log(a) in sage:

sage: R = Integers(99)
sage: a = R(4)
sage: b = a^9
sage: b.log(a)
9

This section is devoted to helping the reader understand which functions are called when for this specific instance of DLP.

When$n$is composite and not a prime power, discrete_log() will be used, which uses generic algorithms to solve DLP (e.g. Pohlig-Hellman and baby-step giant-step).

When $n=p$is a prime, Pari znlog will be used, which uses a linear sieve index calculus method, suitable for $p < 10^{50} \sim 2 ^{166}$.

When $n = p^k$, SageMath will fall back on the generic implementation discrete_log()which can be slow. However, Pari znlog can handle this as well, again using the linear sieve index calculus method. To call this within SageMath we can use either of the following (the first option being a tiny bit faster than the second)

x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))

Example

Given a small prime, we can compare the Pari method with the Sage defaults

p = getPrime(36)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 879 µs, sys: 22 µs, total: 901 µs
# Wall time: 904 µs
# 123456789

time b.log(a)
# CPU times: user 458 ms, sys: 17 ms, total: 475 ms
# Wall time: 478 ms
# 123456789

time discrete_log(b,a)
# CPU times: user 512 ms, sys: 24.5 ms, total: 537 ms
# Wall time: 541 ms
# 123456789

We can also solve this problem with even larger primes in a very short time

p = getPrime(100)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 8.08 s, sys: 82.2 ms, total: 8.16 s
# Wall time: 8.22 s
# 123456789

Discrete log over $E(k)$

// elliptic curve discrete log functions

Overview

Given a composite integer $n$, can it be decomposed as a product of smaller integers (hopefully as a unique product of prime factors)?

As easy as it may sound, integer factorization in polynomial time on a classical computer stands one of the unsolved problems in computation for centuries!

Lets start dumb, all we need to do is check all the numbers $1 < p < n$ such that $p|n$or programmatically n%p==0

def factors(n):
    divisors = []
    for p in range(1,n):
        if n%p==0:
            divisors.append(p)
    return divisors

Seems like its an $O(n)$algorithm! whats all the deal about? By polynomial time, we mean polynomial time in $b$when $n$is a b-bit number, so what we looking at is actually a $O(2^b)$which is actually exponential (which everyone hates)

Now taking a better look at it, one would realize that a factor of $n$can't be bigger than $\sqrt{n}$ Other observation would be, if we already checked a number (say 2) to not be a divisor, we dont need to check any multiple of that number since it would not be a factor.

• Polynomial GCD

  • Euclidean GCD

  • Half-GCD for speed when e=0x10001

  • demo application for that one RSA related message attack?

• Resultant

  • eliminate multivariate polynomials at the expense of increasing polynomial degree

  • demo application for that one RSA Coppersmith short padding related message attack?

• Groebner Basis

  • what if you did GCD and Resultants at the same time, like whoa

  • and what if it took forever to run!

// Visual

// Symmetries

// Permutations

// symmetric polynomials

// discriminants

// resultants

A set$R$with two binary operations $+,\cdot:R\times R\to R$is a ring if the following holds:

• $R,+$is a commutative group with identity $0$

• $R,\cdot$is a monoid (group without the inverse axiom) with identity$1$.

• Distributivity: $a(b+c)=ab+ac,(a+b)c=ac+bc$

// ideals, diff types of domains

Overview

Gram-Schmidt orthogonalization is an algorithm that takes in a basis $\left\{b_i\right\}_{i=1}^n$ as an input and returns a basis $\left\{b_i^*\right\}_{i=1}^n$where all vectors are orthogonal, i.e. at right angles. This new basis is defined as

where $\mu_{i,j}$is the Gram-Schmidt coefficients.

One can immediately check that this new basis is orthogonal, meaning

Let $\mathcal B$be the matrix where the $i$th row is given by $b_i$and$\mathcal B^*$be the matrix where the $i$th row is given by $b_i^*$, then the Gram-Schmidt orthogonalization gives us $\mathcal B=\mu\mathcal B^*$where $\mu_{i,i}=1,\mu_{j,i}=0$and $\mu_{i,j}$is the Gram-Schmidt coefficient. As an example, consider the basis of a subspace of $\mathbb R^4$:

Instead of doing the Gram-Schmidt orthogonalization by hand, we can get sage to do it for us:

B = Matrix([
[-1, -2, 3, 1],
[-6, -4, 5, 1],
[5, 5, 1, -3]])

B.gram_schmidt()

This outputs two matrices, $\mathcal B^*$and $\mu$:

(
[-1 -2  3  1]  [ 1  0  0]
[-4  0 -1 -1]  [ 2  1  0]
[ 0  3  3 -3], [-1 -1  1]
)

One can quickly verify that $\mathcal B=\mu\mathcal B^*$ and that the rows of $\mathcal B^*$are orthogonal to each other.

A useful result is that

Intuitively, this tells us that the more orthogonal a set of basis for a lattice is, the shorter it is as the volume must be constant.

Exercises

1) Show that the basis $b_i^*$is orthogonal.

2) Verify that the output of sage is indeed correct.

3) Show that $\mu\mu^T=1$and $\mathcal B^*\mathcal B^{*T}$ is a diagonal matrix whose entries are $\left\lVert b_i^*\right\rVert$. Conclude that $\det\left(\mathcal B\mathcal B^T\right)=\det\left(\mathcal B^*\mathcal B^{*T}\right)=\prod_i\left\lVert b_i^*\right\rVert$.

4*) Given the Iwasawa decomposition $\mathcal B=LDO$where $L$is a lower diagonal matrix with $1$on its diagonal, $D$is a diagonal matrix and $O$an orthogonal matrix, meaning $OO^T=1$, show that $\mathcal B^*=DO$and $\mu=L$. Furthermore, prove that such a decomposition is unique.

A set$F$with two binary operations $+,\cdot:F\times F\to F$is a field if the following holds:

• $R,+$is a commutative group with identity $0$

• $R-\{0\},\cdot$is a commutative group with identity$1$.

• Distributivity: $a(b+c)=ab+ac,(a+b)c=ac+bc$

// field extensions, algebraic elements

Introduction

In this section, we hope to bring some intuitive understanding to the LLL algorithm and how it works. The LLL algorithm is a lattice reduction algorithm, meaning it takes in a basis for some lattice and hopefully returns another basis for the same lattice with shorter basis vectors. Before introducing LLL reduction, we'll introduce 2 key algorithms that LLL is built from, Gram-Schmidt orthogonalization and Gaussian Reduction. We give a brief overview on why these are used to build LLL.

As the volume of a lattice is fixed, and is given by the determinant of the basis vectors, whenever our basis vectors gets shorter, they must, in some intuitive sense, become more orthogonal to each other in order for the determinant to remain the same. Hence, Gram-Schmidt orthogonalization is used as an approximation to the shortest basis vector. However, the vectors that we get are in general not in the lattice, hence we only use this as a rough idea of what the shortest vectors would be like.

Lagrange's algorithm can be thought as the GCD algorithm for 2 numbers generalized to lattices. This iteratively reduces the length of each vector by subtracting some amount of one from another until we can't do it anymore. Such an algorithm actually gives the shortest possible vectors in 2 dimensions! Unfortunately, this algorithm may not terminate for higher dimensions, even in 3 dimensions. Hence, it needs to be modified a bit to allow the algorithm to halt.

Overview

There are a few issues that one may encounter when attempting to generalize Lagrange's algorithm to higher dimensions. Most importantly, one needs to figure what is the proper way to swap the vectors around and when to terminate, ideally in in polynomial time. A rough sketch of how the algorithm should look like is

def LLL(B):
    d = B.nrows()
    i = 1
    while i<d:
        size_reduce(B)
        if swap_condition(B):
            i += 1
        else:
            B[i],B[i-1] = B[i-1],B[i]
            i = max(i-1,1)
    return B

There are two things we need to figure out, in what order should we reduce the basis elements by and how should we know when to swap. Ideally, we also want the basis to be ordered in a way such that the smallest basis vectors comes first. Intuitively, it would also be better to reduce a vector by the larger vectors first before reducing by the smaller vectors, a very vague analogy to filling up a jar with big stones first before putting in the sand. This leads us to the following size reduction algorithm:

def size_reduce(B):
    d = B.nrows()
    i = 1
    while i<d:
        Bs,M = B.gram_schmidt()
        for j in reversed(range(i)):
            B[i] -= round(M[i,j])*B[j]
            Bs,M = B.gram_schmidt()
    return B

Next, we need to figure a swapping condition. Naively, we want

for all $i$. However, such a condition does not guarantee termination in polynomial time. As short basis vectors should be almost orthogonal, we may also want to incorperate this notion. Concretely, we want $\left|\mu_{i,j}\right|$to be somewhat small for all pairs of $i,j$, i.e. we may want something like

However, since $\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}$, this condition is easily satisfied for a sufficiently long $b_j^*$, which is not what we want. The key idea is to merge these two in some way and was first noticed by Lovász - named the Lovász condition:

It turns out that using this condition, the algorithm above terminates in polynomial time! More specifically, it has a time complexity of $O\left(d^5n\log^3B\right)$where we have$d$basis vectors as a subset of $\mathbb R^n$and $B$is a bound for the largest norm of $b_i$. $\frac14<\delta$ ensures that the lattice vectors are ordered roughly by size and $\delta<1$ensures the algorithm terminates.

Polynomial time proof

This follows the proof provided by the authors of the LLL paper. We first prove that the algorithm terminates by showing it swaps the vectors finitely many times. Let$d$be the number of basis vectors as a subset of $\mathbb R^n$. Let $d_i$be the volume of the lattice generated by $\left\{b_j\right\}_{j=1}^i$at each step of the algorithm. We have $d_i=\prod_{j=1}^i\left\lVert b_j^*\right\rVert$. Now consider the quantity

This quantity only changes whenever some $b_i^*$changes, i.e when swaps happen. Let's consider what happens when we swap $b_i$and $b_{i+1}$. Recall the Gram-Schmidt algorithm:

From this, see that when we swap $b_i$and $b_{i+1}$, $b_i^*$is replaced by $b_{i+1}^*+\mu_{i+1,i}b_i^*$. Now using the Lovász condition, we see that we have$\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2<\delta\left\lVert b_i^*\right\rVert^2$, hence the value of $d_i$must decrease by at least $\delta$, i.e. the new $d_i$is less than $\frac{d_i}\delta$. All other $d_j,j\neq i$must remain the same as the volume remains fixed when we swap basis vectors around. Hence at each swap, $D$decreases by $\delta$. This is why we need $\delta<1$.Now we are left with showing $d_i$is bounded from below then we are done.