A note on monte carlo primality tests and algorithmic information theory

DOI10.1002/cpa.3160310407zbMath0401.94008OpenAlexW1985222920MaRDI QIDQ4186204

Jacob T. Schwartz, Gregory J. Chaitin

Publication date: 1978

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/cpa.3160310407

zbMATH Keywords

computational complexityalgorithmic information theoryformal systemrandom sequencescomplexity of proofsprime numbersaxiomsMonte Carlo primality Tests

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity of computation (including implicit computational complexity) (03D15) Information theory (general) (94A15) Statistical aspects of information-theoretic topics (62B10) Primality (11Y11)

Related Items

Asymptotically Fast Factorization of Integers, Recent developments in primality testing, The Road to Quantum Computational Supremacy, Bell's Primeness Criterion for W(2n + 1), A relation between correctness and randomness in the computation of probabilistic algorithms, Gödel's theorem and information

Cites Work

• Riemann's hypothesis and tests for primality