Integer Factorization Tool

[fosuwxb]

Integer Factorization Tool
We construct a data set that can compute a certain number of integers to compute the greatest common divisor of the integers to be factored. We also designed a parallel processing tool to search the dataset
Features
Multi-process parallel computation for faster factorization
Intelligent Monte Carlo-style search algorithm
Checkpoint capability to resume interrupted calculations
Auto-recovery from errors
Progress tracking and detailed logging
Support for various output formats


We post our source codes here for interesters to vent.

---

Features
- Integer factorization based on geometric methods
- Efficient search space calculation and optimization
- Multi-process parallel processing for improved performance
- Support for large integers (using gmpy2 library)
- Real-time progress tracking and result display
- Detailed logging

The toolset consists of two main components:
- Point Generator: Generates optimal starting points for the search algorithm
- Factor Finder: Uses the geometric search method to find integer factors

We construct a specialized search space in which certain integers can be calculated to compute the greatest common divisor with the integer to be factorized. We also implement a dynamic parallel processing system to efficiently search this space. The algorithm is optimized for modern multi-core CPUs.

We provide the source code for researchers and enthusiasts interested in large integer factorization.

---

Requirements

• Python 3.6+
  
• gmpy2 library for large integer calculations
  
• multiprocessing support (built into Python)
  

Installation
Install the required dependency:

pip install gmpy2


Usage
The tool consists of two main components:

1. Point Generator

  point_generator.py (Size: 8.61 KB / Downloads: 1)
This generates optimal starting points for the factor search algorithm.

Basic usage:

python point_generator.py

The generator will:
- Calculate appropriate search space parameters
- Generate random points within the search space
- Save results to points.txt file

2. Factor Finder

  factor_finder.py (Size: 28.66 KB / Downloads: 1)
Uses geometric methods to search for factors of large integers.

Basic usage:

python factor_finder.py


When run, the program will prompt for four parameters:

Please input parameters (space separated): N g x y


Where:

• N: The large integer to factorize
  
• g: Generator value (recommended: 18-30)
  
• x, y: Starting point coordinates (can be taken from point_generator.py output)
  

Examples

• Basic Factorization:
  
  python factor_finder.py
  > Please input parameters (space separated): 10909343 18 3018551 49061001
  
  
• Using Different Starting Point:
  
  python factor_finder.py
  > Please input parameters (space separated): 10909343 24 2754321 38625122
  
  

How It Works
The algorithm uses geometric search methods to find factors of large integers:

1. Search Space Construction: Defines a two-dimensional search space containing potential factors
   
2. Point-Slope Generation: Generates search lines using given points and directions
   
3. Space Division: Divides the search space into multiple main segments and sub-segments
   
4. Parallel Computation: Multiple processes simultaneously calculate ω function values in different regions
   
5. GCD Calculation: Uses the greatest common divisor algorithm to find potential factors
   

Performance Tips

• Adjust the g value (18-30) to optimize search efficiency
  
• The number of main segments (m) should match your CPU core count
  
• For memory-constrained systems, reduce the batch size (default: 10,000)
  
• Different starting points can significantly affect factorization speed
  
• Using the gmpy2 library provides substantial performance improvements
  

Troubleshooting

1. Memory Issues: Reduce batch size in the code (BATCH_SIZE variable)
   
2. Performance Problems: Adjust number of main segments (m) to match CPU cores
   
3. Long Calculations: Try different starting points or adjust g value
   
4. Crashes: Ensure you have the latest version of gmpy2 installed
   

Advanced Features
The system includes several advanced features:

• Dynamic load balancing for optimal multi-process performance
  
• Intelligent segment distribution based on workload estimation
  
• Optimized GCD calculations using gmpy2 library
  
• Real-time progress tracking across all worker processes
  
  

For more details, please refer to the included documentation or contact the development team.