Pebble Coding

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

数学

SageMath 入門

ほぼpythonと同じ構文と考えておけばよいです。 100未満の素数を出力する sage: x = 1 sage: while x < 100: ....: if x.is_prime(): ....: print(x) ....: x = x + 1 ....: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 プログ…

SageMath のインストール方法と使い方

数学の研究に便利な SageMath のインストール方法と使い方です。 macOSの場合です。 こちらのページから以下のファイルをダウンロードします。 http://ftp.yz.yamagata-u.ac.jp/pub/math/sage/osx/intel/index.html sage-8.5-OSX_10.14.2-x86_64.tar.bz2 解…

楕円曲線における離散対数問題

例として、 を考えます。 有理点の数(群位数)は31で素数です。 点の加法群の位数が31ということは部分群が存在せず、巡回群つまり一つの元を足し合わせることで全ての元が表現できるということです。 全ての点が位数31となります。 ちなみに、無限遠点O以外…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその4

y'についてもみていきます。 を使うと、 残りのフロベニウス写像部分は したがって、 分母を揃え、分子だけ取り出したものがで割り切れるかどうかを調べます。 コンピュータ計算上は分母にyが含まれるか否かの分岐が面倒なので、 分子だけの計算結果にyが含…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその3

アルゴリズムの実際の計算をもう少し詳しくみていきます。 が成り立つかどうかの計算をみていきます。 まず、この式はがreductionの最終結果がxのみの多項式で分母と分子があるということを意味します。 lは奇数なのでにはyは入らないです。 そして、で割り…

楕円曲線のn等倍点の多項式

楕円曲線の点(x, y)をn倍した点(n torsion point)はx,yの具体的な多項式で表せます。 としたとき、n倍点の座標(X, Y)は以下となります。 はdivision polynomialと呼ばれており、以下の漸化式で定義されます。 はmが奇数のとき、xの任意次数の関数。 mが偶数…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその2

楕円曲線の有理点の数の求め方 schoof アルゴリズムその1 - Pebble Coding の続きです。 を素数 l=2, 3, 5, ...について計算するアルゴリズムは以下の通りです。 素体, 楕円曲線とします。 まず、l=2の場合は、の値が1かどうか調べます。 ここでgcdはxの素…

中国剰余定理で2式の場合の解を求める

中国剰余定理とは、2式の場合を互いに素とするとき、 を満たす整数xがの範囲内にただ一つ存在するというものです。 xの求め方はこうです。 まずを満たす(p, q)のセットを一つ求めます。 以下のアルゴリズムを用います。 37x+10y = 1 を拡張されたユークリッ…

37x+10y = 1 を拡張されたユークリッドの互除法で解いてみる

37と10は違いに素なので、は整数解(x, y)を持ちます。 この解を求める方法を拡張されたユークリッドの互除法と呼ぶようです。 具体的には、の形でaをbで割った余りをaに置き換える操作を余りが0になるまで繰り返します。 とおきます。 とおきます。 とおきま…

素体上の1変数多項式の商と余り

こちら 多項式の割り算、商と余り - Pebble Coding の1変数多項式の商と余りを拡張し、素体上での計算をみてみます。 (nがxの最大次数)を、 (mがxの最大次数)() で割ることが考えるとき、以下のようにしてxの最大次数を下げていけばよさそうです。 例えば、 …

素体をpythonで実装する

素体 (pは素数)をpythonで実装してみました。 なお、計算効率については考慮していません。 #!/usr/bin/env python3 class F: def __init__(self, p, v): self.p = p self.v = v self.normalize() def normalize(self): self.v = self.v % self.p def __add_…

中国の剰余定理で3つの式がある場合を解く

を解きます。 これを満たすaは0以上、未満に一つしかありません。 とおけます。 とおけます。 が解となります。 一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語

1変数多項式の四則演算をpythonで実装する

1変数多項式の四則演算をpythonで実装してみました。 係数は整数の範囲としています。 加算、減算、乗算、剰余を実装します。 剰余では割られる側の最大次数の係数は1のみに限定します。 以下、実装です。 #!/usr/bin/env python3 from fractions import gcd…

多項式の割り算、商と余り

多項式の割り算、商と余りの求め方をみていきます。 1変数xの2つの多項式A(x), B(x)を考えます。多項式の係数は全て整数とします。 次数の大きい方をA(x), 次数の少ない方をB(x)とし、 ここでは次数の少ない方の多項式の最大次数の係数は1としておきます。 …

ユークリッドの互除法とpython3で最大公約数(GCD)を求める

2つの整数の最大公約数を求めるアルゴリズムとしてユークリッドの互除法があります。 2つの整数を割り算して余りを求める操作を繰り返し、余りが0になったら終了するアルゴリズムです。 pythonで2つの整数の最大公約数を求める関数gcd()を実装したのがこち…

有限体の楕円曲線の有理点の数とZ関数

有限体の楕円曲線の有理点の数からZ関数を導いていきます。 定理1 qを素数とし、有限体上の楕円曲線Eの有理点について、 とおきます。 また、の解を複素数とおきます。 すると、有限体 上の楕円曲線Eの有理点の数は、 となります。 証明は省略します。 ここ…

有限群の元のべき乗の位数

ラグランジュの定理 Gが有限群、 ならgの位数は群Gの位数の約数である。 この定理より、以下の定理が導かれます。 gが群Gの位数n>0の元でなら、の位数は である。 例: (65537は素数です)の場合、 の位数は

中国の剰余定理

中国の剰余定理 で m, n は互いに素とする。 つまり、 を満たすはの範囲にただ一つ存在する。 中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語 これは、2つの値の場合ですが、もっと拡張します。 を異なる素数とし、 ... を満たすxはの範囲…

ハッセの定理の証明に必要な知識

ハッセの定理の証明には長い道のりと知識が必要です。 ブログに書ける量ではありませんので、どのようにして証明されるのかの概要だけを見ていきたいと思います。 ハッセの定理 Eを有限体 (qは素数のべき)上の楕円曲線とする。 この楕円曲線の位数すなわち、…

有限体の代数閉包(algebraic closure)

Kを体とする時、n次の多項式の解を全て加えて作った体を代数閉包と呼びで表す。 Kが複素数体Cである時、その代数閉包はC自身である。 Kが素体 (p は素数)であるとき、その代数閉包は となる。 素体が有限集合であるのに対し、その代数閉包は無限集合である。

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

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

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

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

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

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

素体の等分点の群構造をしらべる その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にいくつかの元を添加して得られた…

プライバシーポリシー

お問い合わせ

スポンサーリンク