2017-03-10.sagews

%md
# Math 152: Intro to Mathematical Software
### 2017-03-10
### Kiran Kedlaya; University of California, San Diego
### adapted from lectures by William Stein, University of Washington

### **Lecture 25: Algebra and number theory (prep for cryptography): part 2**

Math 152: Intro to Mathematical Software

2017-03-10

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

Lecture 25: Algebra and number theory (prep for cryptography): part 2

%md

Announcements:
- 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.
- Regarding grade cutoffs: as a minimum, 90% will be at least an A-, 80% at least a B-, 70% at least a C-. However, I will lower the cutoffs if necessary to achieve a distribution comparable to other upper-division courses (e.g., under no circumstances will the A range include fewer than 20% of the class).

Announcements:

• 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.

• Regarding grade cutoffs: as a minimum, 90% will be at least an A-, 80% at least a B-, 70% at least a C-. However, I will lower the cutoffs if necessary to achieve a distribution comparable to other upper-division courses (e.g., under no circumstances will the A range include fewer than 20% of the class).

This might be useful: https://wiki.sagemath.org/quickref?action=AttachFile&do=get&target=quickref-nt.pdf

Back to the Chinese remainder theorem

Last time, I demonstrated how to use the extended Euclidean algorithm to make the Chinese remainder theorem explicit. What was that function called again?

xkcd(217)

e to the pi Minus pi

Source: http://xkcd.com/217

There is also a built-in command for this!

(a,b,m,n) = (5,7,10^25 - 11, 10^37 + 28)
x = crt(a,b,m,n); print(x)

30511599324013243201720660000000000085432478107237080964817855

(a,b), (x%m, x%n)

((5, 7), (5, 7))

x = crt(3, 0, 6, 9); x

9

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)

1

mod(a,n)^(-1)

2413

1/mod(a,n)

2413

a.inverse_mod(n)

2413

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

2413

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)

3 * 11 * 17 320

list(factor(561))

[(3, 1), (11, 1), (17, 1)]

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

2 0 10 0 16 0

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 $a$ mod $n$.

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

(1, 1) (2, 8) (3, 16) (4, 4) (5, 16) (6, 16) (7, 16) (8, 8) (9, 8) (10, 16) (11, 16) (12, 16) (13, 4) (14, 16) (15, 8) (16, 2)

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 are relevant for discrete logarithms, more on which later.

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

primitive_root?

File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/arith/misc.py
Signature : primitive_root(n, check=True)
Docstring :
Return a positive integer that generates the multiplicative group
of integers modulo n, if one exists; otherwise, raise a
"ValueError".

A primitive root exists if n=4 or n=p^k or n=2p^k, where p is an
odd prime and k is a nonnegative number.

INPUT:

* "n" -- a non-zero integer

* "check" -- bool (default: True); if False, then n is assumed to
  be a positive integer possessing a primitive root, and behavior
  is undefined otherwise.

OUTPUT:

A primitive root of n. If n is prime, this is the smallest
primitive root.

EXAMPLES:

   sage: primitive_root(23)
   5
   sage: primitive_root(-46)
   5
   sage: primitive_root(25)
   2
   sage: print([primitive_root(p) for p in primes(100)])
   [1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5]
   sage: primitive_root(8)
   Traceback (most recent call last):
   ...
   ValueError: no primitive root

Note: It takes extra work to check if n has a primitive root; to
  avoid this, use "check=False", which may slightly speed things up
  (but could also result in undefined behavior).  For example, the
  second call below is an order of magnitude faster than the first:

   sage: n = 10^50 + 151   # a prime
   sage: primitive_root(n)
   11
   sage: primitive_root(n, check=False)
   11

primitive_root(17)

3

a = primitive_root(37); print(a)

2

l = [mod(a,37)^i for i in range(36)]
l.sort()
l

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]

Discrete logarithms

%md
Let $p$ be a prime. Suppose that $a$ is a primitive root mod $p$. Then for any $m$ not divisible by $p$, the *discrete logarithm* of $m$ mod $p$, with respect to the base $a$, is the integer $g \in \{0,\dots,p-2\}$ such that $a^g \equiv m \pmod{p}$.

Let $p$ be a prime. Suppose that $a$ is a primitive root mod $p$. Then for any $m$ not divisible by $p$, the discrete logarithm of $m$ mod $p$, with respect to the base $a$, is the integer $g \in \{0,\dots,p-2\}$ such that $a^g \equiv m \pmod{p}$.

98

