アルゴリズム/データ構造
はじめに みなさん Go1.20リリースノート(現在進行中) は読みましたでしょうか? crypto関係のパッケージがmath/big.Intと距離を置きだしたりいろいろ面白そうな話題はあるんですが、なんといっても Wrapping multiple errors が一番気になりました! 関連pr…
はじめに どうも皆さんconvtoです。 最近UUIDとかをドカっと調べて色々比較するみたいな記事を書きました。 convto.hatenablog.com で、このとき実はつかってるOSSへのcontributionチャンスを発見していて、今回はそのパッチを上げたぞ(マージされるかはわか…
はじめに 分散システムやってるとどこからでも安全に採番できる強い衝突耐性をもったuuid的なほげほげidがほしくなります。 世にほげほげidはたくさんありますが、適当にREADMEとかよんでもみんな「これイケてるで!」「uuidとかより文字数すくないで!」「s…
はじめに これは RSA完全理解 Advent Calendar 2021 の16日目の記事です。 前回は多倍長整数の四則演算をやりました。乗法は だったので、少し効率の良いアルゴリズムを紹介します karatsuba法 桁数nの整数 があったとします。 これらをそれぞれ ずつに分割…
はじめに これは RSA完全理解 Advent Calendar の15日目の記事です。 RSAについてはひとしきり説明が終わったので、スクラッチで書くために巨大な数の四則演算について説明しようと思います。 四則演算さえできれば!いままでやったユークリッド互除法で逆元…
はじめに これは RSA完全理解 Advent Calendar の12日目の記事です RSAについて語る上で、素因数分解の困難さにふれないわけにはいかんやろ!ということで、素因数分解アルゴリズムの中でも簡単なp-1法について紹介します! (ほんとうは数体ふるい法が実用上…
はじめに これは RSA完全理解 Advent Calendar の8日目の記事です。 さて、同カレンダーの過去の記事にて ユークリッド互除法 ベズーの等式 について紹介したので、今回はユークリッド互除法をつかってベズーの等式の解を探索する方法について紹介します。 …
はじめに これは RSA完全理解 Advent Calendar の6日目の記事です RSAの話は一旦お休みして、今回からは剰余環の逆元をもとめるための前提知識をまとめていきたいと思います おおまかな流れとしては、 ユークリッド互除法の紹介 ベズーの等式と関連する定理…
リンクは以下 https://www.amazon.co.jp/dp/4065128447 会社の輪読会で読んだ 輪読会で読んだシリーズはほかに データ指向アプリケーションデザイン とかがあるけど、こいつも面白かった アルゴリズム関連の本はあまり読んだことがないのでかなりむずい部分…
bloom filter とは bloom filter とは、ざっくりいうと ある集合において、低コストにある要素が存在しないことがわかる データ構造です。 どのくらいコストが低いかというと、要素の登録や存在確認がともに O(k) です(kは利用するハッシュの数)。 集合の最…