iidaの日記： ROCA脆弱鍵検出アルゴリズム

ありきたりのROCA脆弱鍵検出アルゴリズムでは、小さい素数から割っていって65537の冪乗の剰余と比べるのだが、ハズレになる確率の高い素数から割っていけば、より速くハズレを見付けられることに気付き順序を変えてみたら、2倍ほど速くなった。
139、149、163、167では割り切れるばあいだけハズレなのだが、それらはやめて227、229、233、239で割れば誤報が数百分の1〜数千分の1になることも判明。
239のばあい0x108000008000048000000110000002000000888000801100040042で比べればよいので、93%くらいハネることができる。
PS
21-01-02
ハズレとアタリの間違いを1か所訂正