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
Mathematica or Pari.  You can download Pari for free at

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

(In the "downloads" section, you can find several versions that work
under UNIX and even one that works under Windows.)  Run Pari, and you
can ask it for

  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.

See also

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

If you have any questions about this or need more help, please write
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/