hes@ecsvax.UUCP (01/28/86)
"Two computer scientists have found a new way to determine whether large numbers are prime--an old problem that is of practical as well as theoretical importance." Science 31 January 1986 pp.452-453 There are no presently known methods of deterministically testing whether a number is prime and that run in polynomial time. A new method developed by Shafi Goldwasser and Joseph Kilian of MIT doesn't do this either since it "is a probabilistic algorithm that is always correct and that almost always runs in polynomial time. However, it is not yet fast enough to be of clear practical importance." It appears that this method can tell quickly that a number is composite, and can usually (maybe always?) tell if a number is prime. But there *may* be primes for which the test runs slowly. This is the "probabilistic" aspect of this method - but it isn't known if there are any such primes. Some public-key cryptosystems depend for their security on the difficulty of factoring large (200 or more digit) composite numbers. This article doesn't say anything about finding the factors. The article is easy to read (but hard to understand :-) - it is 1 1/3 8 1/2" x 11" pages, and has no literature citations. --henry schaffer