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.

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?

share|improve this question
2  
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

1 Answer 1

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.

share|improve this answer
    
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
1  
Probabilistic algorithm for generating 2 primes. –  DanielV Oct 7 '13 at 14:31

Your Answer

 
discard

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.