Recently, dedicated factoring devices have attracted much attention since they might be a threat for a current RSA-based cryptosystems. In some devices, the clockwise transposition routing is used as a key technique, however, because of the lack of theoretic proof of the termination, some additional circuits are required. In this paper, we analyze the packet exchanging rule for the clockwise transposition and propose some possible alternatives with keeping the farthest-first property. Although we have no theoretic proof of the termination, experimental results show practical availability in the clockwise transposition. We also propose an improvement on the routing algorithm for the relation finding step in the number field sieve method of factorization, which establishes two times speed-up.
['Tetsuya Izu', 'Noboru Kunihiro', 'Kazuo Ohta', 'Takeshi Shimoyama']
Analysis on the Clockwise Transposition Routing for Dedicated Factoring Devices