日韩美女18网站久久精品,伊人久久大香线焦AV综合影院,久久青青国产

一個歐拉數整除問題的兩種證法

參考文獻

[1] 代數學基礎與有限域林東岱

[2] 抽象代數趙春來徐明曜

posted @ 2025-06-20 18:41 春秋十二月閱讀(78) | 評論 (0) | 編輯收藏

有限域上的特征與指數和之擴展

符號含義

關于特征的結論

關于指數和的結論

參考文獻

[1] 代數學基礎與有限域林東岱

[2] 代數與數論李超周悅

[3] 關于群的一些結論及應用本人

posted @ 2025-06-05 09:30 春秋十二月閱讀(120) | 評論 (0) | 編輯收藏

二元二次型的相似變換、正定性與正交分解

本文主要闡述用兩種方法判斷給定兩個二元二次型是否相似，相似情況下的具體變換。
相似變換如果確定了，也利于判斷正定性，因為相似二次型的正定性相同。最后講到了正交分解，
給出怎么求相似的整數對角矩陣

基本定義

下述定義來自文獻[1] 12.1節，有所擴展

變換求解

先來看運用解方程的方法

再來看用矩陣的觀點方法，求解變換。這種方法更適合求解到對角型的變換

正交分解

參考文獻

[1] 華羅庚文集數論卷2

[2] 高等代數丘維聲

posted @ 2025-04-25 19:05 春秋十二月閱讀(271) | 評論 (0) | 編輯收藏

關于群的一些結論及應用

【命題1】所有群同態的原像個數相同，即為核的大小

下面看下這個結論在文獻[1]中3.2節的應用

【命題2】所有元素階小于等于2 的群為交換群，且其階為2的整數冪

該結論在https://zhuanlan.zhihu.com/p/644888274中的推論2.2證明中用到

【命題3】群中任一元的相對于正規子群的指數次冪屬于正規子群，2階正規子群必

屬于群的中心

【定理1】模奇合數的既約乘法群，其中雅可比符號為1的元素構成它的子群，其階為

既約乘法群群階的一半

【定理2】設G是群，H、K是有限子群，則HK的大小等于H的階與K的階乘積除以H與K交群的階

參考文獻

[1] 橢圓曲線及其在密碼學中的應用—導引 Andreas Enge

[2] 抽象代數I 趙春來徐明曜
[3] 華羅庚文集數論卷2

[4] 組合數學馮榮權宋春偉

posted @ 2025-04-22 21:18 春秋十二月閱讀(267) | 評論 (0) | 編輯收藏

不定方程的代數數論解法

符號含義與適用前提

二次域的基本結論

x²-dy²=±1

x² + d = y³

x² + y² = n

參考文獻
[1] 代數與數論李超周悅

posted @ 2024-12-23 11:33 春秋十二月閱讀(344) | 評論 (0) | 編輯收藏

關于橢圓曲線的驗證計算

符號含義

E 表示滿足橢圓曲線Weierstrass方程上的點群

K 代數閉域，用來限制Weierstrass方程的系數與E中的點

E(K) 定義在K上的點群E

E/K 定義在K上的橢圓曲線E

End(E) E上的自同態環

域擴張分析

End(E)模與Z代數

極點首項系數

除子映射及同構

同種映射同態性的解釋

Hasse定理之引理證明的補充

撓曲線及其個數

有限域上的橢圓曲線

一種確定型群階計算法

奇素域上的算法應用

GF域上的群階計算

Schoof算法正確性根本

一種計算橢圓曲線群的階的確定型多項式時間算法，確定型是因為算法內部沒有隨機選擇/概率拋幣操作，多項式時間是因為域k的乘法與求逆總次數是O((logq)^6)
（q為k的大小，乘法與求逆相對加減運算顯著耗時）。具體原理及流程詳見參考文獻[1]中5.2節。這里給出筆者的一些思考

1. Hasse定理（Frobenius自同態方程式）在扭點群上的限制亦成立，這決定了t模l的一個同余方程成立，且在模l的最小非負剩余系下解是唯一的

