Paper 2018/325

Multi-power Post-quantum RSA

John M. Schanck

Abstract

Special purpose factoring algorithms have discouraged the adoption of multi-power RSA, even in a post-quantum setting. We revisit the known attacks and find that a general recommendation against repeated factors is unwarranted. We find that one-terabyte RSA keys of the form $n=p_1^2{p}_2^3{p}_3^5{p}_4^7\cdots p_i^{{\pi }_i}\cdots p_{20044}^{225287}$ are competitive with one-terabyte RSA keys of the form $n=p_1{p}_2{p}_3{p}_4\cdots p_i\cdots p_{2^{31}}$. Prime generation can be made to be a factor of 100000 times faster at a loss of at least $1$ but not more than $17$ bits of security against known attacks. The range depends on the relative cost of bit and qubit operations under the assumption that qubit operations cost $2^c$ bit operations for some constant $c$.