METHOD FOR LARGE INTEGER FACTORIZATION BASED ON THE RESIDUE NUMBER SYSTEM

Abstract

The paper investigates the problem of factoring large integers, which remains one of the fundamental challenges in modern number theory and public-key cryptography. An analysis of the classical Fermat factorization method is performed, and its computational bottlenecks associated with repeated square computations and exhaustive iteration are identified. To overcome these limitations, a modified version of the Fermat method based on a recurrent computation of the difference of squares is proposed. The proposed modification eliminates repeated exponentiation operations by replacing them with incremental arithmetic operations, thereby creating the mathematical foundation for the application of residue number systems.

Based on the proposed modification, two novel factorization algorithms are developed. The first algorithm employs a key-folding mechanism in the Residue Number System, where sets of admissible quadratic residues are generated for individual moduli and subsequently combined according to the Chinese Remainder Theorem. This approach provides a multistage algebraic filtering procedure that substantially reduces the number of candidate values requiring verification in the positional number system. The second algorithm introduces an offset-lattice approach, in which the search process is transferred from the value space to the iteration-index space. By constructing periodic sets of admissible offsets for groups of moduli, the algorithm performs lattice-based filtering and evaluates only those iterations satisfying all modular constraints, significantly decreasing the number of expensive perfect-square tests.

The computational complexity of the proposed algorithms is analyzed and compared with that of the classical Fermat method. Theoretical analysis demonstrates that both algorithms reduce the effective search space through modular filtering, while the offset-lattice algorithm additionally decreases the number of examined iterations by exploiting the periodic structure of admissible offsets. Owing to the independence of computations for different moduli, both algorithms naturally support parallel implementation, making them suitable for execution on multicore and distributed computing platforms.

Experimental studies performed on integers of various sizes confirm the effectiveness of the proposed approaches. Compared with the classical Fermat method, the developed algorithms reduce the number of candidate checks and improve computational efficiency while preserving the correctness of factorization. The obtained results demonstrate that residue number systems, combined with key-folding and offset-lattice techniques, provide a promising direction for accelerating the factorization of medium-sized integers and may serve as a basis for further research on high-performance modular factorization algorithms.