Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!wuarchive!cec2!news
From: kumar@wucs1.wustl.edu (Arun Kumar)
Newsgroups: comp.theory
Subject: Re: Primality Testing
Message-ID: <1990Feb28.173716.23412@cec1.wustl.edu>
Date: 28 Feb 90 17:37:16 GMT
References: <1990Feb26.183024.23868@sj.ate.slb.com>
Sender: news@cec2 (USENET News System)
Reply-To: kumar@wucs1.wustl.edu (Arun Kumar)
Distribution: usa
Organization: Washington University, St. Louis MO
Lines: 11

In article <1990Feb26.183024.23868@sj.ate.slb.com> basie@sj.ate.slb.com writes:
>	Given a positive integer x,
>	Is x a prime number?
>
>My question is this: What is the fastest algorthm for
>determining the primality of x and what is its time

Look for a paper by Rabin in the Computer and Control Abstracts around
1984. He describes a fast probabilistic algorithm.
--------------------------------------------------------------
Arun Kumar (kumar@wucs1.wustl.edu)