Is There a Formula for Prime Number Factorization?

  • Thread starter Thread starter MathJakob
  • Start date Start date
  • Tags Tags
    Formula
Click For Summary
Prime number factorization remains a complex challenge, as no efficient formula exists for factoring large integers into their prime components. Current algorithms can factor numbers, but they are not fast, particularly for products of two large primes, which are commonly used in cryptography. It is generally easier to determine if a number is prime than to perform a full factorization. The discussion highlights the confusion around the terminology of "prime number factorization" versus general integer factorization. Overall, while methods exist, they rely heavily on brute force for larger numbers.
MathJakob
Messages
161
Reaction score
5
I've been looking into prime number factorisation and was wondering does a formula actually exist or is it thought to be impossible to factor primes using a formula and they need to be factored using brute force?
[/PLAIN]
RSA Algorithm
 
Last edited by a moderator:
Mathematics news on Phys.org
Maybe the OP is talking about taking an arbitrarily large number N and finding all of its prime factors. I think the terminology 'prime number factorisation' is somewhat confusing.

For instance, 12 = 2*2*3
 
  • Like
Likes 1 person
Yes that is what I'm talking about, sorry for the confusion

"The most difficult integers to factor in practice using existing algorithms are those that are products of two large primes of similar size, and for this reason these are the integers used in cryptographic applications."

http://en.wikipedia.org/wiki/Integer_factorization
 
Yes, algorithms for factoring numbers into primes exist. But they're not very fast. Currently, it is much easier (=faster) to check if something is prime or not than to actually find a primal decomposition.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

MHB Few more questions from 6th Grade text onward ,Please help ?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Average of prime factors growth
  • · Replies 12 ·
Replies
12
Views
2K
Number of Primes between two integers
  • · Replies 3 ·
Replies
3
Views
2K
What Is a Composite Number With No Co-Prime Factors?
  • · Replies 2 ·
Replies
2
Views
2K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
Which Mathematicians Pioneered Prime Numbers for Cryptography?
  • · Replies 2 ·
Replies
2
Views
3K
Q-Day: When Quantum Computers can Factor ultra-large numbers in a few...
  • · Replies 43 ·
2
Replies
43
Views
6K
Undergrad Is dealing with large numbers as formula a thing? and how is it done?
  • · Replies 3 ·
Replies
3
Views
2K
Discussion on Astronomical Prime Numbers and Re-evaluating the Primali
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Are there any two pairs of integers with the same result in a specific function?
  • · Replies 7 ·
Replies
7
Views
2K