2. 孫子定理保證了某取值范圍內的一個t模L（L為各素因子l的乘積）的唯一解，即由t模L各個素因子l的同余方程構成的同余方程組的解是唯一的

3. L必須大于t取值上限的2倍。這是為了算法求得的解滿足上述2（否則在更小的L內得到的解不唯一，因L與t上限或下限間的某數可以與t模L同余）

4. 素因子l的選擇排除2與橢圓曲線特征p。這是因為算法構造所依賴的一個引理之前提條件：為奇素數保證l次除子多項式屬于k[X]，即引理論斷有意義；
不等于p保證檢測一個多項式f是否零多項式的充要條件成立，即可以用l次除子多項式去整除f來判斷。另l為素數保證了與其它除子多項式（及其冪次）互素
另外發現了算法的一處瑕疵，即第4步預計算除子多項式與Frobenius自同態的復合少了兩個值，這導致第5步可能崩潰，當依賴的后續兩個復合多項式沒被計算時。
這個糾正可通過修改第4步擴大2個值，或第5步通過除子多項式的遞推公式按需計算

扭點的階計算正確性根本

在密碼學中的應用

選取原則

1. 排除超奇異橢圓曲線。這是為避免MOV等約化攻擊，約化攻擊時間復雜度是亞指數

2. 有限域的選擇要使E(F_q)的群階足夠大。這是為了緩解Shanks及Pollard ρ攻擊

3. E(F_q)存在階為大素數的子群。這是為了抵抗Pohlig-Hellman攻擊

對于第1點，就排除了char(K)=2或3且j(E)=0對應的如下標準形式曲線

Y²+α₃Y=X³+α₄X+α₆（α₃≠0）與 Y²=X³+α₄X+α₆

一種典型方案
橢圓曲線及有限域的選擇使得|E(F_q)|=cm，且char(F_q) ∤ q+1-cm。其中m是一個大素數（通常不低于256位二進制長度，提供中長期安全性），c小于m。
m階子群的生成元可通過以下方法確定：隨機選擇E上的一個有理點P，如果Q=cP為零元（即無窮遠點），則重復選擇，直到其不等于零元。
一旦找到了生成元，那么子群就可以構造出來了。下面分析正確性

參考文獻

[1] 橢圓曲線及其在密碼學中的應用—導引 Andreas Enge

[2] 算法數論裴定一、祝躍飛

[3] The Arithmetic of Elliptic Curves Joseph H. Silverman

[4] 標識密碼學程朝輝

[5] 代數學基礎與有限域林東岱

[6] 抽象代數I 趙春來徐明曜

[7] 代數與數論李超周悅

posted @ 2024-11-10 21:45 春秋十二月閱讀(317) | 評論 (0) | 編輯收藏

不可約多項式判別算法的改正

原本算法

摘抄參考文獻1中附錄的算法流程如下

例子測驗

改正后的算法

改正之前，先理清原本算法判別不可約多項式所用的原理。其原理是若f(x)可約，當且僅當存在次數i<=d=[deg(f(x))/2]的不可約因子g(x)，而此時gcd(x^{q^i}-x, f(x))≠1。
根據參考文獻2（詳見如下定理），x^{q^i}-x是所有i次不可約多項式的乘積，因此它必定包含g(x)而與f(x)存在公因子。不可約判別算法的思想應該是遍歷次數1到d的所有不可約多項式
（沒必要檢測大于d的不可約多項式，因為若f(x)可約則其分解因子中必定存在不大于d的不可約多項式），檢測輸入多項式與它們是否存在公因子。所以這個原理是正確的，只是實現不對，
略作改正如下（類c語言描述）

重新測驗

參考文獻

[1] 算法數論裴定一、祝躍飛

[2] 代數學基礎與有限域林東岱

posted @ 2024-09-07 23:07 春秋十二月閱讀(350) | 評論 (0) | 編輯收藏

論證有限域上平方根的求解

通用算法

先摘抄參考文獻[1]中的算法流程如下

