密碼學(xué)——第4章-數(shù)論與有限域基礎(chǔ)-資料下載頁
2025-08-05 05:48本頁面
【正文】 ?最感興趣的是模 2 ? 即所有系數(shù) 0 或 1，例： ? 令 ??(??) = ??3 + ??2 ， ??(??) = ??2 + ?? + 1 ??(??) + ??(??) = ??3 + ?? + 1 ??(??) ???(??) = ??5 + ??2 有限域基礎(chǔ) ?多項式除法 ? 多項式可以寫作： ?? ?? = ?? ?? ??? ?? + ?? ?? ??(??) 稱為余式，記作 ??(??) = ??(??) ?????? ??(??) ? 若余式為 0，則稱 ??(??) 整除 ??(??)，因式 ? 若除了 1 和自身， ??(??) 沒有其它因式，則稱為不可約多項式或者素多項式 ? 關(guān)于不可約多項式的模運算構(gòu)成一個域 有限域基礎(chǔ) ? 最大公因式 ? 能夠整除兩個多項式的最高次多項式 ? ??(??) = ??????(??(??),??(??)) ? 同樣采用歐幾里得算法求解 ????????????,??(??),??(??) ??.??(??) = ??(??)。 ??(??) = ??(??) ??.???? ??(??) = 0 ???????????? ??(??) = gcd ,??(??),??(??) ??.??(??) = ??(??) ?????? ??(??) ??.??(??) ? ??(??) ??.??(??) ? ??(??) ??.???????? 2 有限域基礎(chǔ) ?????(2??)上的多項式運算 ? 多項式的系數(shù)模 2運算 ? 多項式的次數(shù)低于 ?? ? 多項式模一個 ??次不可約多項式 ? 構(gòu)成一個有限域 ? 采用擴展的歐幾里得算法 總能找到乘法逆元 有限域基礎(chǔ) ? 在 ????(????) 中 (??2 +1) 對應(yīng)于 ???????? ， (??2 +?? +1) 對應(yīng)于 ???????? ?多項式加法定義： ? (??2 +1) + (??2 +?? +1) = ?? ，即 ?????? ?????? ?????? = ???????? ?多項式乘法定義： ? (?? +1).(??2 +1) = ??.(??2 +1) + 1.(??2 +1) = ??3 +?? +??2 +1 = ??3 +??2 +?? +1 ? ??????.?????? = ?????? ? 1 ?????? (??????) ? 0 = ???????? ?????? ???????? = ?????????? ?多項式模運算定義： ? (??3 +??2 +?? +1 ) ?????? (??3 +?? +1) = 1.(??3 +?? +1) + (??2) = ??2 ? ???????? ?????? ???????? = ???????? ?????? ???????? = ?????????? 有限域基礎(chǔ) ? 在 ????(????) 上多項式的乘法逆元 ? ???????????????? ???????????? ?? ?? ,?? ?? 1. ??1 ?? ,??2 ?? ,??3 ?? ← 1,0,?? ?? 。 ??1 ?? ,??2 ?? ,??3 ?? ← 0,1,?? ?? 2. ???? ??3 ?? = 0 ???????????? ??3 ?? = gcd ?? ?? ,?? ?? 。 ???? ?????????????? 3. ???? ??3 ?? = 1 ???????????? ??3 ?? = gcd ?? ?? ,?? ?? 。 ??2 ?? = ?? ?? ? ?? ?????? ?? ?? 4. ?? ?? = ???????????????? ??????3 ????3 ?? 5. ??1 ?? ,??2 ?? ,??3 ?? ←??1 ?? ??? ?? ??1 ?? ,??2 ?? ??? ?? ??2 ?? ,??3 ?? ??? ?? ??3 ?? 6. ??1 ?? ,??2 ?? ,??3 ?? ← ??1 ?? ,??2 ?? ,??3 ?? 7. ??1 ?? ,??2 ?? ,??3 ?? ??1 ?? ,??2 ?? ,??3 ?? 8. ???????? 2 有限域基礎(chǔ) 本章小結(jié) ?素數(shù)與互素 ?整數(shù)模運算 ?群、環(huán)、域的基本概念 ?歐幾里得算法 ?有限域 GF(p) ?GF(2n) 有限域上的多項式運算 本章 作業(yè) 1. 計算 1234 mod 4321 的乘法逆元 2. 作業(yè) 3. 證明擴展歐幾里得算法的正確性
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1