Integer factorization problem
GPTKB entity
Statements (21)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:class |
NP
|
| gptkbp:difficulty |
believed to be hard for large integers
|
| gptkbp:field |
cryptography
number theory |
| https://www.w3.org/2000/01/rdf-schema#label |
Integer factorization problem
|
| gptkbp:input |
composite integer
|
| gptkbp:not_known_to_be |
NP-complete
|
| gptkbp:not_known_to_be_in |
P
|
| gptkbp:output |
prime factors of input integer
|
| gptkbp:relatedTo |
gptkb:RSA_algorithm
prime factorization |
| gptkbp:security_basis_for |
gptkb:RSA_encryption
RSA digital signatures |
| gptkbp:solvedBy |
gptkb:quadratic_sieve
gptkb:general_number_field_sieve Shor's algorithm (quantum) trial division (inefficient) |
| gptkbp:used_in |
public-key cryptography
|
| gptkbp:bfsParent |
gptkb:Discrete_logarithm_problem
|
| gptkbp:bfsLayer |
7
|