地板和天花板函数
定义1
地板函数⌊x⌋：最大整数≤x。
示例2
⌊3.99⌋= 3，⌊5/2⌋= 2，⌊3⌋= 3
定义3
天花板函数⌈x⌉：最小整数≥x。
示例4
⌈3.99⌉= 4。⌈5/2⌉= 3。⌈3⌉= 3。
商与余
定理5（分算法）
令b为不等于 0的整数，令a为任意整数。 那么有两个唯一的整数q和r (0≤ r<|b|)，使得a = qb + r。
q和r是当a除以b时的商和余数， r = a mod b。
如果a mod b = 0，则称b为除数或因子a。 在这种情况下，我们说a可以被b整除或b整除a。
GCD
定义8
素数n是正整数且，只有两个正因数1和n。
定义9
公约数是a和b两个整数共同的因数。
由gcd（a，b）表示的两个整数a和b的最大公约数。
命题13
如果a>0,b>0
gcd（b，a）= gcd（-b，a）= gcd（b，-a）= gcd（-b，-a）= gcd（a，b）。
欧氏算法递归计算gcd（a，b）
示例：查找gcd（66,35）。
算法：
根据gcd（a，b）= gcd（b，a mod b）
它的工作原理如下，当余数变为0时停止：
66 = 1×35 + 31
35 = 1×31 + 4
31 = 7×4 + 3
4 = 1×3 + 1
3 = 3×1 + 0
gcd（35,31）gcd（31,4）gcd（4,3）gcd（3,1）gcd（1,0）
因此，在前一页的引理
gcd（66,35）= gcd（35,31）= gcd（31,4）= gcd（4,3）= gcd（3,1）= gcd（1,0）= 1。
时间复杂度为 O(log|b|×[log|b|+log|a|]2)
LCM
定义16
lcm（a，b）表示的两个整数a和b的最小公倍数，即能被a和b可以同时整除的最小正整数。
令a和b为整数。 则
lcm（a，b）= |a*b|／gcd（a，b）
模数n算术
定义19
令n> 1为整数。 我们定义
x⊕n y=（x + y）mod n，[12⊕5 7=（12 + 7）mod 5 = 4]
x⊖n y=（x-y）mod n，[12⊖5 7=（12-7）mod 5 = 0]
x⊗n y=（x×y）mod n，[12⊗5 7=（12×7）mod 5 = 4]
其中+， - 和×是整数运算。 操作⊕n，⊖n和⊗n称为模n加法，模n减法和模n乘法。 整数n称为模数。
*满足交换律、结合律、分配律
定义21
令x∈Zn = {0,1，...，n - 1}。 如果存在整数y∈Zn，使得x⊗n y =：（x×y）mod n = 1。
整数y称为x的乘法逆(multiplicative inverse)，通常表示为x-1（如果存在则为唯一）。
引理24
存在两个整数u和v，使得gcd（a，b）= ua + vb。
示例25
找到u和v的整数，使得gcd（66,35）= u66 + v35。
扩展欧几里德算法，原理如下：
66 = 1×35 + 31 => 1 = −9×66+17×35 （得到系数-9和17）
35 = 1×31 + 4 => 1=8×35−9×31（方法同下）
31 = 7×4 + 3 => 1= -1 × 31 + 8×4（将4=35-31 × 1代入得上一行）
4 = 1×3 + 1 => 1= 4 - 1×3 (将 3=31-7 ×4 代入得上一行)
3 = 3×1 + 0
因此u = -9和v = 17。
定理28
令n> 1为整数， 那么当且仅当gcd（a，n）= 1时，任何a∈Zn具有关于n的乘法逆元。
示例：求 35关于66的模乘法逆元（即求x使得 35×X mod 66 = 1）
因为存在逆元，则gcd(65,35)=1，即u65+v35=1
根据欧几里得扩展： 1=-966+1735
得17即为35关于66的模乘法逆元
定理31
若p为素数，那么Zp中的每个非零元素都具有关于p的模乘法逆元。
定义32
若p为素数， 然后将三元组（Zp，⊕p，⊗p）称为具有p个元素的有限域。
屏幕快照 2017-09-14 下午5.17.52.png
+代表⊕3，×代表⊗3。
网友评论