Pebble Coding

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

モジュラー多項式の定義

とします。これは ではありませんのでご注意ください。 例えば、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件) を見る ホイットフィールド・ディフィーとマーティン・…

ドイッチのゲート

量子コンピュータの原理を調べているが、結局のところ、使っている数学は、線形代数と離散フーリエ変換くらいである。 この記事では、ドイッチのゲートの計算を確かめる。 なお、基礎的な量子論理ゲートである、アダマールゲート、制御ユニタリゲート、制御N…

let's encryptの証明書更新が失敗するようなった

/usr/bin/certbot renew このコマンドが以下のエラーで動きません。 Saving debug log to /var/log/letsencrypt/letsencrypt.log ------------------------------------------------------------------------------- Processing /etc/letsencrypt/renewal/on…

Barrett modular reduction アルゴリズム

モジュラ計算を効率よく行うアルゴリズムの一つに Barrett modular reduction がある。 これを解説してみる。 xとmが与えられたとき、 を計算したい。 であるbを選び、mをb進数で以下のように表現するとkが定まる。 ここで と仮定する。このアルゴリズムでは…

XVim2のTIPS

XVim2というXcodeプラグインのメンテをやっている。 antmdさんによってXcode9に対応され、そこそこ動くようにはなったが、 バージョンアップのたびにどこか壊れるので、PullReqを投げていたら、コミット権を渡された。 XVim2はXcodeでvimキーバインドを使う…

rust croaring::Bitmap とは

rust のクレートの一つに croaring::Bitmap というものがある。 Bitmapとは、任意のサイズで1と0の値を持たせたデータ構造のことである。 例えば、u64 の型は 64のサイズのBitmap型であるといえるが、任意のサイズで使えるようにしたものがBitmapである。 こ…

rust の Hash,Hasher トレイト

swift には多数のprotocolが定義されており、これを理解し有効に活用することで、読みやすいコードを書くことができる。 rustにも同じように多数のtraitが定義されている。swiftに比べて、かなり多くのtraitが定義されているが、 マイナー言語ゆえに、日本語…

rust で 正の奇数を小さい方から返すイテレーター

rust で正の奇数を小さい方から返すイテレーターを作ります。 iterator トレイトの定義は以下の通りです。 trait Iterator { type Item; fn next(&mut self) -> Option<Self::Item>; } https://doc.rust-lang.org/std/iter/trait.Iterator.html ドキュメンテーションでは</self::item>…

grin の Proof Of Work で使われている Cuckoo Cycle / Cuckoo Hashing とは

Cuckoo Hashing とは、ハッシュテーブルの構造の一種である。 カッコウ(Cuckoo)には他の種類の鳥の巣に卵を置き、元々あったその鳥の卵は破棄するという習性があるが、 命名はそこから来ている。 まず、一般的なハッシュテーブルの作り方を考える。 8個の要…

ECDSA署名とECSchnorr署名の概略メモ

ECDSA署名とECSchnorr署名の概略メモです。 群や体の演算など、些細な部分は省略し、核となるロジックだけを記載しています。 楕円曲線上の点は大文字、スカラー値は小文字で表現します。 点Aのx,y座標はと表現します。 ECDSA署名 <共有情報> G:ベースポイン…

grin のトランザクションフローのメモ

こちらにgrinのトランザクションフローについての図が上がっていたので、テキストに落としておく。 まだソースを追っているところだったが、このフロー図で理解が進みやすくなる気がする。 この図はどこから入手したんだろ。 MimblewimbleとGrinのトランザク…

rust ?(question mark)演算子

rustでの?演算子はResultの処理を簡略化した機能を持つ。 戻り値としてResultを持つ関数内で利用することができ、 Resultを生成する式の後ろにつけることができる。 ?をつけた場合は式の結果がSuccessだった場合はその値をunwrapして処理を継続する。 Error…

grin の外部依存 crate

grin はかなりの数の外部 crate を利用しています。 セキュリティ上重要な部分は当然自前実装かつセキュリティ監査をしたらしいです。 rust は脆弱性が入り込みにくいとはいえ、何らかの不備が見つからないとも限らないので、まさに実験的プロジェクトです。…

rust の trait

rust の trait は大雑把に言って、swift の protocol に相当する。 以下サンプルを見てみよう。 fn main() { let mut bicycle = Bicycle { pos: 0 }; bicycle.forward(); } struct Bicycle { pub pos: i32 } trait Movable { fn forward(&mut self); } // Bi…

rust をios用にビルドする

ios の target を追加してからビルドします。 $ rustup target add x86_64-apple-ios $ cargo build --target x86_64-apple-ios cargo.toml [lib] name = "blake2rustios" crate-type = ["staticlib"] これでstatic libraryが生成されるようです。 他、細か…

secp256k1_zkpライブラリの関数

secp256k1_zkpライブラリの関数概要のメモです。 スカラー値は小文字、楕円曲線上の点は大文字で表現します。 未調査の部分は?としてあります。 /// seedを指定してハッシュ関数を通した点を返す // 同じseedを指定した場合、いつも同じ点が返されることが保…

secp256k1 ライブラリの関数

secp256k1のC89実装のライブラリの関数のメモです。 GitHub - bitcoin-core/secp256k1: Optimized C library for EC operations on curve secp256k1 秘密鍵はスカラー値であり、sと表現することにします。 sは1以上secp256k1の群位数N未満である必要がありま…

MimbleWimbleプロトコル情報リンク

MimbleWinbleペーパー 2016年 http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble.txt Block Stream社のAndrew Poelstra氏によるMimbleWimble解説の日本語訳 btcnews.jp GrinのMimbleWinble概要解説 grin/intro_JP.md at master · mimblewimble/grin · G…

macOS にrust(stable版, nightly版)をインストールする

現在の最新バージョンは1.32です。 stableな機能のみしか使わない場合は、brew でインストールしてもよいです。 $ brew install rust nightly の機能を使う場合は rustup を使います。 まずは、brew でインストールしたrustをアンインストールします。 $ bre…

プライバシーポリシー

お問い合わせ

スポンサーリンク