Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

数学

複素数閉包の楕円曲線等分点の群構造を調べる その3

やっと本命の定理です。 定理 Eを体K上の楕円曲線として、nを正の整数とする。 体Kの標数がnを割り切らないまたは0のとき、Eのn等分点のなす群はとの直積に等しい。 体Kの標数がp>0で, , であるとき、 または である。 この定理の証明はものすごく長いので、…

複素数閉包の楕円曲線等分点の群構造を調べる その2

今度は3等分点を考えます。 まず、複素数閉包の楕円曲線の標数が2でも3でもないことを仮定します。 標数というのは、こちら 標数 - Wikipedia によると、複素数の単位元(実数の1)をn個加算したものが、ゼロ元(実数の0)になる場合のnです。 つまり、複素数体…

複素数閉包の楕円曲線等分点の群構造を調べる その1

今までは、素体の等分点の群構造を調べてきましたが、ここから複素数体の楕円曲線の等分点の群構造を調べていきます。 正確には複素数体に無限遠点(O)を追加した閉包(closure)での等分点です。 無限遠点がないと単位元がなくなってしまいますからね。 複素数…

素体の等分点の群構造をしらべる その3

まだまだ、一般の等分点の式をみていくには例が足りません。 次の楕円曲線の2等分点を調べてみます。 F11 p mod 3 is 2 j:400 #E:16 1 torsion Point: 2 torsion Point: P1 P2 P11 3 torsion Point: 4 torsion Point: P1 P2 P7 P8 P11 P12 P13 5 torsion Poi…

secp256k1の群構造

secp256k1は素体で、 群位数は L = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 = 115792089237316195423570985008687907852837564279074904382605163141518161494337 であり素数ですから、巡回群(cyclic group)です。 つま…

素体の等分点の群構造を調べるその2

素体の等分点の群構造を調べる その1 - Pebble Coding の記事の最後の例で、等分点の群構造を調べました。 群構造を調べるには、2つの元を加算した元がどうなるかを全ての元について調べる必要があります。 具体的にどのようにするのかをみてみます。 群位…

コーシーの定理(群論)

コーシーの定理(群論) 有限群Gの位数をnとする。nの素因数pを位数にもつ部分群は必ず存在する。 例えば位数)の有限群がある場合、 位数の部分群は存在するということである。

mod pでの平方剰余を計算する(p mod 8 = 5) その2

www.pebblewind.com こちらの記事で、平方剰余を計算しましたが、ed25519 においては、aは u/v という形になっています。 u,vの計算量は少ないので、計算効率をあげるため、u,vを用いた掛け算になるように変形します。 (フェルマーの小定理) (余分な項が8の…

素体の等分点の群構造を調べる その1

楕円曲線Eにおいてとなる点Pの集まりを等分点(torsion point)と呼びます。 左辺は点をn倍することを表し、右辺は無限遠点を表します。 python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding 以前使ったpythonスクリプトをちょっといじ…

体論

定義 1 Kを体とする。任意の定数でない1変数多項式]に対し がありとなるとき、Kを代数閉体(algebraically closed field)という。 定理 1 Kが代数閉体で、fが の形である場合、 が存在し、である。 拡大体のゆるい定義 2 体Kにいくつかの元を添加して得られた…

楕円曲線の自己準同型

有限体 上の楕円曲線 上の有理点(x, y)を考える。 x座標,y座標はともに0以上p(素数)未満の整数。 2つの点に対する加法を以下で定義すると、この点と加法は群をなすことが知られている。 これを点の加法と呼ぶことにする。 楕円関数の加法公式 - Pebble Codi…

数学英単語

数学書に出てくる英単語がわかりずらいので、リストしておく。 division polynomials 等分多項式 homomorphism 準同型 endomorphism 自己準同型 isomorphism 同型 automorphism 自己同型 morphism 有理写像 injective 単射 (行き先が被らない関数) surjectiv…

群論におけるラグランジュの定理

ラグランジュの定理を解説します。 ここでは有限群のみを考慮対象とします。 まず、群の定義です。 有限個の元からなる集合Gを考えます。 集合Gから2つの元を選び、に対してを作用させて結果rを得るという操作(演算)を定義します。 この演算をここではで表…

