techmedia-think https://blog.hatena.ne.jp/techmedia-think/ Develop with pleasure! https://techmedia-think.hatenablog.com/ Ruby Cryptography 前回はR1CSを扱い、最後にGF(2)上では「制約1本 = ANDゲート1個、XORはタダ」になるところまで見た。ただしあれは制約の書き方の話で、証明系ではない。 今回はその先、GF(2)上のR1CSの充足性を実際に検査する側に進む。最初に立ちはだかるのは、体を小さくしたことの代償で、その解決に二進体のタワーを用いる。今回はそこまでをRubyで書いてみた。 GF(2)には元が2つしかない 多くの算術系の証明系では、「多項式の等式が成り立つ」ことを示す形に問題を変換する。ただし全部の点で確かめると点の数に比例する手間がかかるので、ランダムな1点だけ確かめて済ませる。これが成立するのは、2つの多項… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftechmedia-think.hatenablog.com%2Fentry%2F2026%2F08%2F22%2F172250" title="GF(2) R1CSのための二進体タワーをRubyで実装してみる - Develop with pleasure!" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2026-08-22 17:22:50 rich https://techmedia-think.hatenablog.com/entry/2026/08/22/172250 1.0 100%