2017-03-08.ipynb

Kernel: SageMath (stable)

Math 152: Intro to Mathematical Software

2017-03-08

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

** Lecture 24: Algebra and number theory (prep for cryptography): part 1**

(a/k/a preview of Math 187B, to be offered for the first time next quarter)

Announcements:

• This week's peer grading due Thursday, March 9 at 8pm, as usual. (Ignore the date typo on the HW.)

• Guest lectures next week:

  • Monday, March 13: Kartik Venkatram

  • Wednesday, March 15: Alina Bucur

• No sections on Monday, March 13.

• Office hours next week:

  • Zonglin: Thursday, March 16, 3:30-5:30 in APM 5748.

  • Me: Friday, March 17, 11-12 in APM 7202.

  • Peter: Friday, March 17, 12-1 and 3-4 in APM 6132.

• Next week's homework due Friday, March 17 at 8pm. Peer grading due Sunday, March 19 at 8pm.

  • The first half of this assignment is "normal" (number theory and cryptography).

  • The second half is freeform: create your own lecture! See the assignment for details.

• Please do your course evaluation (CAPE)! Evaluations close Monday, March 20 at 8am.

• HW1-6 grades are available on TritonEd, plus some attendance and peer grading scores. Remember, there is no final exam for this course.

A little number theory

It is very very easy to compute the greatest common divisor of two integers, even very large ones, because of the Euclidean algorithm.

m = 2^300 + 23
n = 2^325 - 73
gcd(m,n)

The same technique can be used to find, given two integers $m$ and $n$, two other integers $a$ and $b$ such that $am+bn = \gcd(m,n)$. This is sometimes called the extended Euclidean algorithm, which helps explain the notation in Sage.

d,a,b = xgcd(m,n)

d

a,b

a*m+b*n

xgcd(75, 20)

These values can be used to make explicit the Chinese remainder theorem: if $\gcd(m,n) = 1$, then every system of equations of the form [ x \equiv x_1 \pmod{m}, \qquad x \equiv x_2 \pmod{n} ] has a solution $x \in \mathbb{Z}$ (which is unique up to adding a mulitple of $mn$).

x1 = 37
x2 = 265
x = x1*b*n + x2*a*m
print(x%m, x%n)

By contrast, finding the prime factorization of a positive integer can be difficult. Not always, though.

factor(m) ## Takes a bit longer.

factor(n) ## Takes even longer, we won't wait for it.

factor(n+2) ## But this one is easy!

What makes the last example particularly easy is that you can test for the very small prime factors quickly (trial division), and then it turns out to be much easier to tell whether or not a big number is prime than to actually factor it. There are other features that make some numbers easier to factor than others, but more on this later.

Modular exponentiation

One reason for this is that it is easy to do modular exponentiation, i.e., the remainder of a^b upon division by c.

How not to do this:

(2^m) % n ## No dice

What does work:

mod(2,n)^m

## Or use pure python.
pow(2, m, n)

## Or do this in abstract-algebra style, by creating the ring of integers mod n and calculating there.
R = IntegerModRing(n)
R(2)^m

Question: how is this possible? Even working mod n, directly computing $2 \times ... \times 2$ with $m$ factors is not feasible.

One application of this is the Fermat test for primality. This is based on the little Fermat theorem: if $p$ is a prime number, then for any positive integer $a$, $a^p - a$ is divisible by $p$. (In the language of congruences, $a^p \equiv a \pmod{p}$.)

One possible proof (for the case $a=2$, but this can be extended to a general argument): in the binomial expansion [ (x+y)^p = x^p + \binom{p}{1} x^{p-1}y + \cdots + \binom{p}{p-1} xy^{p-1} + y^p ] all of the intermediate coefficients are divisible by $p$ (so plugging in $x=y=1$ gives the claim). For example...

P.<x,y> = PolynomialRing(ZZ) ## ZZ = the ring of integers
(x+y)^7

