What is the best program for partially factoring large numbers?

  • Context: Graduate 
  • Thread starter Thread starter CRGreathouse
  • Start date Start date
  • Tags Tags
    Factorization Partial
Click For Summary
SUMMARY

The discussion centers on finding a suitable program for partially factoring large numbers, specifically those ranging from 500 to 35,000 bits. The Elliptic Curve Method (ECM) is identified as a promising approach, with a recommendation for the applet available at Alpertron. The user emphasizes the need for a solution that efficiently handles repeated factors and can process a large volume of numbers (approximately 9,000) without manual input. The preference is for a downloadable, fast application that is not Java-based.

PREREQUISITES
  • Understanding of the Elliptic Curve Method (ECM) for number factoring
  • Familiarity with large number representation (500 to 35,000 bits)
  • Knowledge of prime factorization and its challenges
  • Basic programming skills for potential source code modification
NEXT STEPS
  • Research alternative ECM implementations for large number factoring
  • Explore software options for batch processing large numbers
  • Investigate libraries for number theory in Python or C++
  • Learn about handling squareful numbers in factorization algorithms
USEFUL FOR

This discussion is beneficial for mathematicians, cryptographers, and software developers interested in number theory and efficient algorithms for factoring large integers.

CRGreathouse
Science Advisor
Homework Helper
Messages
2,832
Reaction score
0
(I'm not sure what forum to put this on: number theory because of factoring, programming because I want to automate it, computers because I don't intend to actually program anything myself, or general because it combines these.)

I'm looking for a program that I can use to partially factor numbers that are too large to fully factor (thousands of digits -- 500 to 35,000 bits). I'd like a 'high' chance of finding all factors below 15 digits or so.

A program that has trouble with repeated factors (squareful numbers) is inappropriate, as these numbers may well be divisible by the square of a large (> 1e9) prime. I don't know of any that have trouble with these other than prime powers, but I thought I'd mention it just in case.

So what's out there?
 
Mathematics news on Phys.org
Yes, I'm probably looking for some kind of ECM. But I want to check a large number of, uh, large numbers -- too many to enter by hand, too many even to check by hand (~9,000). Also, something downloadable and fast (not Java) would be nice. I suppose that applet does have source code I could modify, if it came to that... but I was hoping there was something else out there.
 

Similar threads

Undergrad Is dealing with large numbers as formula a thing? and how is it done?
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Prime factorization for large numbers
  • · Replies 6 ·
Replies
6
Views
12K
Undergrad Efficient Prime Factoring Method for Numbers Below the Square Root"
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad What's the logic behind partial fraction decomposition?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad What is the role of geometry and dimensional operations?
  • · Replies 3 ·
Replies
3
Views
2K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
MHB Odd/Even and Prime: Check 819877966 Numbers
  • · Replies 2 ·
Replies
2
Views
2K
Number of unique integer factors
  • · Replies 4 ·
Replies
4
Views
2K
Admissions What are my chances of getting into a competitive physics PhD program?
  • · Replies 7 ·
Replies
7
Views
3K
Graduate Finding the aproximate integer Sqrt of a large prime
  • · Replies 2 ·
Replies
2
Views
2K