Introduction
In mathematics, factoring numbers into their set of prime values has been a major challenge, “. . . factoring numbers is a computationally difficult problem. It’s easy for smaller numbers, but once you start dealing with very large numbers, it can take computers, days, months, years, even centuries to solve .There is no easy shortcut for factoring numbers — it’s a trial and error process. “ [1].
In cryptography, researchers are “. . . mostly interested in the difficult RSA case, viz. n =pq with p; q primes of size approximately √n. This case is interesting, since if you can factor n then you can break the corresponding cryptosystem.” [2].
Apparently, there is a fear among researchers that “As long as there is no general polynomial time algorithm for factoring large numbers, RSA may remain secure.” [3] The fears, however, are persistent because. “Many security implementations in use are based on the difficulty for modern-day computers to perform large integer factorization.” [4].
Generally in factorization algorithms, one “. . . would have to try all of the primes that are less than . . . (the number to be factorized, and until all of the primes are found which) . . . when multiplied together . . .” produce the number to be factorized [1].
In cryptography and in other numerical applications, factorization — because of its difficulty — has been a major asset. The development of this algorithm will force cryptographers to work harder, while opening new horizons in numerical analysis, especially in data compression.
Review of Related Literature
Considering the abundance of applications that employ the factorization of large integers, especially in cryptography, there are similarly numerous factorization methods. The most commonly known are briefly described in Table One. “The methods . . . presented cannot, as yet, be analyzed formally . . .” [2 p14]
Table 1: Most Known Factorization Methods
A very thorough study on integer factorization algorithms concludes with the statement: “There are no known algorithms which can factor arbitrary large integers efficiently” [5]. With the factorization algorithm presented in this paper we may say that, now there is an algorithm that can factor arbitrary large integers efficiently.
The Developed Algorithm
The basic principle of the factorization algorithm, presented in this paper, is to treat the given integer, N, as the product of two numbers X and Y, where N=X*Y, or Y=N/X. The algorithm tracks the Y=X/N curve in unity steps, and stops when X*Y=N. The algorithm uses the square root of N as a starting point climbing upward along the curve.
Our aim in this climb is to reach either X*Y=N or X=1. In the first case, we stop and we evaluate each X and Y value separately to determine if either is a prime number. In the second case, we have successfully reached the end of the process having determined that Y is a prime number. Fig. 1 illustrates the general flowchart of the presented factorization algorithm.
In the climbing up on the Y=N/X curve, when the X&Y point falls in the X*YN area, X is decremented to get closer to the curve.
The presented algorithm is an iterative process using a step by step approach. Each iteration produces two factors, identified as X and Y. If X*Y=P, we stop. If X=1, then Y=N and N is a prime number. If X<>1, no conclusion is drawn, and the X and Y values are individually analyzed. It should be noted that, at the starting point of the iteration, the values of the X&Y pair are the integers most close to R=sqrt(N), the value of the square root of N, where XR.
Should R be an integer itself, then X=Y and X*Y=N, with N being a perfect square. In this case, R is being evaluated to determine if in itself is a prime number. From this initial point on, the value of X is steadily decremented and that of Y is steadily incremented. The X*Y product is continuously tested against the value of N, and when X*Y=N and the X value reaches unity, then we conclude that the corresponding Y is a prime number.
An Example
In this section, there is an example demonstrating the use of the above factorization algorithm and the logic behind it. Here, N is assumed to be 19. Table Two lists the coordinates of the points, as we climb around curve X*Y=N.
Fig. 2 shows the path of the X&Y pair ascending along the N=19=X*Y or Y=19/X curve, where the square root of N is R=4.35889…., identified as Point Zero. The starting point, or Point One, is the X&Y integral pair nearest to the X=Y=sqrt(N)=R point, where XR. Thus, in this case, the starting coordinates become XR or Y=5.
At Point One, P=X*Y=4*5=20. Because the point falls in the X*Y>N (right hand side) area, the next step is to decrement X creating Point Two. The zig-zag continues ending up in one of two options.. One is the case where N is a prime number, as in Fig. 1, where N=19. The other case is where product X*Y=N but X<>1, and we need to analyze X and Y individually.
If in the current step product X*Y is than N, in the following step the value of X is decremented. If in the current step product X*Y is less than N, in the following step the value of Y is incremented. When X*Y reaches N, the process stops. If X=1, as it is in this case, Y is a prime number. If X>1, N is the product of X and Y, and X and Y are individually assessed to determine their prime status.
Conclusion
The development of a simple and reliable algorithm for the factorization of any integer, as presented here, creates new research opportunities in numerical analysis, cryptography and in data compression and data representation. Factorization is the backbone of most cryptographic protocols. The availability of the presented factorization algorithm bases cryptography less on computing power, and more on cryptographic ingenuity.
Table 2: Steps leading to the determination that number
19 is a Prime Number
References
- Learn Cryptography.com http://learncryptography.com/prime-factorization/
- Yuval Film, Factorization Methods: Very Quick Overview by http://www.cs.toronto.edu/~yuvalf/Factorization.pdf
- Kevin Chu, RSA Cryptography: Factorization by http://wstein.org/edu/2010/414/projects/chu.pdf
- Travis L. Swaim, Quantum Computing and Cryptography Today: Preparing for a Breakdown http://essic.umd.edu/joom2/index.php/faculty-and- staff?layout=user&user_id=171&dir= JSROOT%2Ftswaim1&download_file=JSROOT%2Ftswaim1%2FQuantum+Computing+and+ Cryptography+Today.pdf
- Connelly Barnes (2004) Integer Factorization Algorithms http://connellybarnes.com/documents/factoring.pdf
APPENDIX : A Selected Bibliography on Numbers Factorization
