Statements (27)
Predicate | Object |
---|---|
gptkbp:instanceOf |
gptkb:algorithm
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
|
https://www.w3.org/2000/01/rdf-schema#label |
Miller–Rabin 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
gptkb:Gary_L._Miller |
gptkbp:bfsLayer |
6
|