A New Method of Factoring Large Integers

Abstract

In this paper, we reduce a large integer $N$ to an integer $N^\prime$ , which has a smaller number of decimal digits than $N$ . Then we find the greatest common divisor (gcd) of $N$ and $N^\prime$ to return a nontrivial factor of $N$ .

Introduction

The branch of mathematics that deals with integers is called number theory. Integers of particular interest are natural numbers which are given by the set $N=\{1,2,3,\ldots\}$ . The elements of this set are mainly divided into two parts: prime numbers and composite numbers. Prime numbers can only be divided by 1 and itself. They are given by the set $\{2,3,5,7,\ldots\}$ . On the other hand, composite numbers have more than two divisors. They are given by the set $\{4,6,8,9,\ldots\}$ . Normally a composite number is factored into smaller numbers $N=n_1 n_2$ , where the factors $n_1$ and $n_2$ may be again composite numbers. The goal is to express every positive number greater than 1 in terms of prime numbers, which is actually the statement of the fundamental theorem of arithmetic (FTA). According to FTA, one can write $N=p_1 p_2\ldots p_n$ , where the prime factors $p_i$ `s are not necessarily distinct. Although FTA says that prime factors are possible, it does not tell us how to obtain them. This is one of the hardest problems in mathematics and computer science to factor a large number.