PCG(permuted congruential generator)とは PCG自体の元ネタは PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation にあります。(この論文は疑似乱数の統計的性質の比較とかいろいろやってるデカい…

線形合同法とは 線形合同法(LCG; Linear Congruential Generator)は古くから知られている疑似乱数生成アルゴリズムで、背景の理論も簡単。 実行コストが低いため、暗号学的な安全性を求めないかつコンピューティングリソースに制約があるようなユースケース…

今回は小ネタ。みんな知りたいときあると思うからメモ どうやるの https://cs.opensource.google/go/go/+/refs/tags/go1.22.0:src/math/const.go;l=40 intSize = 32 << (^uint(0) >> 63) // 32 or 64 どゆこと ^uint(0) >> 63 は全bitたったuintを右に63シフ…

はじめに これは RSA完全理解 Advent Calendar 2021 の16日目の記事です。 前回は多倍長整数の四則演算をやりました。乗法は だったので、少し効率の良いアルゴリズムを紹介します karatsuba法 桁数nの整数 があったとします。 これらをそれぞれ ずつに分割…

はじめに これは RSA完全理解 Advent Calendar の15日目の記事です。 RSAについてはひとしきり説明が終わったので、スクラッチで書くために巨大な数の四則演算について説明しようと思います。 四則演算さえできれば！いままでやったユークリッド互除法で逆元…

はじめに エンコーディング周りを調べていたら、Goの場合は左辺のオペラントがintかuintかで処理が違うことがわかった。 ドキュメントにも明記されていて、算術シフトと論理シフトというやつを使い分けているらしい。 シフト演算を多用する処理は書いたこと…

はじめに エンコーディングとかをしらべていたら2の補数表現なる概念があることを知った 個人用メモとしてどういう仕組みなのかまとめておく ざっくりまとめ 2の補数表現とは、ある値の補数bitをその値の負数として扱おうというもの (正確には、0を正数とし…