Pebble Coding

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

ガロア群

体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関数の係数は以下のように計算できます。 ここでは低次の係数のみを求めてみます。 と置いてを求…

rust トレイトとジェネリクスと所有権

rustのトレイトは、Javaのインターフェースやswiftのプロトコルに相当します。 ジェネリクスは多くの言語にあるので、馴染みがあるでしょう。 rustのジェネリクスやはその他の言語のジェネリクスに絶対にない特徴を持ちます。 swiftのジェネリクスは、複数の…

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

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

rust + vim でビルドエラーを修正する

rust-lang/rust.vim をBundleでインストールする。これだけでした。 Bundle 'rust-lang/rust.vim' srcフォルダの下のソースファイルのうちのどれかをvimで開く。 :make buildを実行する。 :copenでエラーリストを表示する。参考: https://shinglyu.com/web/2…

rustのtraitで値バージョンと借用バージョンの両方の実装方法

rustの演算子オーバーロードをする際、値と借用の両方の実装を行う方法です。 次の構造体の掛け算を考えます。 #[derive(Debug, Clone, PartialEq, Eq, Default)] pub struct Unit { pub coef: BigInt, pub xpow: BigInt, pub ypow: BigInt, } 値の掛け算と…

rust のファイル分割

rust のソースファイル分割方法はC++やswiftとはかなり違って戸惑いますが、なんとか分割できたのでメモしておきます。 rustではファイル名イコールモジュール名と覚えましょう。 C++やswiftはファイル名にほとんど意味はありませんが、rustは超厳しいです。…

VisualStudio(C++)でメモリリークを検知する

VisualStudio(C++)でメモリリークを検知する方法です。コンソールアプリの場合はmain関数の先頭に以下を追加してデバッグ実行するだけです。 _CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );_CRTDBG_LEAK_CHECK_DF を指定することにより…

仮想通貨取引の手数料(fee)

仮想通貨取引の帳簿(ledger)をつけていたところBTCのウォレットや取引所の残高と帳簿上の残高(balance)が一致しませんでした。調べまわったところ、原因がほぼ分かったのでメモしておきます。 トランザクション手数料と取引所の手数料を計上していなかったの…

円分体で使われる式

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/LとE(C)は同型

複数数体(C)上の楕円曲線はLattice(格子)によって決まります。 格子は、2つの複素数 の複素ベクトルによって作られます。 が格子ですが、無限個の頂点から成ります。 格子Lという時、点の集まりのことを指しています。 ガウス整数からなる格子と言えます。 4…

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

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

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

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

j不変量(j invariant)

SL(2, Z)とモジュラー性 - Pebble Coding こちらの記事でであることをみましたが、 一般にであることが確かめられます。 , と定義されているので、 同じように、 楕円曲線のデルタの逆数のq展開の係数が整数であることの証明 - Pebble Coding こちらの記事に…

楕円曲線のデルタの逆数の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)…

ハッシュ関数の脆弱性

ハッシュ関数とは任意の数のビット列から固定長nのビット列を出力する関数です。 大きなサイズの入力を小さな出力にするわけですから、当然ながら衝突します。 衝突するのに出力のサイズに出来るだけ近い試行回数が必要になっていれば、十分な強度だと言えま…

群の準同型定理

群の準同型定理という有名な定理がある。 全単射な準同型写像を同型写像と呼ぶ。 群の準同型写像をfとおくと、f/Ker(f)をIm(f)に写す写像f'は同型写像である。 参考: http://www.math.tohoku.ac.jp/~kuroki/LaTeX/20080514_homorphism_theorem.pdf

素体の代数閉包(algebraic closure)

素体の閉包のイメージを掴んでおきます。 を考えます。この体は0, 1, 2の3つの元を持ちます。 加法の表はこうなります。 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 乗法の表はこうなります。 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 を考えます。この体は9つの元を持ちます。 9…

macOSにbrewでMacVimをインストールする

以下のコマンドを実行する。 $ brew install macvim /usr/local/Cellar/macvim/8.1-155/MacVim.app/ の位置に、GUIアプリケーションがインストールされる。 以下のコマンドによりリンクを生成する。 $ ln -s /usr/local/Cellar/macvim/8.1-155/MacVim.app/ /…

openssl1.1に追加されたed448

openssl1.1にはed25519だけでなくed448も追加された。 TLS1.3についてのWEB+DB Pressの記事見てたらed448がなんだかとても速いらしい。 素数の選び方に工夫が入っていて、乗算のモジュラ計算の2乗部分の計算が省略できるのが主要因のようだ。 だが、あまりに…

opensslでed25519の鍵を作ってみる

openssl 1.1.1にてed25519の鍵が作れるようになったようです。 www.openssl.org OpenSSL/genpkey - NORK's "HOW TO..." Wiki 略して「のうはうWiki」 macOS10.14.4のbrewではまだバージョンが1.0なので、1.1のバージョンのopensslをインストールします。 $ b…

SipHashの特徴

ハッシュ関数の一つにSipHashがあります。 128ビットのキーと任意長のデータを入力として、64ビットまたは128ビットを出力するハッシュ関数です。 SHA1は、攻撃者がX, SHA1(X)を知っている時、SHA1(X)=SHA1(Y)となるYを求めるのが難しいという特徴を持ちます…

暗号化 プライバシーを救った反乱者たち スティーブン・レビー

暗号化 プライバシーを救った反乱者たち作者: スティーブン・レビー,斉藤隆央出版社/メーカー: 紀伊國屋書店発売日: 2002/02/16メディア: 単行本購入: 4人 クリック: 14回この商品を含むブログ (26件) を見る ホイットフィールド・ディフィーとマーティン・…

プライバシーポリシー

お問い合わせ

スポンサーリンク