Two Prime Numbers with 400-Digit ProductDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/