For those who are interested how is my thesis evolving, this is the brief summary of my notes and afterthoughts of my talk today (since nothing gives you more motivation to do things than dissatisfaction with what you've just done).
Crypto with public key
Main advantage: anybody can see the public key, so we don't have to distribute the key secretly. However, we are the only ones who can decrypt the message, so even if intercepted, the attacker cannot read it without the secret key.
RSA
We pick a number $n = pq$, a product of two large prime numbers (each of some $150$ digits) and use it as the (public) modulus. Then we pick any $e \in \mathbb{N}$ such that $\operatorname{gcd}(e, \phi(n))= 1$ and use it as the public key.
- Anyone who wants to communicate with us takes their message $m$ and computes $m^e$ mod $n$, which they send us,
- To decrypt the message, we compute $(m^e)^d$ mod $n$, where $d$ is the unique inverse of $e$ modulo $\phi(n)$, using \textit{Lagrange} theorem we get that $m^{de} \equiv m$ mod $n$.
It is believed that the only way to compute the inverse $d$ is to know the factorization of $n$ to compute $\phi(n)$, however, knowing $\phi(n) = (p-1)(q-1) = n-p-q+1$ is the same as knowing both $p$ and $q$, hence the system is secure as long as we can't factor large numbers easily.
Complexity rudiments
We make vague remarks about the asymptotic runing time of
- $f(n)$: $O(g(n))$, if $\limsup \frac{f(n)}{g(n)} < \infty$ for $n \rightarrow \infty$
- $o(g(n))$, if $|\frac{f(n)}{g(n)} | \rightarrow 0$ for $n \rightarrow \infty$
Informally we can say that $f(n) = O(g(n)) $ if $|\frac{f(n)}{g(n)} | < K$ for $n$ large enough and $f(n) = o(g(n))$ if becomes negligibly small compared to the function $g(n)$. Hence $o(1)$ is the same as a constant converging to $0$. We will always be concerned about the number of digits (that is, approximately $\log n$), rather than size of $n$ itself. We say that the complexity is then
- polynomial, if $g(n)$ is a polynomial of $\log n$,
- exponential, if $f(n) = O(n^\alpha)$ for some $\alpha$ but not $O(n^\beta)$ for some $0 <\beta < \alpha$
- subexponential, if it is halfway in between, not polynomial and better than exponential, that is, if it is $o(n^\alpha)$ for every $\alpha > 0$ but not polynomial
Factorization of integers
Given a number $n$, we want to factor it into prime numbers. We may suppose that our number is not a prime, either because we know it has factors implicitly or because it has failed some of the standard primality tests (for instance the Rabin Miller test). A very simple factorization scheme is the trial division:
- We start dividing $n$ by small numbers, if it is divisible, we divide, to get a smaller number.
- We always find the complete factorization
- If the number is a product of two primes of approximately the same size, then we need to go all the way to $\sqrt{n}$.
- Even if we try to divide only by prime numbers, we need to try $\pi (n) \sim \frac{\sqrt{n}}{\log \sqrt{n}} $, which is still a lot.
Exploiting $(\mathbb{Z}/n\mathbb{Z})^{\times}$
We know that if $p|n$, then we have a surjective map $(\mathbb{Z}/n\mathbb{Z})^{ \times } \twoheadrightarrow (\mathbb{Z}/p\mathbb{Z})^{ \times}$, hence the idea is to perform computations in the first group that could theoretically give us the unit element in the second group, say $x \equiv 1$ mod $p$, then we have of course that $\operatorname{gcd}(n,x-1) > 1$ and we hope to factor $n$. The typical example is the Pollard's $p-1$ method, which works well if we have a prime divisor $p$ such that $p-1$ is a smooth number, that is, a number divisible only by small primes.
- We pick a pivot $a$ and compute the sequence $a, a^2, a^6, \dots, a^{k!}$ modulo $n$,
- Because $k!$ is only divisible by a small prime numbers, if $p-1$ is smooth, we will soon get that $a^{k!}$ is the unit modulo $p$,
- By computing $\operatorname{gcd}(a^{k!}-1,n) >1$ we hope to get a factor of $n$.
Using the same principle (that is, a group defined modulo $n$ and the reduction homomorphism to a group defined modulo $p$), we can obtain a similar algorithm using the arithmetic of elliptic curves (sets of homogeneous solutions $(x:y:1)$ of the equations of the form $y^2z = x^3+Axz^2+Bz^3$, where $4A^3+27B^2 \neq 0$), which has a group structure modulo any prime number with neutral element $(0:1:0)$. Since any non-invertible element would lead to factor of $n$, we pretend that we have a group defined modulo $n$ as well. We compute in an analogous way the powers of some point $P=(a:b:1)$, hoping to get the neutral element modulo $p$, then the $z-$coordinate has to be divisible by $p$ and we can hope to get a nontrivial factor $\operatorname{gcd}(n,z_p) >1$, if we fail, we use a different elliptic curve or a different point.
This algorithm is so useful because there are \textit{many} elliptic curves and their groups of points have around $p$ elements in a \textit{fairly random} manner, so this works if there is a smooth value close to $p$ and we are lucky enough to hit upon such a curve. Heuristic arguments and reality shows that we are likely to be lucky, especially if we have a small factor, say $30$ digits.
Congruent squares
Another arithmetic fact is that if $n$ is not an odd prime power, then if
$$x^2 \equiv 1 \, \operatorname{mod} \, n$$
Then $x \not\equiv \pm 1$ mod $n$ with probability at least $\frac{1}{2}$. Indeed, for an odd prime power the group of invertible elements is always cyclic, therefore the only solutions to (\ref{square_equal_one}) are $\pm1$. But testing whether a number is a power of a prime number is easy, we can do it by simple binary search:
- For all possible exponents $d$ (that is, while $2^d < n$), we will check, whether $n$ is a square, \item by halving the intervals, we approximate the closest $d-$th power to $a$.
- That is, starting with the interval $[2,a]$, we compute the value $b^d$ for the midpoint $b$, if we have $b^d > a$, we continue with the midpoint of the left half-interval, if we have $b^d < a$ we use the midpoint of the right half-interval, if we have $b^d = a$ at some point, we are done.
- If we cannot halve the interval any further, $a$ is not a $d-$th power, so we raise the exponent.
Forming squares using products
It is easy to see that to use the trick with congruent squares, it is enough to produce independently two squares $x^2 \equiv y^2$. One of the easiest examples for this is the quadratic sieve. Here we will work with values $x^2$ (which always produce squares) and $y = x^2-n$. If $n$ is odd, we can always hope to find a $y^2 = x^2-n$ (since $n=ab = (\frac{a+b}{2})^2+(\frac{a-b}{2})^2$). However, we observe that if for some values $x_i$ we have $\prod (x_i^2-n) = y^2$, we get the desired relation.
This process works in general: if we manage to produce independently sequences $x_i$, $y_i$ such that $x_i \equiv y_i$ modulo $n$ and $\prod x_i = x^2, \prod y_i = y^2$, we have $x^2\equiv y^2$ mod $n$ and we hope to get the desired factors. Smooth numbers Common sense dictates that if a number (such as $x^2-n$ in the quadratic sieve) is divisible by a large prime number, we are less likely to use it in our product, because the numbers divisible by larger primes are sparse.
Hence we naturally arrive at the definition of a smooth number:
A number $a$ is $B-$smooth if all of its prime factors are smaller than $B$.
Supposing we have a collection of smooth numbers (or in general numbers divisible only by prime numbers $p \in \mathbb{P}$ in some set of prime numbers), for which we know the complete factorization into prime numbers. If we wish, we can also use negative integers and remember the sign of each integer.
- Call the prime numbers $p \in \mathbb{P}$ the factorization basis,
- For every number $a$, form the exponent row vector $v(a) = (\operatorname{ord}_p(a))_p$, that is, for every prime number $p \in \mathbb{P}$ remember the highest power with which $p $ divides $a$ (if we need, we can include one entry remembering the sign of the number), since we are only interested in the product being a square, we deduce that we can consider the exponent vector only modulo $2$,
- Because of exponent rules, we see that forming a square as a product of $x_i$ is the same as forming a linear dependency of $v(x)_p$ over $\mathbb{F}_2$,
- Hence we are in the safe homelands of linear algebra!
From basic linear algebra we know that we are sure to find a linear dependency if we have more row vectors than $\# \mathbb{P}$. This also shows the strengths and weaknesses of this approach. If we use many prime numbers, our numbers are more likely to be smooth. However, if we use too large a factorization basis, we will have to find a great many of them and we will have to deal with huge matrices afterwards.
Number field sieve
So now we are ready to appreciate the usage of number rings. By definition, a number ring is a subring of a number field, that is a finite extension of $\mathbb{Q}$. We are only going to need the subrings of the form $\mathbb{Z}[\alpha] \cong \mathbb{Z}[x]/(f(x))$ for some $f(x) \in \mathbb{Z}[x]$ monic irreducible. For simplicity, we will discuss the most widely spread form of the number field sieve, that is, on one side, we will consider numbers of the form $a-bm$, $\operatorname{gcd}(a,b)=1$ such that $m $ is a root of $f(x)$ modulo $n$. Then we have a map $$\mathbb{Z} \times \mathbb{Z}[\alpha] \rightarrow \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$$ sending $(m,\alpha) \mapsto (m,m)$, and hence $(a-bm, a-b\alpha) \mapsto (a-bm,a-bm)$. Hence we have pairs of numbers $(a-bm,a-b\alpha)$ that are congruent to each other modulo $n$.
We have seen how to construct a square from a set of integers via sieving with small prime numbers. We will do this simultaneously by sieving also the numbers $a-b\alpha$. In the following sections, we will define all the important notions and show that sieving can indeed be done.
Constructing the polynomial
In practice, we choose the degree of the polynomial $f(x)$ to be a small number $d$ (say up to $10$), pick $m$ close to $\sqrt[d]{n}$ and write $n = m^d+a_{d-1}m^{d-1}+\dots+a_0$ in basis $m$. Then we set $f(x ) = x^d + a_{d-1}x^{d-1}+\dots+a_0$. We may assume that this polynomial is going to be irreducible, because random polynomials are irreducible and a non-trivial factor would give us a factor of $n$. But it is customary that one does spend some time on picking the polynomial to find the best candidate for making the rest of the computations simple.
Analogies with $\mathbb{Z}$
In general, $\mathbb{Z}[\alpha]$ is not going to be a unique factorization domain. For simplicity, let us assume it is. Then we have the notion of a prime element that substitutes prime numbers. We also have the units that correspond to the sign bit in integers. In general, the unit group is going to be much larger than just $\{\pm 1\}$, but it is the theorem of \textit{Dirichlet} that the unit group is finitely generated and the rank can be bounded by the degree of the polynomial $f$.
Small numbers
We want to have a smooth numbers, that is, numbers divisible only by small primes. For this we first need to define the notion of smallness. As the absolute value on $\mathbb{Z}$ is multiplicative, we have a similar notion of multiplicative map $$\operatorname{Norm}: \mathbb{Z}[\alpha] \rightarrow \mathbb{Z}$$ Since norm can be defined as the determinant of the linear map on the finitely dimensional $\mathbb{Q}-$vector space $\mathbb{Q}(\alpha)$, we get that $$\operatorname{Norm}(\beta \gamma) = \operatorname{Norm}(\beta) \operatorname{Norm}(\gamma)$$ and with the help of characteristic polynomials of linear maps and the classic theory of algebraic integers we can show that $\operatorname{Norm}(\mathbb{Z}[\alpha]) \subset \mathbb{Z}$. From the multiplicativity and integrality of norm we have that $$\beta \mid \gamma \text{ in }\mathbb{Z}[\alpha] \Rightarrow \operatorname{Norm}(\beta) | \operatorname{Norm}(\gamma)\text{ in }\mathbb{Z}$$
This leads to the following definition:
a number $a-b\alpha$ is $B-$smooth if $\operatorname{Norm}(a-b\alpha)$ is a $B-$smooth integers.
Primes
As we have already mentioned, the role of prime numbers is played by prime elements of $\mathbb{Z}[\alpha]$, that is, elements $\pi \in \mathbb{Z}[\alpha]$ such that $(\pi)$ is a prime ideal of $\mathbb{Z}[\alpha]$. We can show that in fact $\operatorname{Norm}(\beta) = \# (\mathbb{Z}[\alpha]/(\beta))$. As prime ideals are the same as kernels of homomorphisms into integral domains, from the finiteness of norm we get that they are actually kernels of homomorphisms from $\mathbb{Z}[\alpha] \rightarrow \mathbb{F}_q$ into finite fields.
Hence we see that the norm of a prime element is always a power of some prime number $p$.
Sieving
Now we will clarify the restriction to numbers $a-b\alpha$, $a,b$ coprime. As we have seen, prime ideals correspond to kernels of homomorphisms into finite fields. Suppose that we have a prime element $\pi$ such that $\pi | a-b\alpha$. Then $a \equiv b\alpha$ mod $(\pi)$. Because $\operatorname{gcd}(a,b)=1$, we cannot have $ab \equiv 0$ modulo $(\pi)$ (because then $p=$ char($\mathbb{F}_q$) would divide both $a$ and $b$). Therefore, $\alpha \equiv \frac{a}{b} \operatorname{mod }\, (\pi)$ and $\mathbb{F}_q = \mathbb{F}_p$ (we call such primes the degree $1$ primes). But in this case $\operatorname{Norm}(\pi) = p$ and $p \mid \operatorname{Norm}(a-b\alpha)$.
We have deduced that if $a,b$ are coprime, then the only primes dividing $a-b\alpha$ are going to correspond to kernels of homomorphisms of $\mathbb{Z}[\alpha]$ into finite prime fields and those correspond to roots of $f(x)$ modulo $p$. However, it can easily be shown that the norm $N(a-b\alpha) = b^d f(\frac{a}{b}) = g(a,b)$, which is a homogeneous polynomial in $a$ and $b$. So we have the following:
- For each prime of degree $1$ we remember the characteristic of the residue field $p$ and the unique root $r_p$ of $f(x)$ modulo $p$ that gives rise to this prime element,
- a necessary condition for $\pi$ to divide $a-b\alpha$ is that $p \mid \operatorname{Norm}(a-b\alpha)$,
- since $\operatorname{Norm}(a-b\alpha)$ is a homogeneous polynomial, we clearly see that $p| g(a,b)$ if and only if $p |g(a+mp, b+np), m,n \in \mathbb{Z}$,
- if $p | \operatorname{Norm}(a-b\alpha)$, then $\pi$ divides $a-b\alpha$ if and only if $\frac{a}{b} \equiv r_p$ modulo $p$
Obstructions
Using the very same tools as before we can produce a number which has even exponent vector for the primes in our factorization basis and is not divisible by any other prime. However, divisibility is always only up to unit. Even though we know that the unit group is finitely generated, in general we do not know how to find the generators. So using the sieving process we only find a number which is a square only up to a unit.
General case
In general, however, $\mathbb{Z}[\alpha]$ is not going to be a unique factorization domain. This is most easily saved by going from elements to ideals. Then we have the following:
- There is a subring $\mathfrak{O}_K$ of the field $K = \mathbb{Q}[\alpha]$ such that $\mathbb{Z}[\alpha] \subset \mathfrak{O}_K$ and $\mathfrak{O}_K$ admits unique factorization into prime ideals, however, this ring need not be monogenic (of the form $\mathbb{Z}[\beta]$)
- In general, ideals of $\mathfrak{O}_K$ are not principal, however, the quotient $\mathfrak{I}(K) / \mathfrak{P}(K)$ of all ideals modulo principal ideals is a finite group
- All prime ideals in $\mathbb{Z}[\alpha]$ come from factors of $f(x)$ the minimal polynomial of $\alpha$ For all but finitely many prime ideals $\pi$ of $\mathbb{Z}[\alpha]$ there is a unique prime ideal $\mathfrak{p}$ of $\mathfrak{O}_K$ such that $\pi = \mathfrak{p } \cap \mathbb{Z}[\alpha]$
- For all $\gamma \in \mathbb{Z}[\alpha]$ we have $f'(\alpha)\gamma \in \mathfrak{O}_K$.
From this, we see that if we deal with prime ideals, we see that we can transform the computation from $\mathbb{Z}[\alpha]$ into the (possibly unknown) ring $\mathfrak{O}_K$, where unique factorization holds. But then we have all sorts of obstructions...
To be continued...
Note: I wonder if I can still use in my bachelor thesis the things I write on my blog, without being accused of plagiarism. However, I need not worry about these notes, since anyone who reaches this note is bound to agree that this text is in desperate need of revision and rewriting.
