Pebble Coding

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

数学

数論的約数関数(number theoretic divisor function)

数論的約数関数に対して成り立つ恒等式を証明します。 と定義します。 自然数nに対してその約数dについて和をとります。 例: 次の恒等式が成り立ちます。 証明: LHSと比較するにはqのべきが等しいものをまとめる必要があります。 同じべきとなる ij = n は n…

ある曲線のグラフ

このグラフは楕円曲線を別の変数でパラメトライズした曲線です。 つまり水平線と1点または3点で交わることが分かります。

SEAアルゴリズムで使う漸化式を導く

Elliptic Curves in Cryptography の VII.23の等式から、VII.24の漸化式を導く計算 証明すべき等式は以下です。 ここからVII.24が得られます。 使う材料は以下です。 (式A) 最初の等式の両辺のwの0乗からd乗までの多項式を計算し、係数を等しいと置くことが…

Doud's method

楕円曲線を満たすxを表す式の一つにDoud's methodがあります。 これを使い、モジュラー多項式の次数を下げた多項式を得るSEA法のロジックのうちの一つを計算してみます。 ぺー関数を以下のように表すのがDoud's methodです。 頭についている定数は以後の計算…

nが素数の時に成り立つ1のn乗根に関する等式

nが素数の時に成り立つ1のn乗根に関する等式 を証明します。 以下の事実を使います。 (式A) (式B) n is prime (式A)の右辺をzの同じ次数のべきでまとめると、の係数は0なので、 以下が成り立ちます。 pick k different element from 次に から一つの要素を除…

楕円曲線のsupersingular

標数pの楕円曲線Eがp等倍点を無限遠点しか持たないとき、その楕円曲線をsupersingularであると呼ぶ。 定理1 qを奇数でであるとし、とするとき、 はsupersingularである。 定理2 完全体上の標数pのsupersingularな楕円曲線はj-invariantが内にある。 (J. H. S…

等倍点とn乗根

定理1 n等倍点がE(K)に全て含まれるなら、n乗根は体Kに含まれる。 この定理から以下が言える。定理2 Eを(有理数体)上の楕円曲線とするとき、n=3以上のn等倍点でに含まれないものが存在する。 定理1は、体上のEを考えるとき(pは素数)、n等倍点がE(K)に含まれ…

数学洋書におけるif and only if

数学洋書で使われるif and only if の使い方です。 定理 a, bを実数とする。 方程式が2つの異なる実数解をもつ場合、 が成り立つ。かつ成り立つのはその時のみである。 これを英語で書くと次のようになります。 Theorem Let a and b be real numbers. The e…

モジュラー形式その4

j関数は重さ0のモジュラーです。つまり、 zで微分します。 ここで、 これを使うと、 これは、 が重さ2のモジュラーであることを意味します。 jの微分がモジュラーになるというのは、Math Overflowという数学専用質問サイトで発見しました。 モジュラー形式そ…

モジュラー形式その3

fを複素上半面の有理関数(meromorphic function)とする。 が全ての について成り立つとき、fを重さ(weight)の弱モジュラー(weakly modular)と呼ぶ。 と定義する。 kが負の値のときは発散するので考えない。 kが奇数のときは右辺は0になるので考えない。 k=2…

モジュラー形式 その2

証明に使う数学公式のメモ。 であるとき、両辺のlogを取り、 微分して、 logを取り、 微分して、 で左辺を書き換えると、 ここで和の順序を変えていないことに注意。

モジュラー形式(modular forms) その1

j関数の定理を証明するのにmodular formsの知識が必要なので、勉強し始めました。 とりあえず、教科書が届くまではネットのPDFで勉強します。 一般線型群のモジュラー形式 とし、 として、 と定義する。 というのは複素数から実数を取り除いた集合という意味…

F_p上の楕円曲線のオーダーをrustでbrute-force(力任せ)に計算する

F_p上の楕円曲線のオーダーをrustでbrute-force(力任せ)に計算してみました。 以前 pythonで実装しましたがだいぶ速くなっています。 GitHub - pebble8888/ellipticcurve F_5, y^2 = x^3 + x + 1, order:9, j:2 F_7, y^2 = x^3 + x + 1, order:5, j:1 order …

Velu's Formula

Velu's Formulaの証明の最後の部分で悩んでいたのですが、解決したのでメモしておきます。 https://eprint.iacr.org/2011/430.pdfこちらの説明でeasyだって書いてあり、数学者のeasyはちょっと計算をすればという意味なので、 ちょっとした計算って何だろう…

拡大体F_25での有理点

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Codingこの記事ででののcardinarityが9であることを調べました。 にの根を加えて拡大体を作ります。 この拡大体上の点を調べてみます。 sage: K = GF(5) sage: R.<x> = K[] sage: L = K.exte</x>…

sagemath をjupyter notebookモードで起動する

今まで ./sageでREPL環境を起動していましたが、jupyter notebookモードで起動することもできるようです。 ./sage -n jupyterテキストエディタ機能が使えるので便利です。

SageMathでisogenyを調べる

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Codingこちらの記事で、 を調べたとき、cardinalityが9でした。 SageMathで同種写像を調べる方法があったので試してみます。 Isogenies — Sage Reference Manual v8.8: Plane curvesなお…

同種写像の例

What is an isogeny of elliptic curves?こちらの記事に同種写像(isogeny)の例がのっています。 この写像のxの部分の分母、分子で次数が大きい方が2なので、 この同種写像の次数(degree)は2ということになります。 この変換式が本当に同種写像かどうかを確か…

Tate(テイト)の同種定理(isogeny theorem)

Tateのisogeny thereom 以下の2つは同値である。 1) 有限体上の2つの楕円曲線が上同種写像である。 2) 2つの楕円曲線上の点の数は等しい。 https://www.math.auckland.ac.nz/~sgal018/iso.pdf

