# RSA-210 factorization

RSA-210 has been factored

N = 245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549103626827191679864079776723243005600592035631246561218465817904100131859299619933817012149335034875870551067


in two 105-digit prime numbers. http://www.mersenneforum.org/showpost.php?p=354259

 435958568325940791799951965387214406385470910265220196318705482144524085345275999740244625255428455944579
562545761726884103756277007304447481743876944007510545104946851094548396577479473472146228550799322939273


How did we know RSA-210 was a semiprime?

-
In RSA $n = p \times q$, where $p$ and $q$ are picked using two large primes by algorithm, RSA Algotithm. This is known as the Integer Factorization Problem. – Amzoti Oct 7 '13 at 12:57

No one "knew" that RSA-210 was semiprime. Not even those running the contest know what the factors of the number are. It's just that they assume their algorithms for generating the contest numbers are correct (to enough probability) and so the numbers they post are almost certainly semiprime.

It's only after factoring that everyone else knows a number is semiprime, unless some incredible result comes up in number theory algorithms which isn't likely.

-
Do you mean by "almost certainly" that their algorithm for generating the contest numbers was probabilistic or that they cannot be sure (as one never can) that their implementation/algorithm did not contain a bug? – JiK Oct 7 '13 at 14:30
Probabilistic algorithm for generating 2 primes. – DanielV Oct 7 '13 at 14:31