久久久无码精品午夜,久久久久久夜精品精品免费啦,久久夜色精品国产网站

二元二次型的相似變換與正定性

本文主要闡述用兩種方法判斷給定兩個二元二次型是否相似，相似情況下的具體變換。
相似變換如果確定了，也利于判斷正定性，因為相似二次型的正定性相同

基本定義

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

變換求解

先來看運用解方程的方法

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

參考文獻

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

[2] 高等代數丘維聲

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

關于群的一些結論及應用

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

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

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

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

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

屬于群的中心

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

既約乘法群群階的一半

參考文獻

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

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

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

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

不定方程的代數數論解法

符號含義與適用前提

二次域的基本結論

x²-dy²=±1

x² + d = y³

x² + y² = n

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

posted @ 2024-12-23 11:33 春秋十二月閱讀(321) | 評論 (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 春秋十二月閱讀(286) | 評論 (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 春秋十二月閱讀(310) | 評論 (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 春秋十二月閱讀(432) | 評論 (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 春秋十二月閱讀(703) | 評論 (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 春秋十二月閱讀(634) | 評論 (0) | 編輯收藏

二元有限域及其擴域上的計算

定義

Berlekamp分解算法

AES有限域

不可約性證明

非本原性驗證


  找出本原元


不可約多項式個數

線性移位寄存器m序列
根據參考文獻1知線生移位寄存器產生m序列的充要條件是特征多項式f(x)為本原多項式。而確立有限域上的本原多項式，主要有兩種方法：
一種方法是根據F_q上所有次數為n的本原多項式的乘積正好等于割圓多項式Q_e，其中e=qⁿ-1，從而所有次數為n的本原多項式可以通過分解Q_e得到。
另一種方法是通過構造本原元再求本原元的極小多項式，先素因子分解qⁿ-1=p₁p₂...p_k，如果對每一p_i都有ord(α_i)=p_i，那么α=α₁α₂...α_k的階就是qⁿ-1，
因此是F_q上的本原元，則f(x)=(x-α)(x-α²)...(x-α^r)，r=qⁿ-1（因為α是本原元，所以n是使α^{q^n}=α成立的最小正整數）。

求解本原多項式
假設線性移位寄存器的級數為4，這里使用上述二種方法求F₁₆上的本原多項式，過程如下
分解割圓多項式法

構造極小多項式法

本原多項式個數

m序列示例

參考文獻
[1] 代數學基礎與有限域林東岱

posted @ 2024-05-16 13:41 春秋十二月閱讀(907) | 評論 (0) | 編輯收藏

簡單連分數攻擊RSA的迭代次數分析

【適用前提】大整數N=pq的素因子p<q<2p，解密指數d<(1/3)N^1/4 【攻擊方法】
1）用歐幾里得算法計算e/N的各個漸近分數k_i/d_i，i>=1，直至d_i>=(1/3)N^1/4，記錄此時的i為m。令i=1
2）計算T=(e*d_i-1)/k_i，若T不為整數則轉到4），否則轉到3）
3）解方程f(x)=x²-(N-T+1)x+N=0的根，如果有正整數根且兩個根皆小于N，則輸出p、q，并返回成功。否則轉到4）
4）遞增i，若i<m則轉回2），否則返回失敗
該方法即Wiener算法用到了關于連分數的一個定理：若α為任一實數，有理數p/q適合|α-(p/q)|<1/(2q²)，則p/q必為α的某一漸近分數。證明詳見參考文獻[2]。
由定理可知攻擊方法是可行的，必能找到使f(x)=0有合理解的某漸近分數。下面證明：攻擊迭代次數的上界為