Factorisation Related Question

  • Context: MHB 
  • Thread starter Thread starter PeterJ1
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the computational challenges of factorizing large numbers, specifically a number N with 1050 digits. It compares two calculations: directly factorizing N and sequentially multiplying primes from 2 until the product approximates N. The consensus is that sequential multiplication is significantly easier than direct factorization. Additionally, it is noted that factorizing a 232-digit number (RSA-768) took two years using hundreds of machines, indicating that numbers beyond 1024 bits present substantial difficulties for current factorization methods.

PREREQUISITES
  • Understanding of integer factorization algorithms
  • Familiarity with RSA encryption and its modulus sizes
  • Knowledge of computational complexity in number theory
  • Experience with distributed computing for large-scale calculations
NEXT STEPS
  • Research advanced integer factorization algorithms such as the General Number Field Sieve (GNFS)
  • Explore the implications of RSA modulus sizes on cryptographic security
  • Learn about distributed computing frameworks like Apache Hadoop for large number calculations
  • Investigate the limits of current factorization methods and potential future advancements
USEFUL FOR

This discussion is beneficial for cryptographers, mathematicians, and computer scientists interested in number theory, particularly those focused on the security implications of large number factorization in cryptography.

PeterJ1
Messages
17
Reaction score
0
A slightly odd layman's question about factoring large numbers and comparing two calculations.

Call N a number with 1050 digits.

1) Factorise N
2) Multiply the primes sequentially from 2 onwards until the product is as close as possible to N.

Would calculation 2 be significantly easier computationally than calculation 1?

How many digits would a number has to have before factorisation becomes a problem for our current methods?

Thanks
 
Mathematics news on Phys.org
Thanks Greg.

"... to factor a 232-digit number (RSA-768) utilizing hundreds of machines took two years and the researchers estimated that a 1024-bit RSA modulus would take about a thousand times as long.[1]"

This helps with the second question but not the first, which is my main question.
 
Doh! On reflection the answer to the second question is obvious. Consider it answered.
 

Similar threads

MHB Few more questions from 6th Grade text onward ,Please help ?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Proof of PSF quadratic factorising
  • · Replies 1 ·
Replies
1
Views
4K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K
MHB Sum of 2 Primes: 45 - (2 Digit Integer)?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Karatsuba multiplication implementation question
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Is this a proof of the Collatz Conjecture?
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad What is the probability that the product of the digits is odd?
  • · Replies 13 ·
Replies
13
Views
2K
MHB Powers function n^5+n^4=(n^5−n^3)(n−1)−(n−2)
  • · Replies 5 ·
Replies
5
Views
3K
MHB What is the last odd digit in the factorial sequence?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Equivalent Goldbach proof impossible question.
  • · Replies 2 ·
Replies
2
Views
2K