正確性分析
下面證明以上算法用到的事實結論，提煉為如下幾個引理

算法構造思想
用到二次剩余知識，即一個待求平方元ɑ可以且只能表示為兩個平方因子的乘積，其中一因子為任意隨機選取的非平方因子β的偶數冪，
另一因子為葉子群H的一元素r，H作為陪集劃分根群（有限域乘法群）得到β生成的集合即商群G/H的一個代表元系。這樣一來，將開方轉化為β與r的乘方運算，
迭代的過程就是為求那個具體的代表元β^e中的指數e（注意e必為偶數），從G_s-2到G₀=H，迭代結束后r被唯一確定，r的開方等于r的(t+1)/2次方（因為t是H的階且為奇數，r^t+1=r）。
觀察算法流程，可以發現如果分解q-1后得到s=1，那么就沒必要選取非平方元β了（這時令β=1），直接跳到第6步得到結果。僅當s≠1才隨機選取β。這樣改進后可加快算法運行

例子測驗

特殊算法
當q是素數且q≡3(mod 4)時，存在更快的算法及測驗如下

參考文獻

[1] 算法數論裴定一、祝躍飛

posted @ 2024-08-30 22:22 春秋十二月閱讀(473) | 評論 (0) | 編輯收藏

求解離散對數問題的Terr算法

基本原理

再來看Terr算法用到的如下定理
定理（基于參考文獻1改正后的描述）對每一正整數t，存在唯一確定的一組整數k和j，0<=k<j，使得t=T_j+1-k，其中T₀=0，T_n=T_n-1+n-1，n>=1

如果t=0，那么j在區間[0,1)，故只能取0，此時k=0與條件k<j矛盾，若允許k=j，則不保證唯一，比如t=1 => j=1, k=0 或 j=2, k=2。
所以參考文獻1中原來定理的描述“對每一非負整數t”是錯誤的。下面列舉一些實例驗證j與k的唯一解

t=1 => j=1, k=0

t=2 => j=2, k=1

t=3 => j=2, k=0

t=4 => j=3, k=2

t=5 => j=3, k=1

t=6 => j=3, k=0

算法偽代碼

例子測驗

參考文獻

[1] 代數學基礎與有限域林東岱

posted @ 2024-08-15 22:35 春秋十二月閱讀(747) | 評論 (0) | 編輯收藏

簡單私鑰加密構造的驗證及安全性分析

私鑰分組加密

上圖的證明中，r^(j)兩兩不同的概率計算是關鍵，下面給出詳細過程

另外兩個分布統計的不同意味著計算可分辨（反之則計算不可分辨），亦即r^(j)至少兩個相同的概率。

Construction 5.3.9一次只能加密與密鑰等長的明文，如果要加密更長的明文，怎么辦？一個簡單直接
的方法是將明文分成多個大小為n的塊，對每個塊調用上述加密步驟，那么就得到形如下的密文塊序列

密文塊序列從Proposition 5.3.10的證明中可知是計算不可分辨的，滿足「多組消息安全性」。但對于解密
需要存儲每一塊的隨機數，因此比較占空間，所以衍生出下面更高效的方案Construction 5.3.12

私密通用加密

語義安全性分析

抗主動攻擊安全性

以上兩種構造因滿足「多組消息安全性」，故滿足CPA與CCA1，具體的證明可參考Oded Goldreich《密碼學基礎》的Proposition 5.4.12、Proposition 5.4.18。
但不滿足CCA2，因為攻擊者拿到挑戰密文后，可以修改它再發出解密質疑，得到回答的明文從而異或求解f_k(r_i)，最后與挑戰密文異或求解挑戰明文
對于通用加密構造的CCA2攻擊細節如下

posted @ 2024-06-29 17:00 春秋十二月閱讀(654) | 評論 (0) | 編輯收藏

僅列出標題

常用鏈接

留言簿(76)

隨筆分類(160)

隨筆檔案(161)

文章分類(30)

關注的開源項目

最新隨筆

積分與排名

最新評論

閱讀排行榜

評論排行榜