Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 exptools 1/6/84; site iwu1d.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!ihnp4!iwu1d!tan
From: tan@iwu1d.UUCP (William Tanenbaum)
Newsgroups: net.math
Subject: Re: Further notes on the number 1729
Message-ID: <197@iwu1d.UUCP>
Date: Thu, 10-May-84 16:44:40 EDT
Article-I.D.: iwu1d.197
Posted: Thu May 10 16:44:40 1984
Date-Received: Sat, 12-May-84 08:58:59 EDT
References: <14100005@smu.UUCP>, <1274@uvacs.UUCP>, <914@dciem.UUCP>
Organization: AT&T Bell Labs, Naperville, IL
Lines: 10

I have a question for Mark Brader or anyone else.  I always thought
that Fermat's theorem (n to the p'th power is equal to n modulo p for 
any n if p is a prime) was THE fast way for testing a large number for
primality.  In other words, if p is chosen composite, Fermat's theorem
fails for some n.  Now we are told that there are some composite values
of p (Carmichael numbers) for which Fermat's theorem always holds.
	Ok, now will someone tell me how to quickly test a large
number for primality.  There must be such a test, or the public key
cryptography system based on factoring large numbers would not work.
What am I missing?