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の証明の最後の部分で悩んでいたのですが、解決したのでメモしておきます。 https://eprint.iacr.org/2011/430.pdfこちらの説明でeasyだって書いてあり、数学者のeasyはちょっと計算をすればという意味なので、 ちょっとした計算って何だろう…
python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Codingこの記事ででののcardinarityが9であることを調べました。 にの根を加えて拡大体を作ります。 この拡大体上の点を調べてみます。 sage: K = GF(5) sage: R.<x> = K[] sage: L = K.exte</x>…
今まで ./sageでREPL環境を起動していましたが、jupyter notebookモードで起動することもできるようです。 ./sage -n jupyterテキストエディタ機能が使えるので便利です。
python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Codingこちらの記事で、 を調べたとき、cardinalityが9でした。 SageMathで同種写像を調べる方法があったので試してみます。 Isogenies — Sage Reference Manual v8.9: Plane curvesなお…
What is an isogeny of elliptic curves?こちらの記事に同種写像(isogeny)の例がのっています。 この写像のxの部分の分母、分子で次数が大きい方が2なので、 この同種写像の次数(degree)は2ということになります。 この変換式が本当に同種写像かどうかを確か…
Tateのisogeny thereom 以下の２つは同値である。 1) 有限体上の２つの楕円曲線が上同種写像である。 2) ２つの楕円曲線上の点の数は等しい。 https://www.math.auckland.ac.nz/~sgal018/iso.pdf
有限体の要素を作ります。 べき部分が3なので、3次の規約多項式の根を追加する必要があります。 を使います。 係数はなので、です。 計算の仕方はだいたい分かったと思いますので以後結果のみを書きます。 有限体の乗法群は元の数が26(=27-1)個あり全ての要…
整数係数の1次元n次多項式で最大次数の係数が1のもの の根となる複素数を代数的整数(algebraic integer)と呼ぶ。 代数的整数 - Wikipedia代数体Kの元のうち、代数的整数のみを抜き出した集合を整数環(ring of integers)と呼び、と表す。 有理数係数の1次元n…
上のの3等分点を考えます。 3等分点は9つあります。(一つは無限遠点です。) そのうちの２つをP, Qとします。 なのでPが曲線上にあることはすぐ確かめられます。 なので、Qも曲線上にあることが分かります。 ちなみに、この計算はmac book上のpython3で以下の…
体K上の楕円曲線 体Kの標数は2,3以外とする。 j不変量を と定義する。 この時、の変換によってjの値は同じになる。 なので不変量という名前がついている。 を格子とする。 ペー関数を と定義する。 が成り立つ。 である。 と定義すると、A, Bはの関数となる…
位数nの２つの巡回群の直積の群は位数nの部分群をn+1個持つ。 これ正しいのか一見分かりませんが、低次を計算してみると確かに正しいことが分かります。 部分群をで表します。 また巡回群なのでnは素数です。 n=2の場合。 確かに成り立っています。 n=3の場…
楕円曲線のlattice(格子)を考える。 lattice上では無限遠点z=0である。格子上の点は全て無限遠点である。 C/L=Eは無限個の点を持つが、そのうち3倍点を考える。 3倍点とは点zを３つ加算したものが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ではタプルが使えるので、同じア…
オイラーの五角数定理というのがあるようです。 j関数の計算に使われるようです。 証明はこちら。 https://faculty.math.illinois.edu/~reznick/2690367.pdf j関数の係数は以下のように計算できます。 ここでは低次の係数のみを求めてみます。 と置いてを求…
rustのトレイトは、Javaのインターフェースやswiftのプロトコルに相当します。 ジェネリクスは多くの言語にあるので、馴染みがあるでしょう。 rustのジェネリクスやはその他の言語のジェネリクスに絶対にない特徴を持ちます。 swiftのジェネリクスは、複数の…
schoofアルゴリズムをpythonで実装したらめちゃくちゃ遅かったのですが、楕円曲線の有理点の数の求め方 schoof アルゴリズムその４ - Pebble Codingrustで実装したところ、 a = -1 mod 3 a = -2 mod 5 の計算が、Debugビルドで90秒、Releaseビルドで7秒で計…
rust-lang/rust.vim をBundleでインストールする。これだけでした。 Bundle 'rust-lang/rust.vim' srcフォルダの下のソースファイルのうちのどれかをvimで開く。 :make buildを実行する。 :copenでエラーリストを表示する。参考: https://shinglyu.com/web/2…
rustの演算子オーバーロードをする際、値と借用の両方の実装を行う方法です。 次の構造体の掛け算を考えます。 #[derive(Debug, Clone, PartialEq, Eq, Default)] pub struct Unit { pub coef: BigInt, pub xpow: BigInt, pub ypow: BigInt, } 値の掛け算と…
rust のソースファイル分割方法はC++やswiftとはかなり違って戸惑いますが、なんとか分割できたのでメモしておきます。 rustではファイル名イコールモジュール名と覚えましょう。 C++やswiftはファイル名にほとんど意味はありませんが、rustは超厳しいです。…
VisualStudio(C++)でメモリリークを検知する方法です。コンソールアプリの場合はmain関数の先頭に以下を追加してデバッグ実行するだけです。 _CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );_CRTDBG_LEAK_CHECK_DF を指定することにより…
仮想通貨取引の帳簿(ledger)をつけていたところBTCのウォレットや取引所の残高と帳簿上の残高(balance)が一致しませんでした。調べまわったところ、原因がほぼ分かったのでメモしておきます。 トランザクション手数料と取引所の手数料を計上していなかったの…
nを整数として、とすると以下が成り立つ。 2番めの式で、とすると、左辺は0になるが、右辺の(x-1)は0ではない。 したがって 1番目の式が正しいかも確認してみます。 ここで、とを使えば係数が全て1になることが分かります。 となり、係数が全て１であること…
、 であるとき、f(x)を原始多項式(primitive polynomial)と呼ぶ。 係数の中に一つでも1または-1があれば、原始多項式です。 ガウスの補題(Gauss's Lemma) 2つの原始多項式の積は原始多項式である。 証明はこちら。 原始多項式とその積について | 高校数学の…
定理 複素数体上の多項式を考える。1)と2)は同値である。 1) n次多項式f(x)は重根を持つ。 2) n次多項式f(x)のある根に対しが成り立つ 証明 1) -> 2) と書ける。 微分して、 したがって、が成り立つ。 証明 2) -> 1) 対偶である、「重根を持たなければ、全て…
楕円曲線のn等倍点の多項式(division polynomial) - Pebble Codingここで、division polynomial を示しました。 体K上の楕円曲線上の点P(x, y)をn倍(nは整数)した点は、division polynomialを用いて、以下のように書けます。 ここで、n等分点、つまり、n倍し…
定理1 標数 (0でもよい)の任意の体Fを考える。 を素数としとする。 体F上の楕円曲線Eの 不変量を とする。 モジュラー多項式 の 個の根 は体Fの代数閉包 に入っている。 定理2 この は - isogenous 楕円曲線 E/C の 不変量である。 ここでCは等分点の群 の …
複数数体(C)上の楕円曲線はLattice(格子)によって決まります。 格子は、2つの複素数 の複素ベクトルによって作られます。 が格子ですが、無限個の頂点から成ります。 格子Lという時、点の集まりのことを指しています。 ガウス整数からなる格子と言えます。 4…
