序文 §
毎年zer0ptsの皆さんが行っている高レベルな集団講義であるyoshi-campですが、例年なら指を咥えながら外側から眺めて終了後の残滓を必死で解読1していたのが、今年はTwitterで外部参加者を募集していたので、./Vespiaryから私とネコチャンが参加したいと伝えたところ、誠にありがたいことに快諾していただいたので参加してきました。というわけで恒例の参加記を書きます。
※ Typo、記号や添字の誤り、そもそも証明の誤りがありましたら、Twitter (@Xornet_Euphoria)へリプライかDM(誰でも送れます)を飛ばすか、このブログのリポジトリでIssueを立てたりプルリクを送ったりしてください。
読者が格子についての知識をある程度有している前提で書いてます。下記のサイトや書籍を読んでいると読みやすいと思います。
いつものupsolveのネタが尽きてきたので重めの問題(pbctf 2021 - Yet Another PRNG)をやろうとしたら、参考となっている論文が面白かったので紹介するついでにPoCを書きます
面白いアルゴリズムを探すために、最近教えてもらったLibrary Checkerを眺めていたら素数計数関数 $\pi(x)$を$x$までの素数を列挙するより速く計算する方法があることが判明したので紹介します。
LFSRの勉強をしていた際に、Berlekamp-Messeyのアルゴリズムが出てきたのでそれ関連でリードソロモン符号について調べてみたら、結構凄さを感じたアルゴリズムだったので紹介します。