Almost all primes can be quickly certified
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new probabilistie primality test is presented, different from the tests of Miller, Solovay-Strassen, and Rabin in that its assertions of primality are certain, rather than being correct with high probability or dependent on an unproven assumption.
Abstract
Article Free Access Share on Almost all primes can be quickly certified Authors: S Goldwasser EECS Department and Laboratory for Computer Science, Massachusetts Institute of Technology EECS Department and Laboratory for Computer Science, Massachusetts Institute of TechnologyView Profile , J Kilian Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of Technology Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of TechnologyView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986Pages 316–329https://doi.org/10.1145/12130.12162Published:01 November 1986Publication History 103citation1,142DownloadsMetricsTotal Citations103Total Downloads1,142Last 12 Months171Last 6 weeks33 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF