Strategy of Relations Collection in Factoring RSA Modulus

摘要

In this paper, we propose a new strategy of relations collection in factoring RSA modulus. The strategy has absolute advantage at computation efficiency with a highly parallel structure, and the reports have higher probability of being relations, since the strategy only considers small and medium primes in factor base without large primes. Besides, it is worth noting that the proposed algorithm used in strategy, only involves a multiplication, which can speed up relations collection step. Furthermore, we propose an architecture for multiplier that is based on our algorithm. Due to the inherent characters of the algorithm, our proposed architecture can perform with less registers, which makes for VLSI area optimization. Additionally, the comparison results with the published achievements show that our strategy could be a good choice for relations collection in factoring RSA modulus.