可逆元是怎么計(jì)算的 1）應(yīng)該是求逆元.具體怎么回事，我是怎么也看不懂

求模逆元的幾種算法，離散數(shù)學(xué)中，怎么求幺元，逆元，如圖所提？1）應(yīng)該是求逆元.具體怎么回事，我是怎么也看不懂？逆元通俗理解，舉生活例子，在有限域中怎么求一個(gè)多項(xiàng)式的逆元？Z5中所有可逆元的逆元。

本文導(dǎo)航

• 求模逆元的幾種算法
• 離散數(shù)學(xué)中，怎么求幺元，逆元，如圖所提
• 1）應(yīng)該是求逆元.具體怎么回事，我是怎么也看不懂
• 逆元通俗理解，舉生活例子
• 在有限域中怎么求一個(gè)多項(xiàng)式的逆元
• Z5中所有可逆元的逆元

求模逆元的幾種算法

摘要：基于模乘法逆元的定義、存在條件及其相關(guān)定理，首先，對(duì)各求模逆元的算法思想和計(jì)算過程進(jìn)行了深入的剖析，并總結(jié)了它們各自的運(yùn)算特點(diǎn)以及它們的局限性所在，最后，依據(jù)可計(jì)算的復(fù)雜性理論和實(shí)際所測試的數(shù)據(jù)，比較了各種算法的執(zhí)行效率以及它們的使用范圍。關(guān)健詞：模逆元；擴(kuò)展歐幾里得算法；二進(jìn)制擴(kuò)展歐幾里得算法；牛頓迭代法；費(fèi)馬小定理中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)11-20308-031 引言模算術(shù)就是用算術(shù)表達(dá)式模一些非零整數(shù)的計(jì)算。（剩余4119字）

離散數(shù)學(xué)中，怎么求幺元，逆元，如圖所提

從最右邊一列找一個(gè)元素，它所在行與表頭的首行完全一致，即為左幺元，圖中是a。

從最上邊一行找一個(gè)元素，它所在列與表頭的首列完全一致，即為右幺元，圖中是a。

所以a是幺元。

逆元就從每一行、每一列找到等于a的地方，逆元也分左右逆元，左右逆元相等，這個(gè)元素才存在逆元。

a的逆元自然是a。

b的左逆元是d，右逆元也是d，所以b與d互為逆元。

同理，c的逆元是c。

1）應(yīng)該是求逆元.具體怎么回事，我是怎么也看不懂

1、單位元、逆元必須在集合Z中；這是定義，當(dāng)然，這么定義是有道理的：討論一個(gè)代數(shù)系統(tǒng)，討論其特殊性質(zhì)，如果令其具備某些特性的元素居然都不包含在其集合內(nèi)部，那我們還能說這種特性是屬于這個(gè)代數(shù)系統(tǒng)的嗎？難道一個(gè)代數(shù)系統(tǒng)的特性還要依賴一個(gè)或一些外部元素嗎？2、對(duì)于(Z,*)而言，所謂的逆元就是元素的倒數(shù)。Z中除±1之外，其他元素的“逆元”都不在Z中——更準(zhǔn)確地說，在這個(gè)代數(shù)系統(tǒng)中，除±1之外其他元素都沒有逆元。所以，這個(gè)代數(shù)系統(tǒng)連“群”都不是，更別說阿貝爾群了。3、就代數(shù)系統(tǒng)(Z,+)而言，它確實(shí)是封閉的；也如你所說，Z確實(shí)是“無限大”的——整數(shù)集中有無窮多個(gè)元素。因?yàn)槿我鈨蓚€(gè)整數(shù)之和仍然是整數(shù)，所以(Z,+)是封閉的。但集合的無窮性卻不是封閉性的必要條件。有限集合也能構(gòu)造封閉的代數(shù)系統(tǒng)，關(guān)鍵在于“運(yùn)算”。因?yàn)閿?shù)的加法計(jì)算是開放性的，所以加法必須在無窮集上才能保持封閉性（除非只包含零元這一個(gè)元素，({0},+)就是封閉的，無論怎么加，結(jié)果還是零元本身）；但也有很多運(yùn)算是非開放性的。隨便舉兩個(gè)例子：（1）求余運(yùn)算：比如用3除的余數(shù)，只有0、1、2這3個(gè)，那么({0,1,2},mod3)就是一個(gè)封閉的代數(shù)系統(tǒng)——當(dāng)然，“mod3”是一個(gè)一元運(yùn)算。（2）邏輯或運(yùn)算：A或B；A、B都是邏輯命題，取值范圍為{真，假}；其計(jì)算結(jié)果也是一個(gè)邏輯命題，取值范圍還是{真，假}，所以（{真，假}，或）就是封閉的。

逆元通俗理解，舉生活例子

廢話不多說，直接總結(jié)。

在模運(yùn)算中，

加法單位元： 0 因?yàn)?(a+0) ≡ a (mod m)；

乘法單位元： 1 因?yàn)?(1*a) ≡ a (mod m)；

而逆元呢，就是把上面的倒過來；

定義 對(duì)a∈Zm，存在b∈Zm，使得 a+b ≡ 0 (mod m) 則b是a的加法逆元，記b= - a。

定義 對(duì)a∈Zm，存在b∈Zm，使得 a×b ≡1 (mod m) 則稱b為a的乘法逆元。

具體計(jì)算對(duì)于乘法逆元：

在mod m的操作下（即Zm中），a存在乘法逆元當(dāng)且僅當(dāng)a與m互質(zhì)。

不定方程ab+mx=1的任意一組整數(shù)解(b,x)，b就是a的乘法逆元。具體計(jì)算可以使用擴(kuò)展歐幾里德算法 (Extended-GCD) 。

在有限域中怎么求一個(gè)多項(xiàng)式的逆元

把生成這個(gè)有限域的生成多項(xiàng)式作為模多項(xiàng)式，用輾轉(zhuǎn)相除法（歐幾里得算法）不停模生成多項(xiàng)式得余式直到1（肯定是1啊，因?yàn)榻o出的多項(xiàng)式有逆元，和模多項(xiàng)式互質(zhì)的）。（可能模多項(xiàng)式次數(shù)比給出的多項(xiàng)式次數(shù)高，第一步除以模多項(xiàng)式，商式是0，余式是給出的多項(xiàng)式）

然后如同求ax=1(mod m)一樣反向進(jìn)行，把1用模多項(xiàng)式和給出的多項(xiàng)式的“線性組合”表示出來，給出的多項(xiàng)式的“系數(shù)”多項(xiàng)式就是這個(gè)多項(xiàng)式的逆元啦。

可以檢查一下算錯(cuò)沒有，求出逆元后和給出的多項(xiàng)式在模生成多項(xiàng)式下相乘，看是否等于1。

過程中涉及多項(xiàng)式長除法，挺費(fèi)紙的。

我在百度搜到幾篇博客，都是通過mod（x^(n/2)）找到與mod(x^n)的關(guān)系，求解方法還涉及FFT,這應(yīng)該屬于偏工程的算法吧，沒仔細(xì)看不是很清楚。

Z5中所有可逆元的逆元

Z5中所有可逆元的逆元個(gè)數(shù)為4.0。這是一種古典密碼體制，有其較為專業(yè)固定的計(jì)算邏輯。