# On factoring really big numbers

**URL:** <https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735>\
**Category:** Factual Questions\
**Created:** [January 26, 2005, 8:52am UTC](https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735 "2005-01-26T08:52:50Z")\
**Posts on this page:** 5\
**Page:** 2

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [January 27, 2005, 5:52am UTC](https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735/21 "2005-01-27T05:52:54Z")

</div>

> [@ftg](#):
>
> 1. Well, _every_ textbook I’ve taught sorting from has had the early termination condition. Otherwise, what’s the point?

Interesting. Of the three algorithms textbooks I have lying around, one doesn’t mention bubblesort at all, one has the early termination condition, and one doesn’t.

---

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [January 27, 2005, 10:48am UTC](https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735/22 "2005-01-27T10:48:38Z")

</div>

> [@pulykamell](#):
>
> Maybe these fabulous prizes will inspire you:
> 
> [http://www.rsasecurity.com/rsalabs/node.asp?id=2093](http://www.rsasecurity.com/rsalabs/node.asp?id=2093)
> 
> Basically, if you can find a relatively quick way to factor the products of two extremely large primes, you’ve undermined the basis of most modern cryptography.

If you figured out how to factor numbers quickly, you’d sell it to the security services for millions, and not enter it into an RSA competition to win a few thousand 🙂

---

<div class="post-metadata">

**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\
**Post date:** [January 27, 2005, 5:34pm UTC](https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735/23 "2005-01-27T17:34:01Z")

</div>

> [@Omphaloskeptic](#):
>
> \otimes is far too symmetric a symbol to be used for an antisymmetric relation, to my sense of aesthetics.

Especially given the existence of \prec.

---

<div class="post-metadata">

**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\
**Post date:** [January 27, 2005, 6:21pm UTC](https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735/24 "2005-01-27T18:21:30Z")

</div>

> [@+MDI](#):
>
> If you figured out how to factor numbers quickly, you’d sell it to the security services for millions, and not enter it into an RSA competition to win a few thousand 🙂

Well, of course. 😉 But imagine one day if someone did figure out a relatively quick algorithm to solve such problems. Do you realize what kind of power he or she would wield? Can you imagine how much $$$ that would be worth not to security services, but to governments themselves? Hey, sounds like a movie plot.

---

<div class="post-metadata">

**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\
**Post date:** [January 27, 2005, 6:52pm UTC](https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735/25 "2005-01-27T18:52:23Z")

</div>

> [@pulykamell](#):
>
> Well, of course. 😉 But imagine one day if someone did figure out a relatively quick algorithm to solve such problems. Do you realize what kind of power he or she would wield? Can you imagine how much $$$ that would be worth not to security services, but to governments themselves? Hey, sounds like a movie plot.

a) There already is an algorithm. It’s down to the engineering problem of building the computer which can run it.

b) You really wouldn’t wield that much power. RSA, and public-key encryption schemes in general, are relatively slow and get used for securely sharing a private key to use a faster cipher like DES or IDEA. There are currently two companies, with two more on the way, selling quantum cryptography systems which are not only literally impossible to break (in theory if not implementation), but alert the users if anyone is trying to listen in. The only catch is that they only work at a range of tens to low hundreds of kilometers.

[Previous page](https://boards.straightdope.com/t/on-factoring-really-big-numbers/286735.md?page=1)