Is it possible to transform RSA to SAT during polynomial time? (Polynomial number of variables and clauses of logical formula and polynomial time of creating logical formula).
The size of the task is obviously the number of bits $n$.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Since RSA (more specifically integer factorization) is in NP and SAT is NP-complete, I think it should be possible. (But I do not know how?) $\endgroup$– user53923Commented Mar 21, 2017 at 9:11
-
$\begingroup$ cstheory.stackexchange.com/q/6755/5038 $\endgroup$– D.W. ♦Commented Mar 21, 2017 at 16:12
Add a comment
|