Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can any body can give me a formula for all composite prime numbers. $$ N=xy$$ where $N$ is given and $x,y$ are both unknown prime numbers.

Ex. $$N=\{\ldots,143,187,209,221,247,253,299,319,\ldots\}$$

The possible solution for splitting any composite numbers with small factors, using Pollard's rho algorithm: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

I try to use spreadsheet(Microsoft Excel 2007) to make #Pollard's rho algorithm :)




Sample file:


share|improve this question
You are asking for a formula (or an algorithm) for factoring large semiprimes? There are no known efficient algorithms. That is, after all, the key to the security of the RSA cryptosystem. So other than time-consuming algorithms, no, nobody can give you a "formula" for factoring. P.S. What's with the links? Are you advertising something? If so, your post is spam and will be deleted. –  Arturo Magidin Jun 25 '12 at 21:42
@Michael Factoring large primes is trivial. Arturo mentioned not that, but factoring semiprimes, which is the OP's problem. –  Bill Dubuque Jun 25 '12 at 22:38
@saccuanjohn: So it sounds like you are posting to advertise your work. That's spam. –  Arturo Magidin Jun 26 '12 at 1:22
@MichaelHardy: Nobody knows if factoring semiprimes is inherently simpler than the factoring problem in general, but by the same token nobody knows an efficient method of factoring semiprimes either. Even factoring RSA challenge numbers, which known to be semiprime and there is a lot of other information known about the prime factors (they are not close to one another, they are "safe primes", etc) does not seem on average to be any easier than the general problem. –  Arturo Magidin Jun 26 '12 at 1:32
@saccuanjohn: Verifying for the first 47 Mersenne primes is not proof. Once upon a time, a chap called Fermat verified that the first few numbers of the form $2^{2^n}+1$ were prime (3, 5, 17, 257 and 65537), and he conjectured that all such numbers are prime. It wasn't until 70 years after poor Fermat passed away that another chap called Euler proved that the next number in this list was not prime. Indeed, noone has found any more Fermat primes. You might be interested in this mathoverflow question. –  user1729 Jun 26 '12 at 10:26

1 Answer 1

Variations on Fermat's method work if $\rm\ n = p\:q\ $ is a product of two "close" primes, namely if $\rm\:|p-q| < n^{1/3},\:$ then $\rm\:n\:$ can be factored in polynomial time, see Robert Erra; Christophe Grenier. The Fermat factorization method revisited. 2009. See also their slides How to compute RSA keys? The Art of RSA: Past, Present, Future. See also this prior question.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.