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