文章目錄

• 代數數論基本知識
• • 同余定理
  • 費馬小定理
  • 算數基本定理
  • 歐拉函數
  • 二項式定理
  • 歐拉定理

代數數論基本知識

同余定理

定理內容：給定一個模正整數m，如果兩個整數a和b滿足（a-b）能夠被m整除，即（a-b）/m得到一個整數，那么就稱整數a與b對模m同余，記作$a\equiv b(modm)$
例：
（1）a=5，b=2，m=3，（a-b）/m為整數1，那么a對m取余和b對m取余都一樣為2。稱5與2對3同余。
（2）a=97，b=37，m=20，（a-b）/m為整數3，那么a對m取余和b對m取余都一樣為17。稱97與37對20同余。

費馬小定理

定理內容：如果p是一個質數，而整數a不是p的倍數，則有$a^{p?1}\equiv 1(modp)$ 。(這里的 ≡ 指的是恒等于，$a^{p?1}\equiv 1(modp)$ 是指a的p-1次冪取模與1取模恒等)
例：
（1）取p=3，a=4，則$a^{p?1}=4^{3?1}=16$，16對3取余為1。
（2）取p=7，a=10，則$a^{p?1}=10^{7?1}=1000000$，1000000對7取余為1。

算數基本定理

定理內容：任何大于1的自然數N，都可以唯一分解成有限個素數乘積，記為
$$N=p_1^{a_1}{p}_2^{a_2}???p_k^{a_k}=\prod _{i=1}^k{p}_i^{a_i}$$
其中$p_i$為素數，$a_i$為正整數。
例：
（1）N=35，則N=57。
（2）N=14535，則N=33517*19。

歐拉函數

定理內容：給定一個整數n，計算不大于n且與n互素的正整數，這些正整數集合記為$Z_n^{?}$，即
$$Z_n^{?}=\{z|z\in Z,0\le z<n,gcd(z,n)=1\}$$
這些正整數的個數記為$?(n)=|Z_n^{?}|$.
其中gcd(z,n)表示z和n的最大公約數。
例：
（1）$n=12，Z_n^{?}=\{1,5,7,11\}$，$?(n)=4$
（2）$n=20，Z_n^{?}=\{1,3,7,9,11,13,17,19\}$，$?(n)=8$

二項式定理

定理內容：描述二項式冪的代數展開式根據這個定理，可以將任意的x+y的非負次冪展開為以下形式：
$$(x+y{)}^n={(}_0^n)x^n{y}^0+{(}_1^n)x^{n?1}{y}^1+?????+{(}_{n?1}^n)x^1{y}^{n?1}+{(}_n^n)x^0{y}^n=\sum _{k=0}^n{(}_k^n)x^{n?k}{y}^k$$
例：$(x+y{)}^4=x^4+4x^{3}y+6x^2{y}^2+4xy3+y^4$

歐拉定理

定理內容：若n,a為正整數,且n,a互素，則以下關系成立：
$$a^{?(n)}\equiv 1(modn)$$
例：
（1）$n=20,a=3,則?(n)=8,a^{?(n)}=3^8=6561=1(modn)$
（2）$n=12,a=5,則?(n)=4,a^{?(n)}=5^4=625=1(modn)$

總結

以上是生活随笔為你收集整理的密码学-代数数论基本知识的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。