Z_nにおける離散力学系について

Abstract

In the RSA cryptosystem, the factorization of a composite integer n, which is the product of two primes, is essential for the decryption of the ciphertext. And the factorization of the integer is very difficult when the integer becomes so large. Therefore, many methods for factorization are developed in recent years. Among them, Pollard ρ method is sometimes very usefull, although there are some cases the method does not work so well. In this paper, we consider the dynamical systems of the mapping in Z_n and, by investigating the cycles of this mapping, we give a theorem on factorization along the same line of Pollard's.