数论算法概要

内容包括整数的整除、数论函数、同余及其运算、同余方程、素性测试与整数分解等。同时,注重数论有关的算法,以及数论的应用。

数论

    数论是研究正整数集合及其性质的数学分支。
    数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论,其研究方法本质上说,就是利用整数环的整除性质,主要包括整除理论、同余理论、连分数理论。
    数论是最为古老的纯数学的分支,被称为数学的皇后("The Queen of Mathematics"),揭示了数学的基础。
    数论研究素数,整数对象的属性以及整数的通则规律。
    数论应用广泛,例如计算方法、代数编码、组合论等方面都广泛使用了初等数论范畴的许多研究成果;
    数论是密码学的数学基础。密码系统与密码分析都需要用到数论,关乎网络信息安全,数论及其算法受到广泛重视。

自然数类型

数论四大定理

典型数论问题

1 整数可除性

1.1 整除概念

    【定义1.1.1】设a, b∈Z(整数集合),b≠0,如果存在q∈Z,使得a=bq,则称b整除a或a可被b整除,记作b|a,且称a是b的倍数,b是a的因数(也可称为除数、约数、因子)。否则,称b不能整除a或a不能被b整除,记作b\|a。

整除性质

    【性质1.1.1】设a, b∈Z,则b|a<=>b|-a<=>-b|-a<=>|a|||b|。

    【性质1.1.2】传递性。设a, b,c∈Z,若c|b且b|a,则c|a。

    【性质1.1.3】设a, b,c∈Z,若c|b且c|a,则c|a±b。

    【性质1.1.4】设a, b,c∈Z,若c|b且c|a,则对于任意整数s、t,有c|sa+tb。

    【性质1.1.5】设a, b∈Z,若b|a且a|b,则a=±b。

    【性质1.1.6】b|a<=>cb|ca(c≠0)。

    【性质1.1.7】若b|a且a≠0,则|b|≤|a|。

素数

    【定义1.1.2】设整数p≠0, ±1。如果它除了显然约数±1, ±p外没有其它的约数,那么,就称p为素数(或质数、不可约数)。若a≠0, ±1,且a不是素数,则称a为合数。

    【定理1.1.1】
        (i) 大于1的最小正因数必是素数。
        (ii)n是正整数,若对所有满足2≤p≤√ n的而言,有p\|n,则n是素数。

    【定理1.1.2】素数有无穷多。

带余除法

    【定理1.1.3】设a, b是两个给定的整数,b≠0。那么,一定存在唯一的一对整数q与r,满足
        a=qb+r, 0≤r<|b|
一般情况下,约定b>0,则上式可表示为
        a=qb+r, 0≤r<b

    【定理1.1.4】设a, b是两个给定的整数,b≠0,则对任意的整数c,一定存在唯一的一对整数q与r,满足
        a=qb+r, 0≤r<|b|+c

1.2 整数表示

    【定理1.2.1】设p是大于1的正整数,则每个正整数n可以唯一地表示成
        n=akp^k+ak-1p^k-1+...+a1p+a0
其中ai为整数,0≤ai≤p(i=0,1,...,k)且首项系数ak≠0(即p^k≤n<p^k+1)。

    【定义1.2.1】用n=(akak-1...a1a0)p表示展开式
        n=akp^k+ak-1p^k-1+...+a1p+a0
其中ai为整数,0≤ai≤p-1(i=0,1,...,k),ak≠0,并称其为整数n的p进制表示

1.3 最大公约数

    【定义1.3.1】设a1,a2,...,an是n个整数(n≥2),若整数d是它们中每一个数的因数,那么d就称做a1,a2,...,an的公约数;若a1,a2,...,an不全为0,那么a1,a2,...,an的公约数中最大的一个叫做最大公约数,记作(a1,a2,...,an)。当(a1,a2,...,an)=1时,称a1,a2,...,an互素。

相关链接:最大公约数GCD的三种算法程序

最大公约数性质

    【性质1.3.1】(a)=|a|。

    【性质1.3.2】(a,b)=(b,a)。

    【性质1.3.3】设a、b为正整数,若b|a,则(a,b)=b。

    【性质1.3.4】设p为素数,a为整数,若p\|a,则(p,a)=1。

    【性质1.3.5】设a1,a2,...,an是n个不完全为零的整数,则
        (i)a1,a2,...,an与|a1|,|a2|,...,|an|的公约数相同;
        (ii)(a1,a2,...,an)=(|a1|,|a2|,...,|an|)。

    【性质1.3.6】设a,b,c是三个不完全为零的整数,a=bq+c,其中q是整数,则        (a,b)=(b,c)

    【性质1.3.7】对于任意整数x,y,有
        (a,b)=(a,b,ax)=(a,b,by)

    【性质1.3.8】对于任意整数x,有
        (a,b)=(a,b+ax)=(a+bx,b)

    【性质1.3.9】
        (i)设a,b均为偶数,则(a,b)=2(a/2,b/2);
        (ii)设a为偶数,b为奇数,则(a,b)=(a/2,b);
        (iii)设a,b均为奇数,则(a,b)=(a,(a-b)/2)=((a-b)/2,b)。

计算(a, b)算法

    即求最大公约数算法,目的是实现计算函数GCD(a, b)

1.4 最小公倍数

    【定义1.4.1】设a1,a2,...,an为整数,若m是这些数的倍数,则称m为这n个数的一个公倍数,所有公倍数中最小的正整数叫做最小公倍数,记作[a1,a2,...,an]。

相关链接:计算最小公倍数LCM

1.5 算术基本定理

    【定理1.5.1】任一整数n>1都可以表示成素数的乘积。且在不考虑乘积顺序的情况下,该表达式是唯一的。即n=p1p2...pk,p1≤p2≤...≤pk

2. 数论函数

2.1 数论函数

2.3 函数potpn

    【定义2.3.1】。

2.4 欧拉函数φ(n)

    【定义2.4.1】设n为正整数,则1,2,...,n中与n互素的整数的个数记做,叫做Euler(欧拉)函数

    【性质2.4.1】设p为素数,则φ(p)=p-1。

相关链接:欧拉函数(计算程序)

2.6 素数个数函数π(n)

    【定义2.6.1】记1~n的所有素数的个数为π(n),称为素数个数函数。

    【定理2.6.1】(素数定理)当n很大时,小于n的素数个数近似等于n/ln(n)。

3. 同余及其运算

3.4 欧拉定理和费尔马小定理

    【定理3.4.1】(欧拉定理)设m是大于1的整数,若整数a满足(a,m)=1,则有aφ(m)≡1(mod m)。

    【定理3.4.2】(费尔马小定理)设p为素数,a为任意正整数,则
        ap≡a(mod p)。

3.5 模幂计算

    模幂计算也称为乘方取模运算,有采用二分法的快速计算法,其计算复杂度为log(n)。

相关链接:乘方取模计算(模幂计算)(计算程序)

3.6 一次不定方程

二元一次不定方程

二元一次不定方程可以使用扩展欧几里德算法来求解。

相关链接: 扩展欧几里得算法(计算程序)

4. 同余方程

5. 二次同余方程与平方剩余

6. 原根与离散对数

7. 连分数

8. 素性测试与整数分解

素性测试方法

整数分解方法

9. 有限域