Associated Topics || Dr. Math Home || Search Dr. Math

### Two Prime Numbers with 400-Digit Product

```Date: 07/29/2006 at 06:40:34
From: Jeff
Subject: prime numbers

What two prime numbers, if multiplied, would generate a 400-digit number?

```

```
Date: 07/29/2006 at 09:48:40
From: Doctor Vogler
Subject: Re: prime numbers

Hi Jeff,

Thanks for writing to Dr. Math.  The only thing you need to do is find
two 200-digit prime numbers.  Pick any two primes that are about 200
digits each, and their product will have about 400 digits.

How do you find such big primes?  The fact of the matter is that if
you want to get a 400-digit number, then you have to deal with very
big numbers.  There's no way around it.  The product of two small
numbers will always get you a small number.  Hand calculators aren't
equipped to deal with numbers that big, and pencil and paper would
take weeks to work out a solution.

So I would recommend using a computer and a math program like

http://pari.math.u-bordeaux.fr/

under UNIX and even one that works under Windows.)  Run Pari, and you

nextprime(7*10^199)

for a 200-digit prime number, for example.  You can say

x = nextprime(7*10^199)

to give it a name.  You can say

y = nextprime(8*10^199)

to get another one.  Then you can multiply them together with

x*y

Or you can tell it

2^1279-1

and then ask for a 15-digit prime and multiply them together.

In Mathematica (which is not free, but many schools and universities
have it installed), you can ask for

NextPrime[m]

for any number m, and it will return the smallest prime bigger than m.

Another math doctor suggested an alternate way to find such big
primes.  Look on a list of large primes to find one near to 400
digits, and then you only have to look for a small prime to make up
the rest of the digits.  See

400-Digit Product of Two Primes
http://mathforum.org/library/drmath/view/61527.html

Does that help?

In practice, you get 400-digit products of two primes when you want to
encrypt a message using RSA.  In that case, you had better not use an
obvious way to pick your prime numbers, or someone could guess what
primes you used, and then what's the good of encrypting?  Someone
could easily crack the message!  You should instead generate two
purely *random* 200-digit numbers, and then find the next primes after
each of those.  Even better would be to keep choosing random 200-digit
numbers until you get one that is prime.

Determining If a Number is Prime
http://mathforum.org/library/drmath/view/65454.html

back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search