SECCON 2017 Very smooth writeup / RustでP-1法素因数分解器を実装した話

TSG Advent Calendar 2017 14日目です。遅れました。
adventar.org

こないだSECCON CTFがありました。
素因数分解するだけ問題が2つありました。
Ps and Qsは自明で、Very smoothも自明のはずでした。

まず意味ありげなタイトルなので、smoothでググるわけですが、smooth numberなんかという単語がヒットします。
どうやら小さい素数の積ででてきているような数のことのようです。

素因数分解アルゴリズムについて若干でも知っていれば、ここからP-1法とかのあたりを連想するのは簡単なはずです。
ってかさっきWikipedia見たら、powersmoothって書いてありました。

で、p-1素因数分解は前実装した気もするんですが、無くしたので、
今回はツールでも探すかって"linux p-1 factor"みたいにググったら、gmp-ecmというのがヒットして、これP-1法もできるらしいんですが、なんかできない。
競技終了後にちゃんと見てみると、たぶんp-1法の亜種の2-phase algorithmを採用しているせいかなぁという気がしてきました。今回の場合最大の素数が5で、大きな素数は1つもないので。（天下り的ですが）
競技中はmoratoriumくんに頼んだら一瞬で素因数分解してくれました。

gmp-ecmは役に立たないことが判明したので、まあ実装し直すかーという話です。
言語は最近勉強しているRustです。
github.com

num::bigintつよい。しかしsqrtやlogはないっぽい。

ついでにFermat法も実装しました。これでSECCON 2014の4096bit合成数も素因数分解できます。
a4lg.com

P-1法はgmp-ecmでいうところのB1パラメタがあって、これによって計算時間が変わりますが、ソース中で1000となっています。
これでもrelease buildにすれば10秒以内に終わります。debug buildだと無限に終わりません。（いいえ）（3分です）
fermat法側は

gmpy.next_prime(3<<512) * gmpy.next_prime((3<<512) + (1<<265))

の素因数分解が秒くらいで終わりますというくらいですね。

おわりです。アンパサンドがたくさんになると、C言語病のせいで、特に初心のRustだと不安になるんですが、やっぱり筋の悪いコードなんですかね。