# Public-Key Cryptography and Large Prime Numbers **URL:** \ **Category:** Factual Questions\ **Created:** [June 25, 2010, 3:06am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440 "2010-06-25T03:06:22Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [June 25, 2010, 3:06am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/1 "2010-06-25T03:06:22Z")
How are the large prime numbers generated ? If they’re so hard to factor, why aren’t they also difficult to generate? ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [June 25, 2010, 3:22am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/2 "2010-06-25T03:22:38Z")
It’s very easy to factor a prime number. The factors are 1 and itself. 🙂 What’s difficult is finding a fast way to find the prime factors of a composite number. If you take the product of two really big primes, for example, finding the prime factors of the product takes a really long time. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [June 25, 2010, 3:27am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/3 "2010-06-25T03:27:07Z")
I wrote some code that creates a public/private key pair for RSA. It takes several minutes to run even though pretty much all of that time is in finding a prime number of proper length. So no, it’s not fast. 😛 As for how you generate it, essentially you just pick a random number and keep adding one until you’ve found a number that passes a prime number test (or keep trying random numbers). ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [June 25, 2010, 3:27am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/4 "2010-06-25T03:27:14Z")
> [@friedo](#): > > It’s very easy to factor a prime number. The factors are 1 and itself. 🙂 > > What’s difficult is finding a fast way to find the prime factors of a composite number. If you take the product of two really big primes, for example, finding the prime factors of the product takes a really long time. Thank you. But how are the large primes generated (i.e., before they’re multiplied)? ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [June 25, 2010, 3:29am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/5 "2010-06-25T03:29:16Z")
> [@Sage\_Rat](#): > > I wrote some code that creates a public/private key pair for RSA. It takes several minutes to run even though pretty much all of that time is in finding a prime number of proper length. So no, it’s not fast. 😛 > > As for how you generate it, essentially you just pick a random number and keep adding one until you’ve found a number that passes a prime number test (or keep trying random numbers). If you pick a random number and keep adding one until you find a prime, doesn’t that mean that there’ll be a lot of overlap among primes generated by your code? How many primes are in that space? ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [June 25, 2010, 3:30am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/6 "2010-06-25T03:30:40Z")
1. Decide how many bits you want it to have. 2. Set the high and low bit to 1. 3. Set the other bits randomly. 4. Check to see if it’s a prime number. 5. If so, you’re done. Otherwise, add 2 and go to step 4. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [June 25, 2010, 3:31am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/7 "2010-06-25T03:31:53Z")
> [@FrustratedIdiot](#): > > If you pick a random number and keep adding one until you find a prime, doesn’t that mean that there’ll be a lot of overlap among primes generated by your code? How many primes are in that space? Each time you want to generate a new random number, you start in a random spot, not where you last left off. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [June 25, 2010, 3:35am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/8 "2010-06-25T03:35:43Z")
> [@FrustratedIdiot](#): > > If you pick a random number and keep adding one until you find a prime, doesn’t that mean that there’ll be a lot of overlap among primes generated by your code? How many primes are in that space? If you choose your start point randomly for each new prime, there’s no particular reason that two values would end up near each other. For my code, rather than adding one each time, I picked a new random number, but I probably didn’t need to. As for how many primes there are on average in a region, there is a formula to determine that,\* but since you _have_ to find a prime, it doesn’t really matter how hard it is. You still have to do it. - “Roughly speaking, the prime number theorem states that if a random number nearby some large number N is selected, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N.” - Wikipedia ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [June 25, 2010, 3:39am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/9 "2010-06-25T03:39:01Z")
> [@FrustratedIdiot](#): > > Thank you. But how are the large primes generated (i.e., before they’re multiplied)? You can generate them yourself with an algorithm like Erastosthenes’ Sieve (which also takes a little while) or you can just pick some from a [known list](http://www.prime-numbers.org/prime-number-9879450000-9879455000.htm). For example, if I pick known primes 9,879,452,447 and 9,879,454,831, the result is 97,603,604,205,148,921,457 which would take quite a while to factor. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [June 25, 2010, 3:55am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/10 "2010-06-25T03:55:18Z")
> [@friedo](#): > > You can generate them yourself with an algorithm like Erastosthenes’ Sieve (which also takes a little while) or you can just pick some from a [known list](http://www.prime-numbers.org/prime-number-9879450000-9879455000.htm). > > For example, if I pick known primes 9,879,452,447 and 9,879,454,831, the result is 97,603,604,205,148,921,457 which would take quite a while to factor. If you used a known list, wouldn’t the composite number be fairly easy to factor? ---
**Author:** ![Kevbo](https://avatars.discourse-cdn.com/v4/letter/k/e47774/32.png) [@Kevbo](https://boards.straightdope.com/u/Kevbo)\ **Post date:** [June 25, 2010, 3:58am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/11 "2010-06-25T03:58:20Z")
> [@Sage\_Rat](#): > > As for how you generate it, essentially you just pick a random number and keep adding one . Since no even numbers are prime, you can increase the speed of this by adding two instead of one. (and then there is no need to test for 2 as a factor) Lots of faster ways to find primes, BTW. ETA:No even numbers _except 2_ are prime. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [June 25, 2010, 4:21am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/12 "2010-06-25T04:21:46Z")
> [@FrustratedIdiot](#): > > If you used a known list, wouldn’t the composite number be fairly easy to factor? Not necessarily, if the list is large. It’s really quick to pick _some_ random entry from a big list, while it takes a long time to check data against _every_ entry in the list. ---
**Author:** ![Dervorin](https://avatars.discourse-cdn.com/v4/letter/d/eb8c5e/32.png) [@Dervorin](https://boards.straightdope.com/u/Dervorin)\ **Post date:** [June 25, 2010, 4:43am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/13 "2010-06-25T04:43:11Z")
> [@FrustratedIdiot](#): > > If you used a known list, wouldn’t the composite number be fairly easy to factor? The [Prime Counting Function](http://en.wikipedia.org/wiki/Prime_counting_function) allows us to calculate the number of primes that are less than a given number x. Public-key cryptography now typically uses keys that are 512 bits in length, meaning that we would potentially have to check all primes less than 2^512, which is going to be a fairly large number, approximately equal to 2^512 / ln(2^512), which is 3.78 \* 10^151. Even if the list is known, the problem can still be impracticably difficult if the list is long enough, which is true in this case. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [June 25, 2010, 4:56am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/14 "2010-06-25T04:56:56Z")
Public key cryptography hasn’t used 512 bit keys since 1990. ---
**Author:** ![rjk](https://avatars.discourse-cdn.com/v4/letter/r/ed655f/32.png) [@rjk](https://boards.straightdope.com/u/rjk)\ **Post date:** [June 25, 2010, 6:18am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/15 "2010-06-25T06:18:44Z")
In [Wikipedia’s RSA article](http://en.wikipedia.org/wiki/Rsa), they say: > [@](#): > > As of 2010[update], the largest (known) number factored by a general-purpose factoring algorithm was 768 bits long (see RSA-768), using a state-of-the-art distributed implementation. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future. Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 300 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. Keys of 512 bits have been shown to be practically breakable in 1999 when RSA-155 was factored by using several hundred computers and are now factored in a few weeks using common hardware.[9] A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys. It is currently recommended that n be at least 2048 bits long.[10] Back to the OP’s question: **Punoqllads** about covered it, but skimmed over the testing step. Primes are hard to test for mostly because there are a huge number of possible factors to try. See [Wikipedia](http://en.wikipedia.org/wiki/Primality_test) again for info on that. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [June 25, 2010, 7:03am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/16 "2010-06-25T07:03:09Z")
> [@FrustratedIdiot](#): > > If [products of two large prime numbers] are so hard to factor, why aren’t they also difficult to generate? One doesn’t need the calculation details to grasp the concept: Some reversible processes are easier one direction than the other. For example, it’s much easier to square 7777 than to find the square root of 60481729. Or, it’s much easier to _exit_ a parallel-parking spot than to park there in the first place. 😃 > [@Sage\_Rat](#): > > … until you’ve found a number that passes a prime number test … Technical question I’m too lazy (or stupid) to Google for: Some primality tests will miscall primes 0.000001% of the time. What happens if you feed such a pseudo-prime into the encryption algorithms? ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [June 25, 2010, 8:44am UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/17 "2010-06-25T08:44:43Z")
> [@septimus](#): > > One doesn’t need the calculation details to grasp the concept: Some reversible processes are easier one direction than the other. For example, it’s much easier to square 7777 than to find the square root of 60481729. Or, it’s much easier to _exit_ a parallel-parking spot than to park there in the first place. 😃 The technical term for this is a “trapdoor function”: It’s easy to fall in (multiply two big numbers) but difficult to climb back out (factor one huge number). ---
**Author:** ![rjk](https://avatars.discourse-cdn.com/v4/letter/r/ed655f/32.png) [@rjk](https://boards.straightdope.com/u/rjk)\ **Post date:** [June 25, 2010, 3:57pm UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/18 "2010-06-25T15:57:02Z")
> [@septimus](#): > > One doesn’t need the calculation details to grasp the concept: Some reversible processes are easier one direction than the other. For example, it’s much easier to square 7777 than to find the square root of 60481729. Or, it’s much easier to _exit_ a parallel-parking spot than to park there in the first place. 😃 > > Technical question I’m too lazy (or stupid) to Google for: Some primality tests will miscall primes 0.000001% of the time. What happens if you feed such a pseudo-prime into the encryption algorithms? The encryption still works fine, but it’s easier to break. ---
**Author:** ![rjk](https://avatars.discourse-cdn.com/v4/letter/r/ed655f/32.png) [@rjk](https://boards.straightdope.com/u/rjk)\ **Post date:** [June 25, 2010, 4:08pm UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/19 "2010-06-25T16:08:11Z")
(Missed the edit.) The Greatest Common Factor test will find a factor half the time (for large numbers), so you can apply it repeatedly to reach any probability you like that your candidate number is prime. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [June 25, 2010, 4:44pm UTC](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440/20 "2010-06-25T16:44:57Z")
What’s “the Greatest Common Factor test”? [Next page](https://boards.straightdope.com/t/public-key-cryptography-and-large-prime-numbers/544440.md?page=2)