Notes on “A Friendly Introduction to Number Theory”

Chap.1 What Is Number Theory?

Number Theory is the study of the set of positive whole numbers $1, 2, 3, 4, 5, 6, 7, …$, which are often called the set of natural numbers. We will especially want to strudy the relationship between different sorts of numbers.

The main goal of number theory is to discover interesting and unexpected relationships between different sorts of numbers and to prove that these relationships are true.

Number Theory is partly experimental (comes first) and partly theoretical (follows).

Steps to follow:

Accumulate data, usually numerical, but sometimes more abstract in nature.
Examine the data and try to find patterns and relationships.
Formulate conjectures (i.e., guesses) that explain the patterns and relationships. These are frequently given by formulas.
Test your conjectures by collectiong additional data and checking whether the new information fits your conjectures.
Devise an argument (i.e., a proof) that your conjectures are correct.

数论里面的定理，大多都是从一些数据之间发现关系，再去总结关系，形成猜想，然后用严谨的数学语言证明，才最终成为了定理。

Chap.2 Pythagorean Triples

Why we study Pythagorean triples, or further more, Number Theory?

There is at least one good reason to study Pythagorean triples, and it’s the same reason why it is worthwhile studying the art of Rembrandt and the music of Beethoven. There is a beauty to the ways in which numbers intereact with one another, just as there is a beauty in the composition of a painting or a symphony. To appreciate this beauty, one has to be willing to expend a certain amount of mental energy. But the end result is well worth the effort. Our goal in this book is to understand and appreciate some truly beautiful mathematics, to learn how this mathematics was dicovered and proved, and maybe even to make some original contributions of our own.

单独的数字看起来是很单调的，不美的。但是正是数字之间的种种关系，隐含着美，这就是数学家研究数字的乐趣所在。

A primitive Pythagorean triple (or PPT for short) is a triple of numbers (a, b, c) such that a, b, and c have no common factors and satisfy a^2 + b^2 = c^2.

Theorem 2.1 (Pythagoream Triples Theorem). We will get every primitive Pythagorean triple (a, b, c) with a odd and b even by using the formulas a = st, b = (s^2 - t^2)/2, c = (s^2 + t^2)/2, where s > t >= 1 are chosen to be any odd integers with no common factors.

上式可以任意生成primitive Pythagorean triples。

Chap.3 Pythagorean Triples and the Unit Circle

Theorem 3.1. Every point on the circle x^2 + y^2 = 1 whose coordinates are rational numbers can be obtained from the formula (x, y) = ( (1-m^2)/(1+m^2), 2m/(1+m^2) ) by substituting in rational numbers for m [except for the point (-1, 0) which is the limiting value as m -> ∞].

数形结合

Chap.4 Sum of Higher Powers and Fermat’s Last Theorem

Fermat’s Last Theorem. The equation a^n + b^n = c^n has no solutions in positive integers if n >= 3.

… Finally, in 1994, Andrew Wiles completed the proof of Fermat’s 350-year-old claim.

费马大定理！

Chap.5 Divisibility and the Greatest Common Divisor

整除的定义 (divisibility)

最大公因数的定义 (Greatest common divisor)

互质的定义 (relatively prime)

如何找两个数的最大公因数？ –> Euclidean algorithm

1
2
3
4


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

即使a, b很大，用上面这个方法也可以在极短时间内找到两者的最大公因数。

Chap.6 Linear Equations and the Greatest Common Divisor

ax + by is divisible by gcd(a, b).

Conclusion: The smallest positive value of ax + by is equal to gcd(a, b).

Theorem 6.1 (Linear Equation Theorem). Let a and b be nonezero integers, and let g = gcd(a, b). The equation ax + by = g always has a solution (x1, y1) in integers, and this solution can be found by the Euclidean algorithm method described earlier. Then every solution to the equation can be obtained by substituting integers k into the formula (x1 + kb/g, y1 - ka/g).

1
2
3
4
5
6
7
8
9


def egcd(a, b):
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q, r = divmod(a, b)
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, r
    return u, v, a

扩展欧几里得算法，可以用来求解线性(同余)方程和求模逆元。

Chap.7 Factorization and the Fundamental Theorem of Arithmetic

Lemma 7.1. Let p be a prime number, and suppose that p divides the product ab. Then either p divides a or p divides b (or p divides both a and b).

素因数的一个性质，可以为后面很多定理的证明提供方便。

Theorem 7.2 (Prime Divisibility Property). Let p be a prime number, and suppose that p divides the product a1a2...ar. Then p divides at least one of the facotors a1, a2, …, ar.

上述引理7.1的推广

Theorem 7.3 (The Fundamental Theorem of Arithmetic). Every integer n >= 2 can be factored into a product of primes n = p1p2...pr in exactly one way.

算术基本定理。所有数均可表示成质数的乘积，这就是质数的特殊之处。

Proof:

