From root@newsbf02.news.aol.com	 Fri Aug 16 15:32:13 1996
Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU [18.69.0.28]) by bloom-picayune.MIT.EDU (8.6.13/2.3JIK) with SMTP id PAA14542; Fri, 16 Aug 1996 15:32:07 -0400
Received: from relay4.UU.NET by MIT.EDU with SMTP
	id AA25385; Fri, 16 Aug 96 15:30:55 EDT
Received: from ngeout01.news.aol.com by relay4.UU.NET with SMTP 
	(peer crosschecked as: ngeout01.news.aol.com [152.163.176.244])
	id QQbdba18204; Fri, 16 Aug 1996 15:30:48 -0400 (EDT)
Received: from newsbf02.news.aol.com (newsbf02.mail.aol.com [152.163.172.50]) by ngeout01.news.aol.com (8.6.12/8.6.12) with SMTP id PAA04292 for <news-answers@uunet.uu.net>; Fri, 16 Aug 1996 15:34:23 -0400
Received: by newsbf02.news.aol.com
	(1.38.193.5/16.2) id AA18175; Fri, 16 Aug 1996 15:30:46 -0400
Posted-Date: 16 Aug 1996 15:30:37 -0400
Received-Date: Fri, 16 Aug 1996 15:30:46 -0400
To: news-answers@uunet.uu.net
Path: newsbf02.news.aol.com!not-for-mail
From: rsamaven@aol.com (RSAMaven)
Newsgroups: news.answers
Subject: RSA Laboratories FAQ - Part 6
Date: 16 Aug 1996 15:30:37 -0400
Organization: America Online, Inc. (1-800-827-6364)
Lines: 538
Sender: root@newsbf02.news.aol.com
Message-Id: <4v2i8t$hn5@newsbf02.news.aol.com>
Reply-To: rsamaven@aol.com (RSAMaven)

Factoring and Discrete Logarithms


Question 45. What is the Factoring Problem?


Factoring is the act of splitting an integer into a set of smaller
integers (factors) which, when multiplied together, form the original
integer. For example, the factors of 15 are 3 and 5; the factoring problem
is to find 3 and 5 when given 15. Prime factorization requires splitting
an integer into factors that are prime numbers; every integer has a unique
prime factorization. Multiplying two prime integers together is easy, but
as far as we know, factoring the product is much more difficult.

Question 46. What is the Significance of Factoring in Cryptography?

Factoring is the underlying, presumably hard problem upon which several
public-key cryptosystems are based, including RSA. Factoring an RSA
modulus (see Question 8) would allow an attacker to figure out the private
key; thus, anyone who can factor the modulus can decrypt messages and
forge signatures. The 
security of RSA depends on the factoring problem being difficult and the
[remainder of text deleted by folder-shrink.pl]