密码学-2-数学引论

数论基础知识

数论基础 - OI Wiki (oi-wiki.org)

定义5-1 (整除)：设\(a,b\)是整数，\(a\neq b\)，如果有一个整数\(x\)，使得\(b=ax\)，则\(b\)叫做\(a\)的倍数，\(a\)叫做\(b\)的因数，或者说\(a\)能整除\(b\)， 或\(b\)能被\(a\)整除。\(a\)能整除\(b\),记为\(a|b\)

整除的性质：

• 若\(a|b\)，那么对任何整数\(c\)，都有\(a|bc\)
• 若\(a|b，b|c\)，那么有\(a|c\)
• 若\(a|b，a|c\)，那么对任何整数 x 和 y，都有\(a|(bx+cy);\)
• 若\(a|b，b|a\)，那么\(a=\pm b\)
• 若\(a|b,a>0,b>0\)，那么\(a\leq b.\)

群的相关概念

群的概念

对乘法，单位元是1，但是不是所有的整数都有逆元（或者说除了1和-1都没有=

逆元：对任意a，存在b，使得a * b=b * a=e，这里的b是逆元，e是单位元

群的阶：\(ord(G)=群中元素的个数\)

群元素的阶：\(ord(g)\)

• 群元素g做群的操作 i 次
• 最小的正整数 i 满足，\(g^i=1\)（单位元）

\(g^{ord(G)} = 1(单位元)\)，证明如下：

\[ \begin{align} ∵ord(g) \ &|\ ord(G)\\ g^{ord(g)} &= 1\\ ∴ord(G) &= k*ord(g)\\ ∴g^{ord(G)} &= 1 \end{align} \]

对$Z_n* $ ，{ a|gcd(a,N)=1 } *mod N，元素的个数为欧拉函数：φ(N)

当N为素数，{0,1,2,,,,,p-1} *mod p

例如p等于7时，$Z_n* \(为\){1,2,3,4,5,6}$，单位元：1

元素1-6的阶为：1，3，6，6（×）3（√），6，2

元素1的阶：\(1*1=1\)，再mod 7 = 1，所以元素1的阶为1

元素2的阶：\(2 * 2 * 2 = 8\)，再mod 7 =1，所以元素2的阶为3，写作：\(ord（2）=3\)

元素3的阶：\(3 * 3 * 3 * 3 * 3 * 3 = 729\)，再mod 7 = 1，所以元素3的阶为6

元素4的阶：\(4 * 4 * 4=64\)，再mod 7 = 1，所以元素4的阶为3

……

逆元（1-6的）：1，4，5，2，3，6

1的逆元：1 * 1 = 1，再mod 7 = 1，所以元素1的逆元为1

2的逆元：2 * 4 = 8，再mod 7 = 1，所以元素2的逆元为4

3的逆元：3 * 5 = 15，再mod 7 = 1，所以元素3的逆元为5

4的逆元：4 * 2 = 8，再mod 7 = 1，所以元素4的逆元为2

……

😴

对{0，1，2，3，，，，N-1} +mod N

是一个群

封闭性，结合律都满足

单位元：0

逆元：3的逆元N-3 （Zn）