Pebble Coding

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

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

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

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

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

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

ラグランジュの定理 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を位数にもつ部分群は必ず存在する。 例えば位数)の有限群がある場合、 位数の部分群は存在するということである。

投資関連本

バフェットの銘柄選択術 バフェットの義娘、メアリーバフェットによる、ウォーレンバフェットの株投資術について具体的に記した書籍です。 億万長者をめざすバフェットの銘柄選択術作者: メアリー・バフェット,デビッド・クラーク,井手正介,中熊靖和出版社/…

仮想通貨取引の基本知識

仮想通貨取引について最低限の知っておくべき基本的な知識についての解説を行おうと思います。 取引所と販売所とFX 仮想通貨を売ったり買ったりする方法として、取引所と販売所とFXというサービスを使います。 ここでは例としてBitFlyerという会社を用います…

仮想通貨取引で利益を出すには?

仮想通貨取引で利益を出す方法はたくさんありますが、メジャーな方法のみを挙げてみます。利益を出すには、通貨を安く買って高く売る。これが基本になりますが、いくつものバリエーションがあります。 裁量トレード スキャルピング 人が自分の判断とタイミン…

おすすめの金融系映画3本

おすすめの金融系映画3本を紹介します。 いずれも、2008年のリーマンショックを題材にしたものです。 マネー・ショート華麗なる大逆転 サブプライムローンの暴落の予兆にいち早く気づき、相場の暴落によって、利益を上げることに成功する人々とそれを取り巻…

仮想通貨投資と納税

仮想通貨投資を行う場合、納税をどうしたらよいのか気になると思います。 去年は仮想通貨で利益が出たため、初めて確定申告をしました。 情報が少なく、試行錯誤して、だいぶ苦しみましたので、ポイントをメモしておきます。 今年確定申告する方の参考になれ…

ApplePayは ApplePayマークがない店舗でも使える

ApplePayをお店で支払いに使う場合、非接触型ICカード読み取り機が置いてあり、ApplePayマークが表示されていれば必ず利用できます。 ですが、実はApplePayマークがなくても利用は出来ます。 ApplePayで支払いをする場合、Suica、iD、QUICPayの3つの選択肢が…

Blake2b を swift で実装してみた

Blake2 というハッシュ関数があります。 MD5,SHA-1などといういわゆるハッシュ関数の仲間です。 特徴としては、MD5,SHA-1,SHA-2,SHA-3よりも計算が高速で、SHA-3と同程度のセキュリティ(衝突耐性など)があるようです。 MD5などとは異なり、seed(key)を指定で…

肩こりと腰痛とプログラマー

一日中座りっぱなしのプログラマーにとって、肩こりと腰痛は職業病です。 20代の頃はそれほど心配ないですが、30代に入ったあたりからだんだんと対策を考える必要が出てきます。 座っている時間が長いほど病気になる確率が高くなるとも言われます。 対策につ…

仮想通貨、ブロックチェーンとは何か

2018年は仮想通貨、ブロックチェーンが特に日本で世間一般に認知された年でした。 仮想通貨、ブロックチェーンとは何なのか、今後どうなってゆくのかについてまとめておきたいと思います。 仮想通貨 2008年11月にサトシナカモトという匿名の人物が論文を書き…

AdSenseのブログ審査に2回目で通過しました

Google AdSenseの1回目の審査で落ちたので、日記系(技術系だけど一つの記事は短め)はダメなのかなと思ったら、2回目の審査で通りました。 1回目の審査では、無料版はてなブログで書きためたサイトをグローバルドメインに置き換えて審査に出しました。 審…

go言語実装のed25519のベンチマークを測定してみる

go言語によるed25519実装は2種類あるようですが、こちらにあるもので調べてみました。 GitHub - Bytom/bytom: Official Go implementation of the Bytom protocol go言語では単体テストにベンチマーク機能が組み込まれており、簡単にベンチマークが取れるよ…

C++/ObjC/swift コーディング規約

私が考えるC++/ObjC/swift についてのコーディング規約です。 基本的にコーディング規約はプロジェクトの生産性を最大化するのが目的であり、厳しすぎず、ゆる過ぎないものにするべきです。 以下、箇条書きにしていきます。 守るべき規約 定数は先頭に k の…

mod pでの平方剰余を計算する(p mod 8 = 5) その2

www.pebblewind.com こちらの記事で、平方剰余を計算しましたが、ed25519 においては、aは u/v という形になっています。 u,vの計算量は少ないので、計算効率をあげるため、u,vを用いた掛け算になるように変形します。 (フェルマーの小定理) (余分な項が8の…

go 言語 でed25519ライブラリを使う

go の標準ライブラリにはed25519は含まれない($ go list std | grep cryptoで確認できます。)ため、 以下のライブラリを使います。 github.com 以下のコマンドでインストールします。 $ go get -u golang.org/x/crypto/ed25519 a.goというファイル名で以下を…

はてなブログをproにして独自ドメインに変更する

はてなブログの無料版はサブドメインのため、GoogleAdsenseを導入することができません。 そのため、はてなブログをproにして独自ドメインに変更した時の手順です。 まず、元のURLはこのようになっています。 http://pebble8888.hatenablog.com hatenablog.c…

twisted edwards curve でのaffine加算公式とprojective加算公式

Twisted Edward Curveでのコンピュータでの計算の最適化手法はいくつかありますが、 この記事では、projective座標系を使って、わり算の数をへらし計算量を押さえる手法を紹介します。 twisted edwards curve のaffine座標での加算公式その1は以下です。 式…

ed25519におけるcofactor=8

こちらの記事 ed25519のpython実装を紐解く その2 暗号編キーペア生成からベリファイまで - Pebble Coding で、ed25519の署名のロジックを検証しました。 8の倍数を使う意味が分かった気がしたので、それについて書きます。 結論からいうと、small subgroup…

プライバシーポリシー

お問い合わせ

スポンサーリンク