P.<x,y> = PolynomialRing(IntegerModRing(7))
(x+y)^7

The contrapositive of the little Fermat theorem is: if $a^p-a$ is not divisible by $p$, then $p$ is not prime. This test works extremely well!

mod(2,m)^m

mod(2,n)^n ## Couldn't factor it, but definitely not prime

is_prime(n) ## Uses this and some other methods

This method is not foolproof: it can return false positives for primality. Look up Carmichael numbers.

mod(2,561)^561

mod(3,561)^561

mod(17, 561)^561

Consequently, this method cannot be used to certify that a particular number is prime, only that it is not prime. There are efficient algorithms that can certify primality, but they are somewhat harder to describe. One important one is the (Agrawal-Kayal-Saxena (AKS) algorithm)[https://en.wikipedia.org/wiki/AKS_primality_test], which is both extremely simple and polynomial-time (though not as efficient in practice as some other methods). Kayal and Saxena were undergraduates at the time they discovered it (2002)!

One way to say this is that "prime numbers are easy to factor". The reason this is not an empty statement is because you have to know when to stop factoring!

In any case, the Fermat test is so effective that any number that passes it is probably prime, and this is sometimes good enough (though not for cryptography!).

for n in range(10^4):
    m = 10^500 + n
    if mod(2,m)^m == 2 and not is_prime(m): print m
print("no more examples found")

The fact that prime numbers are (relatively) easy to identify makes it possible to have functions like this:

next_prime(10^125) -10^125

Multiplicative order and primitive roots

Let $a,n$ be integers with $\gcd(a,n) = 1$. Using the extended Euclidean algorithm as above, one can find a multiplicative inverse of $a$ modulo $n$, i.e., a value $b$ such that $ab \equiv 1 \pmod{n}$. In fact, Sage will do this automatically.

a = 577
n = 6825
gcd(a,n)

mod(a,n)^(-1)

## Or if you prefer abstract algebra syntax:
R = IntegerModRing(n)
R(a)^(-1)

As a consequence of the existence of the multiplicative inverse, there always exists a positive integer $d$ such that $a^d \equiv 1 \pmod{n}$. (There must be two powers that coincide mod $n$, and we can cancel the powers of $a$ from one side.)

If $n$ is prime, the little Fermat theorem implies that $d = n-1$ always works (although it need not be the smallest such value; more on this in a moment). For general $n$, there is a generalization of the Fermat theorem due to Euler: we have $a^{\phi(n)} \equiv 1 \pmod{n}$ where $\phi(n)$ denotes the Euler phi function (or totient function): if $n$ has prime factorization $p_1^{e_1} \times p_2^{e_2} \times \cdots$, then [ \phi(n) = (p_1 - 1)p_1^{e_1}-1(p_2-1)p_2^{e_2-1} \cdots. ] For those who know group theory: recall that this works because the residue classes mod $n$ which have no common factor with $n$ form a group under multiplication, and $\phi(n)$ is its order.

factor(561)
euler_phi(561)

list(factor(561))

for (d,e) in factor(561):
    print euler_phi(d), 560 % euler_phi(d) #Aha!

So now it makes sense to consider the smallest positive integer $d$ such that $a^d \equiv 1 \pmod{n}$. This integer must divide $\phi(n)$, otherwise the remainder of $\phi(n)$ mod $d$ would be an even smaller value. (Or use group theory!) This $d$ is called the multiplicative order of $d$ mod $n$.

for d in range(1, 17):
    print (d, multiplicative_order(mod(d,17)))

Important result: if $n$ is prime, then there is always at least one value of $a$ for which the multiplicative order of $a$ mod $n$ is equal to the maximum possible value $\phi(n) = n-1$. Any such $a$ is called a primitive root mod $n$. These play an important role in the use of discrete logarithms in cryptography.

(Abstract algebra interpretation; if $n$ is prime, then $(\ZZ/n\ZZ)^*$ is a cyclic group!)