有限体F27の元

有限体の要素を作ります。 べき部分が3なので、3次の規約多項式の根を追加する必要があります。 を使います。 係数はなので、です。 計算の仕方はだいたい分かったと思いますので以後結果のみを書きます。 有限体の乗法群は元の数が26(=27-1)個あり全ての要…

代数的整数と代数的数

整数係数の1次元n次多項式で最大次数の係数が1のもの の根となる複素数を代数的整数(algebraic integer)と呼ぶ。 代数的整数 - Wikipedia代数体Kの元のうち、代数的整数のみを抜き出した集合を整数環(ring of integers)と呼び、と表す。 有理数係数の1次元n…

有限体の3等分点の例

上のの3等分点を考えます。 3等分点は9つあります。(一つは無限遠点です。) そのうちの2つをP, Qとします。 なのでPが曲線上にあることはすぐ確かめられます。 なので、Qも曲線上にあることが分かります。 ちなみに、この計算はmac book上のpython3で以下の…

位数nの2つの巡回群の直積の群は位数nの部分群をn+1個持つ

位数nの2つの巡回群の直積の群は位数nの部分群をn+1個持つ。 これ正しいのか一見分かりませんが、低次を計算してみると確かに正しいことが分かります。 部分群をで表します。 また巡回群なのでnは素数です。 n=2の場合。 確かに成り立っています。 n=3の場…

dual isogeny

楕円曲線のlattice(格子)を考える。 lattice上では無限遠点z=0である。格子上の点は全て無限遠点である。 C/L=Eは無限個の点を持つが、そのうち3倍点を考える。 3倍点とは点zを3つ加算したものが0になる点つまり、z+z+z=3z=0となる点のことである。 この点…

ガロア群

体Lの自己同型のうち同型群 を考える。 体Lを体Fの有限次拡大とする。 体Fの全ての要素を変更しない拡大体LからLへの自己同型群の全てを要素とし、 演算をこの群の合成としてガロア群 Gal(L/F)と定義する。 は自己同型群 命題1. Gal(L/F)は合成に関して群を…

群、環、体、正規拡大、分離拡大

群の定義 集合Gから任意の要素a, bを取り出してそれに対してGの要素cを割り当てる操作(写像ともいう)を c = f(a, b) と表す。 A) 結合律、B) 単位元 C) 逆元 が成り立つとき、これを群と呼ぶ。 A) 結合律 a, b, cを集合から取り出したとき、 f(a, f(b, c)) =…

拡張ユークリッドの互除法

pythonの再帰で実装したもの import sys def egcd(a, b): """return (g, x, y) such that a*x + b*y = g = gcd(a, b)""" if a == 0: return (b, 0, 1) else: g, x, y = egcd(b % a, a) return (g, y - (b // a) * x, x) rustではタプルが使えるので、同じア…

オイラーの五角数定理(Euler's Pentagonal Number Theory)とj関数の係数の計算

オイラーの五角数定理というのがあるようです。 j関数の計算に使われるようです。 証明はこちら。 https://faculty.math.illinois.edu/~reznick/2690367.pdf j関数の係数は以下のように計算できます。 ここでは低次の係数のみを求めてみます。 と置いてを求…

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

schoofアルゴリズムをpythonで実装したらめちゃくちゃ遅かったのですが、楕円曲線の有理点の数の求め方 schoof アルゴリズムその4 - Pebble Codingrustで実装したところ、 a = -1 mod 3 a = -2 mod 5 の計算が、Debugビルドで90秒、Releaseビルドで7秒で計…

円分体で使われる式

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

プライバシーポリシー

お問い合わせ

スポンサーリンク