Premium
A note on monte carlo primality tests and algorithmic information theory
Author(s) -
Chaitin Gregory J.,
Schwartz Jacob T.
Publication year - 1978
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.3160310407
Subject(s) - primality test , computer science , watson , ibm , discrete mathematics , theoretical computer science , mathematical economics , calculus (dental) , mathematics , artificial intelligence , prime number , medicine , materials science , dentistry , nanotechnology
Solovay and Strassen, and Miller and Rabin have discovered fast al- gorithms for testing primality which use coin-flipping and whose con-