Intel AVX-512IFMA52 命令セットによるモンゴメリ乗算の高速化 - Fixstars Tech Blog /proc/cpuinfo

このブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。 目次 導入 Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット モンゴメリ乗算を SIMD 実装する際のデータ配置 各種モンゴメリ乗算プログラムのパフォーマンス比較 総括 参考文献 謝辞 導入 Fixstars では暗号アルゴリズムの高速化を行っています。暗号アルゴリズムでは、素体 \(\mathbb{F}_p\) を扱うものが多くあり、その際、\(\mathbb{F}_p\) の上での乗算を実装する必要があります。 この乗算は非負整数の剰余付き乗算 \(z := x \cdot y \pmod p\) となります。素直にこの式に従って計算すると、 \(p\) で割った余りを求めるために除算・剰余算が使用されます。しかし除算・剰余算は、少な