what is the formula to figure out two unknown prime numbers that equal
a known product?
in other words... prime x prime = known number

---

Request for Question Clarification by mathtalk-ga on 09 Jan 2005 08:48 PST

Hi, mrjingles-ga:

As crythias-ga rightly points out, such problems form the basis of the
widely used RSA method of encryption.  Up to 20 or perhaps 30 digits
in the known product such problems are solved by fairly easily
programmed methods.  Using networks of loosely coupled computers,
problems with up to a few hundred digits are tractable with current
methods.

Before I'd attempt to present something in the way of a "formula" to
factor a product of two primes, it would be helpful to know a bit
about your background both in math and in programming.

regards, mathtalk-ga

The answer to that question is the basis of some cryptographic
methods. That is, multiplying two very large prime numbers is very
easy. Determining the prime numbers from the known multiple is a very
processor intensive task. The answer to your question is worth more
than $7... it is probably one of "The" true multi-million dollar
questions.

The short answer is that there is no forumla to do what you ask. It is
pretty much brute force to accomplish. I had a thought in my head to
start with a table of primes, but even that is a daunting task.

If the answer is able to be given, then some very popular
cryptographic methods are now useless.

This is a free comment.

thank you for replying :)

That's right.

If you are playing with number theory, then good luck.

If you you are playing with small numbers only, or you are trying to
use the factoring of the small composite number for applied math, then
use your computer and some patience.

N = u*v
So, u = N/v

N is your known number, known product, composite number.
u is one of the primes.
v is the other prime.

You start with v=2.
u = N/2. Then check if this u is a prime. If it is, then you got your two primes.
If not, then try u = N/3, N/5, N/7, N/11, N/13, ...., until you get your two primes.

Just out of curiosity, what is the semi-prime you are trying to
factor? Perhaps I could factor it.

I'm fond of David Bressoud's 1989 book, Factorization and Primality
Testing (in Springer-Verlag's Undergraduate Texts in Mathematics
series).

Quoting from his introductory section of Chapter 8, The Quadratic Sieve:

"Once you have used trial division to get all the small divisors out
of your number, a pseudoprime or strong pseudoprime test has shown
that it is still composite, and you feel that you have exhausted the
possibilities of Pollard's rho and p - 1 algorithms, then you need to
consider one of the big guns: the Elliptic Curve Method (ECM), the
Continued Fraction Algorithm (CFRAC), or the Quadratic Sieve (QS). 
The Quadratic Sieve has now totally supplanted the Continued Fraction
Algorithm.  As currently implemented, it is faster than CFRAC for any
n of at least 18-20 digits, the smallest size for which QS is readily
usable.  The Elliptic Curve Method has the advantage of being
practical from the point where trial division becomes impossible until
well into the range where QS can be implemented, at least 25-30
digits."

Of course the march of progress since that book was written has been
relentless, but it's a charming exposition of the basic theory and
techniques.

regards, mathtalk-ga