可逆元是怎么計算的 1）應該是求逆元.具體怎么回事，我是怎么也看不懂
求模逆元的幾種算法，離散數學中，怎么求幺元，逆元，如圖所提？1）應該是求逆元.具體怎么回事，我是怎么也看不懂？逆元通俗理解，舉生活例子，在有限域中怎么求一個多項式的逆元？Z5中所有可逆元的逆元。
本文導航
求模逆元的幾種算法
摘要：基于模乘法逆元的定義、存在條件及其相關定理，首先，對各求模逆元的算法思想和計算過程進行了深入的剖析，并總結了它們各自的運算特點以及它們的局限性所在，最后，依據可計算的復雜性理論和實際所測試的數據，比較了各種算法的執(zhí)行效率以及它們的使用范圍。關健詞：模逆元；擴展歐幾里得算法；二進制擴展歐幾里得算法；牛頓迭代法；費馬小定理中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)11-20308-031 引言模算術就是用算術表達式模一些非零整數的計算。（剩余4119字）
離散數學中，怎么求幺元，逆元，如圖所提
從最右邊一列找一個元素，它所在行與表頭的首行完全一致，即為左幺元，圖中是a。
從最上邊一行找一個元素，它所在列與表頭的首列完全一致，即為右幺元，圖中是a。
所以a是幺元。
逆元就從每一行、每一列找到等于a的地方，逆元也分左右逆元，左右逆元相等，這個元素才存在逆元。
a的逆元自然是a。
b的左逆元是d，右逆元也是d，所以b與d互為逆元。
同理，c的逆元是c。
1）應該是求逆元.具體怎么回事，我是怎么也看不懂
1、單位元、逆元必須在集合Z中；這是定義，當然，這么定義是有道理的：討論一個代數系統(tǒng)，討論其特殊性質，如果令其具備某些特性的元素居然都不包含在其集合內部，那我們還能說這種特性是屬于這個代數系統(tǒng)的嗎？難道一個代數系統(tǒng)的特性還要依賴一個或一些外部元素嗎？2、對于(Z,*)而言，所謂的逆元就是元素的倒數。Z中除±1之外，其他元素的“逆元”都不在Z中——更準確地說，在這個代數系統(tǒng)中，除±1之外其他元素都沒有逆元。所以，這個代數系統(tǒng)連“群”都不是，更別說阿貝爾群了。3、就代數系統(tǒng)(Z,+)而言，它確實是封閉的；也如你所說，Z確實是“無限大”的——整數集中有無窮多個元素。因為任意兩個整數之和仍然是整數，所以(Z,+)是封閉的。但集合的無窮性卻不是封閉性的必要條件。有限集合也能構造封閉的代數系統(tǒng)，關鍵在于“運算”。因為數的加法計算是開放性的，所以加法必須在無窮集上才能保持封閉性（除非只包含零元這一個元素，({0},+)就是封閉的，無論怎么加，結果還是零元本身）；但也有很多運算是非開放性的。隨便舉兩個例子：（1）求余運算：比如用3除的余數，只有0、1、2這3個，那么({0,1,2},mod3)就是一個封閉的代數系統(tǒng)——當然，“mod3”是一個一元運算。（2）邏輯或運算：A或B；A、B都是邏輯命題，取值范圍為{真，假}；其計算結果也是一個邏輯命題，取值范圍還是{真，假}，所以（{真，假}，或）就是封閉的。
逆元通俗理解，舉生活例子
廢話不多說，直接總結。
在模運算中，
加法單位元： 0 因為 (a+0) ≡ a (mod m)；
乘法單位元： 1 因為 (1*a) ≡ a (mod m)；
而逆元呢，就是把上面的倒過來；
定義 對a∈Zm，存在b∈Zm，使得 a+b ≡ 0 (mod m) 則b是a的加法逆元，記b= - a。
定義 對a∈Zm，存在b∈Zm，使得 a×b ≡1 (mod m) 則稱b為a的乘法逆元。
具體計算對于乘法逆元：
在mod m的操作下（即Zm中），a存在乘法逆元當且僅當a與m互質。
不定方程ab+mx=1的任意一組整數解(b,x)，b就是a的乘法逆元。具體計算可以使用擴展歐幾里德算法 (Extended-GCD) 。
在有限域中怎么求一個多項式的逆元
把生成這個有限域的生成多項式作為模多項式，用輾轉相除法（歐幾里得算法）不停模生成多項式得余式直到1（肯定是1啊，因為給出的多項式有逆元，和模多項式互質的）。（可能模多項式次數比給出的多項式次數高，第一步除以模多項式，商式是0，余式是給出的多項式）
然后如同求ax=1(mod m)一樣反向進行，把1用模多項式和給出的多項式的“線性組合”表示出來，給出的多項式的“系數”多項式就是這個多項式的逆元啦。
可以檢查一下算錯沒有，求出逆元后和給出的多項式在模生成多項式下相乘，看是否等于1。
過程中涉及多項式長除法，挺費紙的。
我在百度搜到幾篇博客，都是通過mod（x^(n/2)）找到與mod(x^n)的關系，求解方法還涉及FFT,這應該屬于偏工程的算法吧，沒仔細看不是很清楚。
Z5中所有可逆元的逆元
Z5中所有可逆元的逆元個數為4.0。這是一種古典密碼體制，有其較為專業(yè)固定的計算邏輯。
