密碼學(xué)：數(shù)論基礎(chǔ)

發(fā)布時(shí)間：2025-10-07 | 來(lái)源：互聯(lián)網(wǎng)轉(zhuǎn)載和整理

如果我們用代替，稱為此過(guò)程稱為模約化，而代表了除以的余數(shù)

對(duì)于如果整除，則稱“同余于?！?，記做

我們定義算術(shù)模為：表示具有兩個(gè)運(yùn)算符（加法）和（乘法）的***。中的加法和乘法與實(shí)數(shù)加法和乘法完全一樣，只是結(jié)果要進(jìn)行模約化。

講“群”，先講講“代數(shù)結(jié)構(gòu)”。代數(shù)結(jié)構(gòu)是指具有?個(gè)及以上運(yùn)算的?空***。

群是非空***和基于定義的二元操作符組成的，滿足如下4種性質(zhì)的對(duì)，表示為。因此群也是一種代數(shù)結(jié)構(gòu)。

有兩類特殊的群：阿貝爾群和循環(huán)群，下文介紹。

有限群的階定義為，表示為。

對(duì)群中的元素，即，的階定義為滿足如下式的最小的正整數(shù)。其中為的單位元

對(duì)于群如果操作符還滿足交換律，對(duì)，有，則稱為阿?爾群，?稱為交換群。

對(duì)于群如果是有限***，則稱是有限群。

對(duì)于有限阿貝爾群，如果存在一個(gè)元素的階數(shù)等于，則稱該群為循環(huán)群，元素稱為該群的生成元（Generator），通常記作。循環(huán)群中的所有元素都可以由生成元通過(guò)冪次運(yùn)算得到，且生成元和群的階一定是互質(zhì)的。

循環(huán)群都是阿?爾群，但不是所有的阿?爾群都是循環(huán)群。

假設(shè)是一個(gè)有限群。如果也是一個(gè)有限群，且，則稱是的一個(gè)子群。

顯然為使為有限群，并非任意的就可以的，從中選取元素時(shí)需重點(diǎn)考慮令滿足封閉性：。

設(shè)是的子群那么定義右陪集（rightcoset）為:。同理,定義左陪集（leftcoset）為：。

對(duì)于整數(shù)表示小于且與互質(zhì)的所有正整數(shù)的數(shù)量。被稱為歐拉函數(shù)。

如果是的子群，則整除

一個(gè)從到的同構(gòu)是一個(gè)雙射（bijection）滿足，。

如果是從到的同構(gòu)，那么和的階相同，并且

一個(gè)從到的同態(tài)是一個(gè)映射（mapping）滿足，。

一個(gè)從到的同態(tài)是同構(gòu)當(dāng)且僅當(dāng)是雙射的時(shí)候。

用于計(jì)算兩個(gè)正整數(shù)（例如a和b）的最大公約數(shù)。

給定兩個(gè)不完全為0的整數(shù)，，必存在整數(shù)，使得，是，的最?公約數(shù)。

給定兩個(gè)不全為0整數(shù)a和b，擴(kuò)展歐幾里得算法計(jì)算整數(shù)使得，本文略。

假設(shè)和是群則其直積所得的群定義為,其中：對(duì)于任意的，滿足。

環(huán)是非空***和基于定義的兩個(gè)?元操作符組成的，滿足如下性質(zhì)三元組，記作。

注意環(huán)中的乘法不要求可交換、有單位元或逆元，可理解為只支持加減乘運(yùn)算。

如果環(huán)中是有限***，則稱為有限環(huán)。

如果環(huán)中的乘法滿足交換律，則稱為交換環(huán)。

計(jì)算兩個(gè)多項(xiàng)式,的最大公約數(shù)

假設(shè)和是環(huán)。則其直積所得的環(huán)定義為,其中：對(duì)于任意的，滿足，且

一個(gè)從到的同構(gòu)是一個(gè)雙射（bijection）滿足，，且。

求解同時(shí)滿足多個(gè)子同余式的的同余式。本文略去。

對(duì)于有理數(shù)域，整數(shù)環(huán)就是它的?個(gè)?環(huán)。對(duì)于整數(shù)環(huán)所有偶數(shù)依然在加法、乘法下構(gòu)成?個(gè)環(huán)（因?yàn)槿魏蝺蓚€(gè)偶數(shù)通過(guò)加、減、乘得到的還是偶數(shù)，對(duì)于加、減、乘是封閉的，所以依然是?個(gè)環(huán)），偶數(shù)環(huán)是整數(shù)環(huán)的?個(gè)?環(huán)。對(duì)于階實(shí)數(shù)矩陣環(huán)，其所有的?對(duì)?線上的值全為0的階矩陣在矩陣加法、矩陣乘法上也構(gòu)成了原矩陣環(huán)的?個(gè)?環(huán)，對(duì)于、兩個(gè)矩陣，如果?對(duì)?線上為0，那么?論加法、減法還是乘法，得到的結(jié)果?對(duì)?線上都為0。

對(duì)于交換環(huán)如果的每個(gè)理想都是主理想，那么稱是主環(huán)。

一個(gè)主環(huán)的例子是：

一個(gè)帶單位元的交換環(huán)，如果使得每個(gè)非零元素都具有乘法逆元，即是阿貝爾群，則稱其為域，記作。

域是同時(shí)滿?加法和乘法的結(jié)合律，交換律，分配律，單位元以及逆元五個(gè)性質(zhì)的三元組，能同時(shí)支持加減乘除（除0以外）。

上式意思是域中的所有?零元素的***是關(guān)于乘法的阿?爾群。

舉例而言，，是域，是環(huán)。

根據(jù)定理當(dāng)且僅當(dāng)時(shí)階為的有限域才存在，其中為素?cái)?shù)，且。稱為的特征

類似子群子環(huán)。