For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(= pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N = p~rq while ed = 1 mod (p - 1)(q -1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.
展开▼
机译：对于 RSA，May 显示了计算 d 与因式分解 N（= pq） 的确定性多项式时间等价性。另一方面，Takagi 展示了 RSA 的变体，使得解密算法比标准 RSA 更快，其中 N = p~rq 而 ed = 1 mod （p - 1）（q -1）。在本文中，我们证明了确定性多项式时间等价性也适用于该变体。应用LLL算法的系数矩阵T不再是下三角形，因此我们开发了一种新技术来克服这个问题。
展开▼
