Statements (26)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:algorithm
gptkb:primality_test |
| gptkbp:complexity |
O(k log^3 n)
|
| gptkbp:deterministic_for |
certain values of n
|
| gptkbp:error_probability |
decreases exponentially with number of rounds
|
| gptkbp:field |
computer science
number theory |
| gptkbp:hasWikipediaPage |
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
|
| gptkbp:input |
odd integer n > 2
|
| gptkbp:introducedIn |
1976
|
| gptkbp:inventedBy |
gptkb:Michael_O._Rabin
gptkb:Gary_L._Miller |
| gptkbp:namedAfter |
gptkb:Michael_O._Rabin
gptkb:Gary_L._Miller |
| gptkbp:output |
composite or probably prime
|
| gptkbp:probabilistic_for |
general n
|
| gptkbp:relatedTo |
gptkb:AKS_primality_test
gptkb:Fermat_primality_test gptkb:Solovay–Strassen_primality_test |
| gptkbp:type |
gptkb:algorithm
|
| gptkbp:used_in |
cryptography
RSA key generation |
| gptkbp:usedFor |
primality testing
|
| gptkbp:bfsParent |
gptkb:Rabin–Miller_primality_test
|
| gptkbp:bfsLayer |
6
|
| https://www.w3.org/2000/01/rdf-schema#label |
Miller–Rabin primality test
|