準同型写像に関するカーネルの元の数についての定理

準同型写像に関する元の数についての定理を直観的に理解したいと思います。 G,Yを有限群とする。 群Gから群Yへの準同型写像(Homomorphism)を とする。 すなわち、 をGの任意の元として、 が成りたちます。 ここで左辺のプラスは群Gでの演算,右辺のプラスは群…

素体を拡大する

素体 を拡大してみます。 を拡大して、拡大体 を作ることにします。 体の拡大には既約多項式を使います。 ここでは、規約多項式を使います。 を作る場合は素数3で割った余りを使うというルールでした。 の元は{0, 1, 2}の3つですが、加法の単位元が0で乗法の…

平方剰余とは

平方剰余 http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf について簡単に説明しておきます。 整数aと整数pを与えた時に の式を満たす解xは存在する場合と、存在しない場合があります。 解が存在する時、a は p を法…

素体Fpの乗法群

素体は体であり、元は{0, 1, ..., p-1}のp個あります。 素体という時、pは素数です。 体なので、加法と乗法について閉じているわけですが、乗法演算の部分のみを取り出した群のことを、 素体の乗法群と呼びと書きます。 この乗法群には加法の単位元0は含まれ…

群論における写像

群論における写像の定義メモ。 準同型写像、同型写像、自己同型写像。 写像というのはプログラムで考えると、引数を一つ入力として持ち、戻り値を一つ返す関数だとイメージすることができますが、 要するに関数f(x)のことです。 準同型写像 関数f(x)が f(x)f…

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる

ここでは、有限体 (p=5) 楕円曲線 (a=0,b=1,c=1) の有理点をpythonで調べています。 有理点の数は9です。(無限遠点を含む) 無限遠点はOと出力しています。 加法公式を用いて、有理点{P1, P2, ... P8}を2倍,3倍,...,9倍した点も示しています。 この計算の途中…

macOS 10.12 jupyer notebook でグラフを描画する(Fpにおける楕円曲線の解の個数)

matplotlibをインストールします。 ~$ pip install matplotlib %matplotlib inline import numpy as np import matplotlib.pyplot as plt # 乱数を生成 x = np.random.rand(100) y = np.random.rand(100) # 散布図を描画 plt.scatter(x, y) plt.show() うま…

B-smooth と B-power-smooth

B-smooth と B-power-smooth の概念を押さえておきます。 B-smooth 任意の自然数Nを素因数に分解すると次の形になります。 ここで、はk番目の素数 {2, 3, 5, 7, 11, …}を表します。 は0以上の整数です。 ここで最も大きい素数として、 NをB-smoothであるとい…

ポラードのp-1因数分解法

大きな合成数を素因数分解(factorization in prime numbers)するアルゴリズムの一つにポラードのp-1法があります。 ポラードの (ロー)法とは別モノなので混同しないようにしましょう。 因数分解したい合成数をnとします。 の時、素数pを求めたいです。qはと…

体の標数(characteristic)

体Kにおいて、n個の1の和 1+1+…+1 が0となるような整数が存在するとき、その最小値を体Kの標数といい、ch(K)と表します。 いくつ加えても0にならない時は標数が0と定めます。 標数は0か素数です。 有理数体Qの標数は0です。 有限体の標数はpです。

体の拡大

拡大体 体とは大雑把に言って、加法と乗法に対して演算が閉じている数の集合のことを指します。 有理数Q, 実数体R, 複素数体Cは全て加法と乗法において演算が閉じているので体と呼べます。 これらは数の集合としては数の存在の密度が高すぎますね。 整数Zと…

約数記号

整数 a が 整数 b を割り切るとき と書きます。 例: 整数 a が整数 b を割り切らないとき と書きます。 例: であるとき、b は a の倍数であり、a は b の約数であるといいます。

Hasse-Weilの定理(楕円関数限定版)

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

Mordellの定理(位数2の有理点をもつ曲線の場合)

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

有限アーベル群と有限生成アーベル群

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

Nagell-Lutzの定理

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

素数を高い確率で高速に判定するミラーラビン判定法

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

プライバシーポリシー

お問い合わせ

スポンサーリンク