mod(98,101).log(mod(2,101))

19

This looks straightforward enough, but it is actually very difficult to compute discrete logarithms! There is no obvious trick for this.

As a result, the function $g \mapsto a^g \pmod{p}$ is often treated as a one-way function: it is easy to compute but hard to invert. (This is a practical definition, not a formal mathematical one, because we (probably) cannot say for sure that it is actually hard to compute, as opposed to our merely being ignorant.)

In any case, the existence of one-way functions makes it feasible to have public-key cryptography, where everyone knows how to encrypt a message but only one person knows how to decrypt; or public-key signature schemes, where only one person knows to encrypt but everyone knows how to decrypt.

The difficulty of integer factorization behaves in a similar (but slightly more complicated) way: if $p,q$ are two prime numbers, then it is easy to form the product $pq$ but much harder to recover $p$ and $q$ from the product.

Quadratic residues

For $n$ a positive integer, an integer $a$ is a quadratic residue mod $n$ if there exists a perfect square congruent to $a$ modulo $n$.

For example, say $n = 7$. To test whether a perfect square is congruent to $a$ modulo $n$, we need only test $0^2, \dots, 6^2$. Their residues modulo $7$ are $0, 1, 4, 2, 2, 4, 1$.

quadratic_residues(107) # for any p, will include 0 and (p-1)/2 other values.

[0, 1, 3, 4, 9, 10, 11, 12, 13, 14, 16, 19, 23, 25, 27, 29, 30, 33, 34, 35, 36, 37, 39, 40, 41, 42, 44, 47, 48, 49, 52, 53, 56, 57, 61, 62, 64, 69, 75, 76, 79, 81, 83, 85, 86, 87, 89, 90, 92, 99, 100, 101, 102, 105]

For $p$ an odd prime, the list of quadratic residues mod $p$ will include 0 plus $(p-1)/2$ other values. (If we run over $\{0,\dots,p-1\}$, no residue can occur more than twice: if $x^2 \equiv y^2 \pmod{p}$, then $(x+y)(x-y)$ is divisible by $p$, and so one of $x+y$ or $x-y$ must be.)

For $p$ an odd prime and $a$ not divisible by $p$, $a$ is a quadratic residue modulo $p$ if and only if its discrete logarithm (with respect to any base) is even.

The Legendre symbol $\left( \frac{a}{p} \right)$ is defined to be $0$ if $a \equiv 0 \pmod{p}$, $+1$ if $a$ is a nonzero quadratic residue modulo $p$, and $-1$ if $a$ is not a quadratic residue mod $p$. This symbol has the multiplicativity property: [ \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right). ] (The less-than-obvious part is that the product of two quadratic nonresidues is a quadratic residue. This would fail if $p$ were not prime.)

legendre_symbol(5, 7)

-1

p = next_prime(10^70)
%time
legendre_symbol(3, p) ## How is this feasible?? No way we are exhausting over all residue classes mod p!

1 CPU time: 0.10 s, Wall time: 0.10 s

The law of quadratic reprocity (originally proved by Gauss) states that if $p,q$ are distinct odd primes, then [ \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{(p-1)(q-1)/4}. ] That is, the two Legendre symbols agree if either $p$ or $q$ is congruent to 1 mod 4, and disagree if they are both congruent to 3 mod 4.

If $a$ is not prime, you can apply quadratic reciprocity by first factoring $a$. But this is not necessary: if one defines the Kronecker symbol to extend the Legendre symbol via the rule [ \left( \frac{a}{b_1} \right) \left( \frac{a}{b_2} \right) = \left( \frac{a}{b_2} \right), ] then the formula [ \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{(p-1)(q-1)/4}. ] extends to all odd positive integers $p,q$.

This still leaves the prime 2, but there is another formula of Gauss to handle this case: [ \left( \frac{2}{p} \right) = (-1)^{(p-1)/8}. ] That is, if $p$ is an odd prime, then 2 is a quadratic residue mod $p$ if $p$ is congruent to 1 or 7 mod 8, and a quadratic nonresidue mod $p$ if $p$ is congruent to 3 or 5 mod 8.

%md
Upshot: you can compute Legendre (and Kronecker) symbols quickly using a form of the Euclidean algorithm!

Upshot: you can compute Legendre (and Kronecker) symbols quickly using a form of the Euclidean algorithm!

%time 
a = next_prime(10^31)
b = next_prime(10^32)
legendre_symbol(a, b)

-1 CPU time: 0.01 s, Wall time: 0.01 s