Pebble Coding

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

数学

円分体で使われる式

nを整数として、とすると以下が成り立つ。 2番めの式で、とすると、左辺は0になるが、右辺の(x-1)は0ではない。 したがって 1番目の式が正しいかも確認してみます。 ここで、とを使えば係数が全て1になることが分かります。 となり、係数が全て1であること…

多項式についてのガウスの補題(Gauss's Lemma)

、 であるとき、f(x)を原始多項式(primitive polynomial)と呼ぶ。 係数の中に一つでも1または-1があれば、原始多項式です。 ガウスの補題(Gauss's Lemma) 2つの原始多項式の積は原始多項式である。 証明はこちら。 原始多項式とその積について | 高校数学の…

n次多項式の重根判定と微分

定理 複素数体上の多項式を考える。1)と2)は同値である。 1) n次多項式f(x)は重根を持つ。 2) n次多項式f(x)のある根に対しが成り立つ 証明 1) -> 2) と書ける。 微分して、 したがって、が成り立つ。 証明 2) -> 1) 対偶である、「重根を持たなければ、全て…

division polynomialと等分点

楕円曲線のn等倍点の多項式(division polynomial) - Pebble Codingここで、division polynomial を示しました。 体K上の楕円曲線上の点P(x, y)をn倍(nは整数)した点は、division polynomialを用いて、以下のように書けます。 ここで、n等分点、つまり、n倍し…

モジュラー多項式とN-isogenousの関係

Nを正の整数としてをN次のモジュラー多項式とし、 楕円曲線 がそれぞれ不変量を持つとする。 この時、以下が成り立つ。 からへの写像がN-isogenusであるとき、である。 逆に、であるとき、からへの写像はN-isogenusである。 この定理は、有限体上の楕円曲線…

複素数体(C)上の同種写像(isogenies)

複数数体(C)上の楕円曲線はLattice(格子)によって決まります。 格子は、2つの複素数 の複素ベクトルによって作られるものです。 が格子ですが、無限個の頂点から成ります。 ガウス整数からなる格子と言えます。 45度傾いた格子と言えます。 格子の繰り返しの…

ワイエルシュトラスのペー関数(weierstrass p-function)の係数についての漸化式

ワイエルシュトラスのペー関数の係数についての漸化式の導出方法です。 から出発します。 なお、はkが奇数のとき0です。 微分します。 点がついている部分はzの1次以上の項を表します。 ここで、関数f(z)が格子に対する二重周期関数で、極を持たない場合は、…

モジュラー多項式の定義と係数の求め方

とします。これは ではありませんのでご注意ください。 例えば、N=2の時のの集合は、 となります。 以下の式を考えます。 N=2の場合は、 となります。 驚くべきことに、はの整数係数多項式で表せることが知られています。 N=2の場合は、 のように書けるとい…

楕円曲線のデルタの逆数のq展開の係数が整数であることの証明

楕円曲線で使われるの逆数のq展開の係数が整数であることの証明が素晴らしかったので、メモしておきます。 についてであることの証明。 ここで、 とおく。 は連続する3つの整数なので3の倍数、連続する2つの整数を含むので2の倍数でもある、したがって6の倍…

SL(2, Z)とモジュラー性

SL(2, Z)のちゃんとして説明はうまくできないので、高校数学の範囲内で特徴を説明したいと思います。 x, yの2次元平面を考えて、x, y, X, Yを整数とします。 線形変換を考えます。 ここでa, b , c, d も整数とします。 これは整数点P(x, y)から整数点Q(X, Y)…

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.riken.jp/sagemath/osx/intel/index.html http://ftp.yz.yamagata-u.ac.jp/pub/math/sage/os…

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

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

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

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

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

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

楕円曲線のn等倍点の多項式(division polynomial)

楕円曲線の点(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は素数のべき)上の楕円曲線とする。 この楕円曲線の位数すなわち、…

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

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

プライバシーポリシー

お問い合わせ

スポンサーリンク