Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
primality test
|
| gptkbp:alsoKnownAs |
gptkb:Miller–Rabin_primality_test
|
| gptkbp:complexity |
O(k log^3 n)
|
| gptkbp:deterministicFor |
certain values of n
|
| gptkbp:errorDetection |
at most 1/4 per iteration
|
| gptkbp:field |
computer science
number theory |
| gptkbp:generalizes |
gptkb:Fermat_primality_test
|
| https://www.w3.org/2000/01/rdf-schema#label |
Rabin–Miller primality test
|
| gptkbp:input |
odd integer n > 2
|
| gptkbp:introducedIn |
1976
|
| gptkbp:language |
English
|
| gptkbp:namedAfter |
gptkb:Michael_O._Rabin
gptkb:Gary_L._Miller |
| gptkbp:output |
composite or probably prime
|
| gptkbp:relatedTo |
gptkb:AKS_primality_test
gptkb:Solovay–Strassen_primality_test |
| gptkbp:type |
gptkb:algorithm
|
| gptkbp:usedFor |
primality testing
|
| gptkbp:usedIn |
cryptography
RSA key generation |
| gptkbp:bfsParent |
gptkb:Michael_Rabin
gptkb:Michael_O._Rabin |
| gptkbp:bfsLayer |
5
|