The number n can be factored into a product of primes in some way. (Induction, 即数学归纳法)
There is only one such factorization (aside from rearranging the factors). (Theorem 7.2)

Chap8. Congruences

同余的定义、符号。同余满足加减法(其实就是加法)，以及乘法，但不满足常规除法(模运算下的除法其实就是乘以模逆元)。

Theorem 8.1(Linear Congruence Theorem). Let a, c, and m be integers with m >= 1, and let g = gcd(a, m).

If g ∤ c, then the congruence ax ≡ c (mod m) has no solutions.
If g | c, then the congurence ax ≡ c (mod m) has exactly g incongruent solutions. To find the solutions,
1. first find a solution (u0, v0) to the linear equation au + mv = g.
2. Then x0 = cu0 / g is a solution to ax ≡ c (mod m), and a complete set of incongruent solutions is given by x ≡ x0 + km/g (mod m) for k = 0, 1, 2, ..., g-1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def linearCongruenceSolver(a, c, m):
    '''
    Solve x such that `a * x ≡ c (mod m)`
    returns all the possible *x*s (mod m), None if no solution.
    '''
    g = gcd(a, m)
    if c % g:
        return None
    u0 = egcd(a, m)[0]
    return [(c * u0 + k * m) // g % m for k in range(g)]

线性同余方程的通解

Theorem 8.2 (Polynomial Roots Mod p Theorem). Let p be a prime number and let f(x) = a0x^d + a1x^(d-1) + ... + ad be a polynomial of degree d >= 1 with integer coefficients and p ∤ a0. Then the congruence f(x) ≡ 0 (mod p) has at most d incongruent solutions.

以质数为模数的非线性同余方程的非同余解的个数取决于最高次数。

Chap.9 Congruences, Powers, and Fermat’s little Theorem

Theorem 9.1 (Fermat’s Little Theorem). Let p be a prime number, and let a be any number with a ≢ 0 (mod p). Then a^(p-1) ≡ 1 (mod p).

费马小定理！质数的神奇之处。

Fermat’s Little Theorem can be used to show that a number is not a prime without actually factoring it.

Lemma 9.2. Let p be prime number and let a be a number with a ≢ 0 (mod p). Then the numbers a, 2a, 3a, ..., (p-1)a (mod p) are the same as the numbers 1, 2, 3, ..., (p-1) (mod p), although they may be in a different order.

推导费马小定理所需的引理。

Chap.10 Congruences, Powers, and Euler’s Formula

Theorem 10.1 (Euler’s Formula). If gcd(a, m) = 1, then a^phi(m) ≡ 1 (mod m).

欧拉定理！！费马小定理的推广，适用于任何模数。证明类似于费马小定理

Lemma 10.2. If gcd(a, m) = 1, then the numbers are the same as the numbers b1, b2, b3, ..., bphi(m) (mod m), although they may be in a different order.

类似于Lemma 9.2.

Chap.11 Euler’s Phi Function and the Chinese Remainder Theorem

如何计算phi(m)?

Theorem 11.1 (Phi Function Formulas). (a) If p is a prime and k >= 1, then phi(p^k) = p^k - p^(k-1). (b) If gcd(m, n) = 1, then phi(mn) = phi(m)phi(n).

一元数集Ring mn与二元点集Ring m, Ring n之间的对应关系。 –> 中国剩余定理

Theorem 11.2 (Chinese Remainder Theorem). Let m and n be integers satisfying gcd(m, n) = 1, and let b and c be any integers. Then the simultaneous congruences x ≡ b (mod m) and x ≡ c (mod n) have exactly one solution with 0 <= x < mn.

参考CTF中常见的RSA相关问题总结

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


# 适用于模数两两互质的情况，可以直接通过构造求解。
def CRT(ai, mi):
    # # make sure every two *m*s in *mi* are relatively prime
    # lcm = lambda x, y: x * y // gcd(x, y)
    # mul = lambda x, y: x * y
    # assert(reduce(mul, mi) == reduce(lcm, mi))
    assert(isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * egcd(M // m, m)[0]  for (m, a) in zip(mi, ai)]
    return reduce(lamdba x, y: x + y, ai_ti_Mi) % M

# 推广，不要求模数两两互质，总体思路是代入合并，再解线性同余方程。
def GCRT(ai, mi):
    assert(isinstance(mi, list) and isinstance(ai, list))
    a, m = ai[0], mi[0]
    for a1, m1 in zip(ai[1:], mi[1:]):
        # `x ≡ a (mod m)` ==> `x = a + k * m`
        # substitute in `x ≡ a1 (mod m1)` ==> `k * m ≡ a1 - a (mod m1)`
        k = linear_congruence_equation(m, a1 - a, m1) # solve k
        if not k:
            return None
        # The solution is x ≡ a + k * m (mod m * m1)
        a, m = a + k[0] * m, m * m1
    return a

Chap.12 Prime Numbers

Prime numbers are the building blocks of number theory.

质数是数论的根基。

Theorem 12.1 (Infinitely Many Primes Theorem). There are infinitely many prime numbers.

有无数个质数。

Theorem 12.2 (Primes 3 (Mod 4) Theorem). There are infinitely many primes that are congruent to 3 modulo 4.

可以用来构造一个质数生成器。

Theorem 12.3 (Dirichlet’s Theorem on Primes in Arithmetic Progressions). Let a and m be integers with gcd(a, m) = 1. Then there are infinitely many primes that are congruent to a modulo m. That is, there are infinitely many prime numbers p satisfying p ≡ a (mod m).

Theorem 12.2.是该定理的一个例子。该定理的证明颇为复杂，涉及到复分析。

Chap.13 Counting Primes

How many primes are there?

Let π(x) = #{primes p with p<=x}.

Theorem 13.1 (The Prime Number Theorem). When x is large, the number of primes less than x is approximately equal to x / ln(x). In other words, lim x->∞ π(x) = x / ln(x).

需要看下证明

There are many famous unsolved problems invovlling prime numbers.

Conjecture 13.2 (Goldbach’s Conjecture). Every even number n >= 4 is a sum of two primes.

In 1966, Chen Jing-run says that every(sufficiently large) even number is a sum of two numbers p + a, where p is a prime and a is either prime or a product of two primes.

哥德巴赫猜想！！！

Conjecture 13.3 (The Twin Primes Conjecture). There are infinitely many prime numbers p such that p + 2 is also prime.

孪生质数猜想。

Conjecture 13.4 (The N^2 + 1 Conjectur). There are infinitely many primes of the form N^2 + 1.

Chap.14 Mersenne Primes

Proposition 14.1. If a^n - 1 is prime for some numbers a >= 2 and n >= 2, then a must equal 2 and n must be a prime.

梅森质数。

Chap.15 Mersenne Primes and Perfect Numbers

A perfect number is a number that is equal to the sum of its proper divisors.

Theorem 15.1 (Eucild’s Perfect Number Formula). If 2^p - 1 is a prime number, then 2^(p-1) * (2^p - 1) is a perfect.

Sigma Function: σ(n) = sum of all divisors of n (including 1 and n).

Theorem 15.3 (Sigma Function Formulas). (a) If p is a prime and k >= 1, then σ(p^k) = 1 + p + p^2 + ... + p^k = (p^(k+1) - 1) / (p - 1). (b) If gcd(m, n) = 1, then σ(mn) = σ(m)σ(n).

类似于phi函数。

Theorem 15.4 (Euler’s Perfect Number Theorem). If n is an even perfect number, then n looks like n = 2^(p-1) * (2^p - 1), where 2^p - 1 is a Mersenne prime.

所有偶完全数的通式。现在还未找到任何奇完全数。

Chap.16 Powers Modulo m and Successive Squaring

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def FastExponentiation(x, y, n):
    '''
    Square-and-Mutiply for Modular Exponentiation.
    '''
    b = bin(y)[2:]
    res = x
    for i in b[1:]:
        res = res * res % n
        if int(i):
            res = res * x % n
    return res

快速幂算法，RSA的基础。(可以直接用python内置的pow()函数)

Chap.17 Computing kth Roots Modolu m

Algorithm 17.1 (How to Compute kth Roots Modulo m). Let b, k, and m be given integers that satisfy gcd(b, m) = 1 and gcd(k, phi(m)) = 1. The following steps give a solution to the congruence x^k ≡ b (mod m).

Compute phi(m).
Find positive integers d such that k * d ≡ 1 (mod phi(m)).
Then the solution is x ≡ b^d (mod m).

求k关于phi(m)的模逆元d，再幂运算。关键之处(也是最难的地方)是如何计算phi(m)。(RSA的解密算法)

Chap.18 Powers, Roots, and “Unbreakable” Codes

就是RSA。“Unbreakable"在于质因数分解一个大指数十分困难。

Chap.19 Primality Testing and Carmichael Numbers

How can we tell if a (large) number is prime?

既然RSA需要大质数，那么去哪里找这样的大质数呢？

思路1: 质数必定满足费马小定理(Theorem 9.1.)，如果不满足则必为合数。但是也有全都满足费马小定理的合数，即Carmichael number。 Theorem 19.1 (Korselt’s Criterion for Carmichael Numbers). Let n be a composite number. Then n is a Carmichael number if and only if it is odd and every prime p divding n satisfies the following two conditions: (1) p^2 does not divide n. (2) p - 1 divides n - 1.

思路2: Theorem 19.2 (A Property of Prime Numbers). Let p be an odd prime and write p - 1 = 2^k * q with q odd. Let a be any number not divisible by p. Then one of the following two conditions is true: (i) a^q is congruent 1 to modulo p. (ii) One of the numbers a^q, a^(2q), a^(4q), ..., a^(2^(k-1) * q) is congruent to -1 modulo p.

既然有a^(p-1) ≡ 1 (mod p)，那么对此开根之前的数必定已经≡ 1或者≡ -1。

Theorem 19.3 (Rabin-Miller Test for Composite Numbers). Let n be an odd interger and write n - 1 = 2^k * q with q odd. If both of the following conditions are true for some a not divisible by n, then n is a composite number. (a) a^q ≡/ 1 (mod n). (b) a^(2^i *q) ≡/ -1 (mod n) for all i = 0, 1, ..., k - 1.

If n is an odd composite number, then at least 75% of the numbers a between 1 and n - 1 act as Rabin-Miller witnesses for n.

可以用来判断一个大数是否为质数，但不能质因数分解这个大数。

Chap.20 Squares Modulo p

线性同余方程的解已经在 Theorem 8.1. 中给出了方法。但是非线性的同余方程呢？例如: $x^2 \equiv -1\ (mod\ p)$。

A nonzero number that is congruent to a square modulo p is called a quadratic residue modulo p (QR). A number that is not congruent to a square modulo p is called a (quadratic) nonresidue modulo p (NR). 平方剩余和平方非剩余的定义。

Theorem 20.1. Let p be an odd prime. Then there are exactly $\frac{p-1}{2}$ quadratic residues modulo p and exactly $\frac{p-1}{2}$ nonresidues modulo p. 平方剩余和平方非剩余的个数。

Theorem 20.2 (Quadratic Residue Multiplication Rule). (Version 1) Let $p$ be an odd prime. Then: (i) The product of two quadratic residues modulo $p$ is a quadratic residue. (ii) The product of a quadratic residue and a nonresidue is a nonresidue. (iii) The product of two nonresidues is a quadratic residue. $Q!R × Q!R = Q!R, Q!R × N!R = N!R, N!R × N!R = Q!R.$

Analogue to $1 ^ 1 = 0,\ 1 ^ 0 = 1,\ 0 ^ 0 = 0$, $+!1 × +!1 = +!1,\ +!1 × (-!1) = -!1,\ (-!1) × (-!1) = +!1$.异性相吸？

The Legendre symbol of a modulo p is:

$$(\frac{a}{p}) = \begin{cases} 1\quad if\ a\ is\ quadratic\ residue\ modulo\ p, \newline -1\quad if\ a\ is\ nonresidue\ modulo\ p. \end{cases}$$

勒让德符号。

Theorem 20.3 (Quadratic Residue Multiplication Rule). (Version 2) Let p be an odd prime. Then

$$(\frac{a}{p})(\frac{b}{p}) = (\frac{ab}{p}).$$

二次剩余乘法法则。

Chap.21 Is -1 a Square Modulo p? Is 2?

For which primes p is -1 a QR?

Theorem 21.1 (Euler’s Criterion). Let p be an odd prime. Then

$$a^{\frac{p-1}{2}} ≡ (\frac{a}{p})\ (mod\ p).$$

欧拉判别。由费马小定理有a^(p-1) ≡ 1 (mod p)，那么对左边开根，开根结果只有1 or -1，如果是1则说明a是QR，-1则为NR。

Theorem 21.2 (Quadratic Reciprocity). (Part I) Let p be an odd prime. Then -1 is a quadratic residue modulo $p$, if $p \equiv 1\ (mod\ 4)$, and -1 is a nonresidue modulo $p$, if $p \equiv 3\ (mod\ 4)$.

$$(\frac{-1}{p}) = \begin{cases} 1\quad if\ p \equiv 1 \ (mod\ 4), \newline -1\quad if\ p \equiv 3 \ (mod\ 4). \end{cases}$$

-1是QR还是NR？这个取决于质数p，若 $p \equiv 1\ (mod\ 4)$ 则为QR，$p \equiv 3\ (mod\ 4)$ 则为NR。

Theorem 21.3 (Primes 1 (Mod 4) Theorem). There are infinitely many primes that are congruent to 1 modulo 4.

有无数质数 $p \equiv 1\ (mod\ 4)$ 。与Theorem 12.2.相对应。

现在来考虑2在什么情况下是QR，什么情况下是NR。

Theorem 21.4 (Quadratic Reciprocity). (Part II) Let p be an odd prime. Then 2 is a quadratic residue modulo p if p is congruent to 1 or 7 modulo 8, and 2 is a nonresidue modulo p if p is congruent to 3 or 5 modulo 8. In terms of the Legendre symbol,

$$(\frac{2}{p}) = \begin{cases} 1\quad if\ p \equiv 1\ or\ 7 \ (mod\ 8), \newline -1\quad if\ p \equiv 3\ or\ 5 (mod\ 8). \end{cases}$$

2是QR还是NR？这个取决于质数p，若 $p \equiv \pm1\ (mod\ 8)$ 则为QR，$p \equiv \pm3\ (mod\ 8)$ 则为NR。

Chap.22 Quadratic Reciprocity

$(\frac{a}{p}) = (\frac{q_1}{p})(\frac{q_2}{p}) \ldots (\frac{q_r}{p})$ $\dashrightarrow$ If we know how to compute $(\frac{q}{p})$ for primes $q$, then we know how to compute $(\frac{a}{q})$ for every $a$.

Yet another instance of the principle that primes are the basic building blocks of number theory. 另外一个质数是数论基石的实例。

Theorem 22.1 (Law of Quadratic Reciprocity). Let p and q be distinct odd prims. $$(\frac{-1}{p}) = \begin{cases} 1\quad if\ p \equiv 1 \ (mod\ 4), \newline -1\quad if\ p \equiv 3 \ (mod\ 4). \end{cases}$$ $$(\frac{2}{p}) = \begin{cases} 1\quad if\ p \equiv 1 \ or\ 7\ (mod\ 8), \newline -1\quad if\ p \equiv 3\ or\ 5 \ (mod\ 8). \end{cases}$$ $$(\frac{q}{p}) = \begin{cases} (\frac{p}{q})\quad if\ p \equiv 1 \ (mod\ 4)\ or\ q \equiv 1\ (mod\ 4), \newline -(\frac{p}{q})\quad if\ p \equiv q \equiv 3 \ (mod\ 4). \end{cases}$$ 二次互反律，可以用来计算$(\frac{a}{p})$。不必质因数分解a。

Jacobi symbol: $(\frac{a}{b}) = (\frac{a}{p_1})(\frac{a}{p_2})…(\frac{a}{p_r})$. 雅可比符号

Theorem 22.2 (Generalized Law of Quadratic Reciprocity). Let a and b be odd positive integers. $$(\frac{-1}{b}) = \begin{cases} 1\quad if\ b \equiv 1 \ (mod\ 4), \newline -1\quad if\ b \equiv 3 \ (mod\ 4). \end{cases}$$ $$(\frac{2}{b}) = \begin{cases} 1\quad if\ b \equiv 1 \ or\ 7\ (mod\ 8), \newline -1\quad if\ b \equiv 3\ or\ 5 \ (mod\ 8). \end{cases}$$ $$(\frac{a}{b}) = \begin{cases} (\frac{b}{a})\quad if\ a \equiv 1 \ (mod\ 4)\ or\ b \equiv 1\ (mod\ 4), \newline -(\frac{b}{a})\quad if\ a \equiv b \equiv 3 \ (mod\ 4). \end{cases}$$

推广，不必要求是质数。

 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


# WRONG, DONT USE!
def qr(a, b):
    '''
    Return 1 if equation `x^2 ≡ a (mod b)` has solutions, -1 otherwise
    '''
    if a > b:
        a, b = b, a
    res = 1
    while a != b - 1 and a != 2 and a != 1 and a != 0:
        count = 0
        while a & 1 == 0:  # a is even
            a = a // 2
            count += 1
        if count & 1:  # count is odd
            if b % 8 == 3 or b % 8 == 5:
                res *= (-1)
        if a % 4 == 3 and b % 4 == 3:
            res *= (-1)
        a, b = b % a, a
    if a == b - 1:
        if b % 4 == 3:
            res *= (-1)
    if a == 2:
        if b % 8 == 3 or b % 8 == 5:
            res *= (-1)
    return res

同余方程 $x^2 + ax + b ≡ 0\ (mod\ p)$ 有解 $\iff$ $(\frac{\Delta\ =\ a^2 - 4b}{p}) = 1$。

Chap.23 Proof of Quadratic Reciprocity

二次互反律的第三个部分可以用下式来表示:

$$(\frac{q}{p})(\frac{p}{q}) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}$$

In this chapter we build upon the ideas used to prove the second part to give Eisenstein’s proof of the third part.

Let $\mu(a,p)$ = ( number of integers in the list $a, 2a, 3a, …,Pa$ that become negative when the intergers in the list are reduced modulo $p$ into the interval from $-P$ to $P$ ).

Theorem 23.1 (Gauss’s Criterion). Let $p$ be an odd prime, let $a$ be an interger that is not divisible by $p$. Then

$$(\frac{a}{p}) = (-1)^{\mu(a,p)}.$$

高斯判别。

Lemma 23.2. When the numbers $a, 2a, 3a, …, Pa$ are reduced modulo $p$ into the range from $-P$ to $P$, the reduced values are $\pm1$, …, $\pm$$P$ in some order, with each number appearing once with either a plus sign or a minus sign. 映射后（除去符号）没有重复。

Lemma 23.3. Let $p$ be an odd prime, let $P = \frac{p-1}{2}$, let $a$ be an odd integer that is not divisible by $p$, and let $\mu(a,p)$be the quantity defined above that appears in Gauss’s criterion. Then

$$\sum_{k=1}^{P} \left \lfloor \frac{ka}{p} \right \rfloor \equiv \mu(a,p) \ (mod\ 2).$$

piece of the proof of Quadratic Reciprocity:

$$\mu(q,p) + \mu(p,q) \equiv \frac{p-1}{2} \centerdot \frac{q-1}{2} \ (mod\ 2).$$

二次互反律的证明。

Chap.24 Which Primes Are Sums of Two Squares?

Which numbers can be written as sums of two squares?

Theorem 24.1 (Sum of Two Squares Theorem for Primes). Let $p$ be a prime. Then $p$ is a sum of two squares exactly when

$$p \equiv 1 \ (mod\ 4) \qquad \qquad (or\ p = 2).$$

从一边证到另一边很容易，从另一边证到这一边很困难。

Descent Procedure

Chap.25 Which Numbers Are Sums of Two Squares?

A product of sums of squares can be expressed by a sum of squares:

$$(u^2 + v^2)(A^2 + B^2) = (uA + vB)^2 + (uA - vB)^2.\qquad\qquad\qquad(*)$$

Divide and Conquer Divide: Factor $m$ into a product of primes $p_1p_2…p_r$. Conquer: Write each prime $p_i$ as a sum of two squares. Unify: Use the identity (*) repeatedly to write $m$ as a sum of two squares.

Theorem 25.1 (Sum of Two Squares Theorem). Let $m$ be a positive integer. (a) Factor $m$ as $m = p_1p_2…p_rM^2$ with distinct prime factors $p_1, p_2, …, p_r$. Then $m$ can be written as a sum of two squares exactly when every $p_i$ is either 2 or is congruent to 1 modulo 4. (b) The number $m$ can be written as a sum of two squares $m = a^2 + b^2$ with $gcd(a, b) = 1$ if and only if it satisfies one of the following two conditions: (i) $m$ is odd and every prime divisor of $m$ is congruent to 1 modulo 4. (ii) $m$ is even, $m/2$ is odd, and every prime divisor of $m/2$ is congruent to 1 modulo 4.

把m分解成不同的质数，且这些质数要是$4k+1$的形式。

Theorem 25.2 (Pythagorean Hypotenuse Proposition). A number $c$ appears as the hypotenuse of a primitive Pythagorean triple $(a, b, c)$ if and only if $c$ is a product of primes each of which is congruent to 1 modulo 4.

Chap.26 As Easy as One, Two, Three

Many number theoretic assertions have the form: Such and such a statement is true for every natural number $n$. For example:

$1^2 + 2^2 + … + n^2 = \frac{2n^3 + 3n^2 + n}{6}$ for every $n \in \mathbb{Z}$.
Every natural number $n$ is equal to a product of prime numbers.
Every natural number $n$ is equal to a sum of at most four squares.

Principle of Mathematical Induction

Step I (Initialization) Check the initial case $n = 1$.
Step II (Induction Step) Assume that we’ve already completed the proof for all values up to $n$, and using this assumption, which is called the induction hypothesis, prove the statement for $n + 1$. 数学归纳法

Complete induction or strong induction

Step I (Initialization) Check the initial case $n = 1$.
Step II (Induction Step) Assume that we’ve already completed the proof for all values of $n$ satisfying $1 \leqslant n \leqslant N$, and using this assumption, prove that the statement is true for $n = N + 1$. 强数学归纳法

Chap.27 Euler’s Phi Function and Sums of Divisors

Define a function $F(n) = \phi(d_1) + \phi(d_2) + … + \phi(d_r),\qquad\qquad where\ d_1, d_2, …, d_r\ are\ the\ divisors\ of\ n$.

Lemma 27.1. $I!f\ gcd(m, n) = 1,\ then\ F(mn) = F(m)F(n)$.

sum(phi(di) where di | n) = n

后面的一些内容有点深奥，不再一个一个地把定理写下来了，就写点概括和理解。

Chap.28 Powers Modolu p and Primitive

Primitive Roots (原根): a^x 能生成所有在{1, 2, …, p-1}内的数，质数p一共有phi(p-1)个原根

Chap.29 Primitive Roots and Indices

{g^1, g^2, g^3, …, g^(p-1)}与{1, 2, 3, …, p-1}一一对应。但是对应关系没有规律，也就是discrete，DLP正基于这一点。

Chap.30 The Equation X^4 + Y^4 = Z^4

方程$x^4 + y^4 = z^2$没有正整数解。

Chap.31 Square-Triangular Numbers Revisited

既是平方数又是三角数的数叫做square-triangular number，有无数个这样的数。求平方数可以归于求方程$x^2 - 2y^2 = 1$的正整数解。方程的解可以由$x_k + y_{k}\sqrt2 = (3 + 2\sqrt2)^k$生成。

Chap.32 Pell’s Equation

形如$x^2 - Dy^2 = 1$（其中D是一个非完全平方数的正整数）的方程叫做佩尔方程(Pell equation)。该方程被Brahmagupta, Bhaskaracharya和Brouncker研究过，更应被称为$B^3$ equation。方程总有正整数解，如果$(x_1, y_1)$是最小解，那么所有解可以由$x_k + y_{k}\sqrt{D} = (x_1 + y_{1}\sqrt{D})^k\qquad for\ k = 1,2,3,…$生成。

Chap.33 Diophantine Approximation

丢番图逼近，丢番图分析？？ Dirichlet’s approximation theorem 有无数对正整数满足$|x - y\alpha| < \frac{1}{y}$，其中$\alpha > 0$是无理数。

Chap.34 Diophantine Approximation and Pell’s Equation

用Diophantine Approximation证了一下佩尔方程有无数解和解的形式。（很难看懂）

Chap.35 Number Theory and Imaginary Numbers

虚数$i = \sqrt{-1}$

Theorem 35.1 (The Fundamental Theorem of Algebra). If $a_0, a_1, a_2, …, a_d$ are complex numbers with $a_0 \ne 0$ and $d \ge 1$, then the equation

$$a_0x^d + a_1x^{d-1} + a_2x^{d-2} + … + a_{d-1}x + a_d = 0$$

has a solution in complex numbers.

We do number theory with a certain subset of the complex numbers called the Gaussian integers. These are the complex numbers that look like $a + bi$ with $a$ and $b$ both integers.

Gaussian primes

为什么要扯上虚数？ for $(a + bi)(a - bi) = a^2 + b^2$

Theorem 36.1 (Unique Factorization of Gaussian Integers). Every Gaussian integer $\alpha \ne 0$ can be factored into a unit $u$ multiplied by a product of normalized Gaussian primes $\alpha = u\pi_1\pi_2…\pi_r$ in exactly one way.

引入虚数以及虚数的因数分解，有什么用呢？

We use the Gaussian Integer Unique Factorization Theorem to count how many different ways a number can be written as a sum of two squares.

Theorem 36.5 (Sum of Two Squares Theorem(Legendre)). For a given positive integer N, let $D_1$ = (the number of positive integers d dividing N that satisfy $d \equiv 1\ (mod\ 4)$), $D_3$ = (the number of positive integers d dividing N that satisfy $d \equiv 3\ (mod\ 4)$). Then N can be written as a sum of two squares in exactly $R(N) = 4(D_1 - D_3)$ ways.

Chap.37 Irrational Numbers and Transcendental Numbers

整数 -> 有理数 -> 无理数

algebraic number(代数数): 能成为整系数多项式的根。 transcendental number(超越数): 非代数数。

One of the most beautiful theorems in transcendence theory was proved independently by A.O Gelfond and T.Schneider in 1934. They showed that if $a$ is any algebraic number other than 0 or 1 and if $b$ is any irrational algebraic number, then the number $a^b$ is transcendental.

很难证明一个数是个超越数。

Chap.38 Binomial Coefficients and Pascal’s Triangle

二项式系数在模质数p上有一些性质。

$(A + B)^p \equiv A^p + B^p\ (mod\ p)$，利用该定理，可以用（强）数学归纳法来证明费马小定理。

Chap.39 Fibonacci’s Rabbits and Linear Recurrence Sequences

$$F_n = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^2 - (\frac{1-\sqrt{5}}{2})^n]$$

斐波那契数列在模质数p下也有一些性质。

Chap.40 Oh, What a Beautiful Function

介绍了$O(f(n))$，也就是*‘big-Oh’ notation*。

$O(\log{n})$ is said to take linear time.

最后几章是椭圆曲线。

Chap.41 Cubic Curves and Elliptic Curves

$E: y^2 = x^3 + ax^2 + bx + c$，其中$a, b, c$均为整数。

If $\vartriangle!(E) = -4a^3c + a^2b^2 - 4b^3 - 27c^2 + 18abc \ne 0$, there are only finetely many solutions in integers x and y。

Chap.42 Elliptic Curves with Few Rational Porints

有些E仅有很少（1个或者几个）有理数解。

Chap.43 Points on Elliptic Curves Modulo p

可以对E模质数p。

$N_p$

p-defect: $a_p = p - N_p$

Chap.44 Torsion Collections Modulo p and Bad Primes

In general, we say that $p$ is a bad prime for an elliptic curve $E: y^2 = x^3 + ax^2 + bx + c$ if the polynomial $x^3 + ax^2 + bx + c$ has a double or triple root modulo $p$.

Chap.45 Defect Bounds and Modularity Patterns

Hasse’s Theorem: $$|a_p| < 2\sqrt{p}$$

Modularity Patterns

Chap.46 Elliptic Curves and Fermat’s Last Theorem

let $p \ge 3$ be a prime, and suppose that there is a solution (A, B, C) to $A^p + B^p = C^p$ with A, B, C nonzero integers and $gcd(A,B,C) = 1$.
Let $E_{A,B}$ be the Frey Curve $y^2 = x(x + A^p)(x - B^p)$.
Wiles’s Theorem tells us that $E_{A,B}$ is modular; that is, its $p$-defect $a_p$ follow a modularity pattern.
Ribet’s Theorem tells us that $E_{A,B}$ is so strange that it cannot possibly be modular.
The only way out of this seeming contradiction is the conclusion that the equation $A^p + B^p = C^p$ has no solutions in nonzero integers.

It is here, at the successful resolution of this most famous problem in mathematics, that we end our voyage through the Seven Seas of Number Theory. I hope you have enjoyed the tour as much as I have enjoyed being your guide and that you have found much to admire and much to ponder in this most beautiful of subjects. Above all, I hope that you have gained a sense of mathematics as a living, growing enterprise, with many wonderful treasures already discoveredm, but with many others, even more wonderful, waiting just over the horizion for the person having the insight, the daring, and the perseverance to sail into the unknown.

这个作者的文笔真的很不错。

Summary

毕竟起初打CTF我就对密码学情有独钟，但是一开始又懒于钻入学习，直到后来校队选拔的时候才发觉自己还是tcl。校队选拔后，我立下决心要正式地学习一下密码学。

自今年5月开始看youtube上一个关于密码学的lecture 以来，我发现的确学到了许多东西。lectures只看了一半，后来觉得lectures上面虽然教授讲得很棒，但还是有一些额外的东西没有涉及到，所以就直接找到了教授Paar写的书，也就是看的第一本密码学书籍Understanding Cryptography。书里讲得更棒了，有多棒呢？棒到如果有人想入门密码学，我会第一个推荐这本书。书里不光讲了各种加密算法的具体实现，还附带一些常见的攻击方式以及拓展知识，看完这本书，基本上就能对密码学有一个比较大概的理解。CTF题做起来也变得很顺滑了，基本上能应付得了超过一半的密码题。在看lectures和书的同时，我也按照书（lectures）上的叙述，用Python实现了一遍大部分加密算法，可以在我的github 上找到（还有后面一部分没完成）。看完书后，感觉意犹未尽，感觉密码学的学习不应该蜻蜓点水、就此而止，于是就在知乎上找到了一篇求大触们推荐一些比较系统的关于密码加密解密的书籍？。想跟着里面的书单学一下，所以就直接上手了这本A Friendly Introduction to Number Theory。

看之前去翻了下豆瓣上的书评，看到有说中文翻译不太行，就直接怼上了英文版。

第一天看，就直接连看了好几章，果然很friendly，看了还想看。按照这个速度，原本打算10天看完的，不过中间也有几件小插曲，总共花了15天才看完。

书里有一个很吸引我的地方，就是关于是否有无数个平方三角数。我上高三的时候，快到高考了，很无聊，就各种没事找事，手算2的100次方、手算3的100次方，后来找上了这个n(n+1)/2是平方数的问题。那个时候还尝试过用高一学过的一点Visual Basic写了个代码，跑了下，发现是有挺多个的，到后面都很大，不过并不会用严格的数学语言来证明，那个时候好像也推到了$x - 2y^2 = 1$这一步。所以在书的一开头我就又看到这个问题，自然十分欣喜，所有就有一种想继续看下去，在书的后面去找答案的冲动，所幸找到了答案，也学习了很多别的东西。

先吹一波这个作者的文笔，是真的挺好的。就单凭第二章数论之美以及最后一章继续远行，我就被折服了，或许这就是看英文原版书籍的好处吧。作者不光文笔好，写的东西也很能引人入胜，很多定理都是先由一些对数字的观察，发现patterns后，再去给出证明的，而且在给出一长串证明的时候，能够将大证明拆成小证明，再结合许多个小证明来完成大证明。这就相对于那些直接给定理和证明的就有意思多了，这种方式更能启发读者自己的思考，能有自己的发现过程。或许这就是作者想要传授给我们的sence of mathematics吧。

书中有课后习题，这里比较惭愧，基本上都没有去做，有些只是稍微扫扫、略作思考、一带而过。可能是后面不想再深入学习数论吧，毕竟我是个搞计算机的，而且数论的精妙、美丽之处我也大致有所领悟。再深入下去的话，就真的不如去学数学吧。。

大致说下书里面的内容吧。毕达哥拉斯定理，整除，最大公因数，扩展欧几里得定理，线性方程的解，因数分解，同余，线性同余方程的解，费马小定理，欧拉定理，欧拉函数，质数，梅森质数，完全数，快速幂，模逆，RSA，素性测试，平方剩余，二次互反律，原根，4次方程X^4+Y^4=Z^4，丢番图逼近，虚数，超越数，斐波那契数列，数学归纳法，椭圆曲线。稍微看了下大二上要学的一本《信安数基》，里面只讲到原根那边，30章后面的内容基本没有涉及。大致说下我的阅读体验，基本上二次互反律之前的内容，看起来都还能接受，二次互反律的证明就已经开始有点吃不消了，后面的十几章很多证明都是很快掠过。

数论稍微了解了下，接下来的打算就是An Introduction to Mathematical Cryptography了，毕竟我感觉密码学里面最美妙的莫过于公钥密码了。