ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

Math

RSAの基本的な解説. 巨大な合成数の素因数分解が困難であることを安全性の根拠としたアルゴリズム. \( (p, q) \rightarrow N (= pq) \): 易しい \( N \rightarrow (p, q) \): 難しい [追記 (2019.09.27)] RSAが巨大な合成数の素因数分解が困難であることを安…

タイトルは後で考える

いくつか命題を証明していきたい. 奇素数pを法とすると平方剰余の個数は(p-1)/2個となる \(A := \{x^{2} \, mod \, p \mid x \in GF(p) \} \) としたときに, \( \#A = \frac{p-1}{2} \) となることを示したい. まず\(GF(p) = \{1, 2, ..., p-1 \}\), \(\#GF(…

Euler's criterion 平方剰余の判別

整数論において奇素数\(p\)をModulusとしたとき, \(a \in GF(p)\)について $$ x^{2} \equiv a \, mod \, p $$ となる \(x\)が存在するとき\(a\)を\(p\)の平方剰余であるという. \(a\)が平方剰余であるかどうか(上式で解を持つかどうか)を判定するのに使われ…