第七章 數論和密碼學困難性假設
知識點
素數、模運算、群、子群、群同構、中國剩餘定定理、生成随機素數、素數判定、因子分解假設、RSA假設、循環群、生成元、離散對數和Diffie—Hellman假設、橢圓曲線群、單向函數和置換、構造抗碰撞的散列函數
專業術語
non-trivial factor：非平凡因子 除1和自身之外的因子
prime:素數 composite:合數
division with remainder：帶餘除法
gcd: greatest common divisor
relatively prime:互素
Modular Arithmetic：模算術
reduction modulo N：模N的消減運算
congruent modulo N/Congruence modulo N：模N同餘
equivalence relation:等價關系 reflexive、symmetric、transitive：自反、對稱、傳遞
(multiplicative) inverse：（乘法）逆元 b invertible modulo N：b模N可逆
binary operation：二進制運算 group：群
Closure：封閉性 Existence of an Identity：存在機關元 Existence of Inverses：存在逆元
Associativity：結合律 Commutativity：交換律 abelian：阿貝爾群
finite group：有限群 the order of the group：群的階
subgroup：子群 trivial subgroups：平凡子群 strict subgroup：嚴格子群
cancelation law：消去律
permutation：置換 Group Isomorphisms：群同構
bijection：雙射
Chinese Remainder Theorem：中國剩餘定理
factoring：因子分解 factorization：因數分解
trial division：試除法
one-way function：單向函數
cyclic groups：循環群
iff:當且僅當
Discrete Logarithm：離散對數
discrete logarithm of h with respect to g：關于g的h的離散對數
computational Diffie-Hellman (CDH) problem:計算Diffie-Hellman問題
decisional Diffie-Hellman (DDH) problem：判定Diffie-Hellman問題
quadratic residue modulo p:模p平方剩餘
elliptic curves：橢圓曲線
重要/疑難定理
中國剩餘定理從具體到抽象
素數判定
Q&A
群的階和群中元素的階的定義？
群的階：群中元素的個數
群中元素的階：
離散對數實驗
？
答：雙數線表示一個範數，1階範數相當于比特長度，表示q是n比特長
括号中後面這個條件確定了方程沒有重根如何得到的？
可由三次方程重根判别式推導化簡得到