Hasse-Weilの定理を楕円関数に限定した形で書くと、 Cが有限体 上定義された非特異な楕円曲線であるとき、 C上の に座標を持つ点の数をと定義すると、 不等式だが、任意の楕円曲線に関するものだというのがすごい。 これを実感するために、pをくらいの数とす…

Cを で与えられる3次曲線とする。ここでa,bは整数。 このとき曲線上の有理点のなす群C(Q)は有限生成アーベル群である。 解(x,y)が無限個、有限個どちらの場合でも、有限個の元から出発し、群演算によって、全ての元を作り出せるといっている。

有限アーベル群と有限生成アーベル群の違いを直感的に説明する。 アーベル群の正確な定義は述べないが、一つの演算(加法や乗法と呼ぶ)が定義された数の集合としておく。 有限アーベル群とは元の数が有限であるアーベル群である。 例えば、加法として２つの整…

Nagell-Lutzの定理 を整数係数a,b,cを持つ非特異3次曲線とする。 P=(x,y)を有限位数の有理点とする時 x,yは整数である。 これは、整数ではない有理点が存在するときは、無限位数となるということも同時に示している。 例えば、 (a=0, b=0, c=2)の場合を考え…

ECDSA ( Elliptic Curve Digital Signature Algorithm )のWiki(日本語) 楕円曲線DSA - Wikipedia ECDSA のWiki(英語) Elliptic Curve Digital Signature Algorithm - Wikipedia EdDSA ( Edwards-Curve Digital Signature Algorithm ) のWiki EdDSA - Wikiped…

前回 RSA暗号化方式を紐解く その(1) - Pebble Coding からの続きです。 暗号化は の式によって行い、 復号化は の式によって行います。 これがうまく動作する仕組みを知るにはどうやってe, d, nを選ぶかということを知る必要があります。 理論の根幹をなす…

感覚をつかむため、まずは実際の数値での例を見てみましょう。 RSAの秘密鍵、公開鍵のペアを16bitの長さで生成してみました。 16bitを指定するとmodulusの大きさが16bitになります。 modulus:29353 秘密鍵 exponentE:65537 秘密鍵(通常65537固定なのであまり…

私がビットコインを入手した経緯は2015年に Bountysource というソフトウェアを作成したり、バグを直したりして報酬を得るサイトでバグを直したことによる報酬をビットコインで受け取ったことでした。2015年当時はUS DollorとBitCoinのどちらかが選べました…

与えられた数が素数かどうかを高い確率で高速に判定するアルゴリズムとしてミラーラビン(Miller-Rabin)判定法があります。 暗号の実装で素数が必要な時にこの判定法が使われることが多いようです。 厳密に素数かどうかを判定する方法として、試行割算法(Tria…

少し前でp mod8 = 5の場合のmod p での平方剰余の計算方法を示しました mod pでの平方剰余を計算する(p mod 8 = 5の場合) - Pebble Coding が、swiftで実装しておきます。 の解は存在すると仮定しておきます。 func quadraticResidue(_ a:Int, _ p:Int) -> I…