SageMathのalarmが便利

この記事の内容は

ask.sagemath.org

を見て書かれました

---

プログラムを書いていると「とりあえず factor してみて、小さい素因数を持っているかどうか確かめる」ということがよくあります。Invalid Curve AttackをしたいのでPohlig-Hellmanに向いた「位数が小さい素因数に持つ楕円曲線を探す」みたいな場合です。

しかし、 factor （や discrete_log）はうまい値ならばすぐ終わりますが、そうでない場合は時間がかかってしまいます。そこでこれまでは https://github.com/pnpnpn/timeout-decorator を使っていたのですが、スレッドだとうまくいかないのでシグナルを使わないとだめだとか（逆だったかも）そもそもデコレーターなので処理を関数に切り出さないといけないとかがあって面倒でした。

調べたところによるとSageには alarm と cancel_alarm という関数があって、これが便利に使えます。たとえば位数に小さい素因数を含む楕円曲線を探してみます

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = int(-3 % p)
# b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

for b in range(1000):
    try:
        E = EllipticCurve(GF(p), [a,b])
        alarm(5)
        order = E.order()
        factors = factor(order, limit=100000)
        cancel_alarm()
    except (AlarmInterrupt, ArithmeticError):
        continue

    if prod([p**e for p, e in factors if p < 100000]) > 1000000000:
        print(b)
        quit()

上記の例から読み取れるように alarm は数値を引数に取って即座に処理を返しますが、バックグラウンドで動いていてそのn秒後に AlarmInterrupt 例外を投げます。それよりもさきにcancel_alarmが呼び出されるとアラームは投げられなくなります。

これがimport不要で使えて便利、というメモでした。