What is recorded here?
Rabin analyzes randomized compositeness-witness sampling: for each fixed composite, independent uniform trials give exponentially decreasing false acceptance, while a witness certifies compositeness; the journal paper includes implementation and reported experiments. A modular calculation can expose an integer as composite without finding all its factors. Rabin shows that witnesses are common enough that independent random choices rapidly reduce the chance of mistakenly accepting a composite. Finding a witness is decisive; passing the trials gives a probable-prime result, not a proof that the number is prime. The paper explains this distinction and reports implementations and large-number searches. Its later note simplifies the test using repeated squaring, while preserving the earlier witness theory and contributors.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
Exact 1980 J. Composite-witness logic and at-most-quarter nonwitness bound yield <=4^-k false acceptance for each fixed composite under independent uniform random residues; this is not posterior primality probability or a deterministic prime certificate. Source inequality/cost glyphs damaged: inclusive quarter bound retained, exact strictness/step coefficient not certified. Arithmetic-operation model not silently unit bit cost; computation/randomness errors separate. Note eliminates gcds through square-root checks. Reported large/twin-prime searches are assertions, not twin-prime conjecture proof or guaranteed termination of all special-form searches; heuristic search costs remain heuristic. The complete proof and the source-reported computer experiments have not been independently reproduced here. Repeating one fixed base gains no independent-trial bound.
Read the original work
- Rabin: randomized primality testing with one-sided witness error; exact original journal technical text
- Publisher-deposited exact 1980 journal identity
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Michael O. Rabin
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Rabin: randomized primality testing with one-sided witness error
Rabin analyzes randomized compositeness-witness sampling: for each fixed composite, independent uniform trials give exponentially decreasing false acceptance, while a witness certifies compositeness; the journal paper includes implementation and reported experiments.
A modular calculation can expose an integer as composite without finding all its factors. Rabin shows that witnesses are common enough that independent random choices rapidly reduce the chance of mistakenly accepting a composite. Finding a witness is decisive; passing the trials gives a probable-prime result, not a proof that the number is prime. The paper explains this distinction and reports implementations and large-number searches. Its later note simplifies the test using repeated squaring, while preserving the earlier witness theory and contributors.
Scientific scope
Exact 1980 J. Composite-witness logic and at-most-quarter nonwitness bound yield <=4^-k false acceptance for each fixed composite under independent uniform random residues; this is not posterior primality probability or a deterministic prime certificate. Source inequality/cost glyphs damaged: inclusive quarter bound retained, exact strictness/step coefficient not certified. Arithmetic-operation model not silently unit bit cost; computation/randomness errors separate. Note eliminates gcds through square-root checks. Reported large/twin-prime searches are assertions, not twin-prime conjecture proof or guaranteed termination of all special-form searches; heuristic search costs remain heuristic. The complete proof and the source-reported computer experiments have not been independently reproduced here. Repeating one fixed base gains no independent-trial bound.
People and systems
Michael O. Rabin