Re: reducing the factorization decision problem to SAT?

In article <73f0758f-8c5b-4682-803e-c509edcd9c92@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
Hi,

It's obviously possible to reduce an NP decision problem to SAT using
Cook-Levin's mapping, but how does one do it in an "intelligible,"
simple way in practice for integer factorization?

I know it's been done before, I just don't know how. Specifically,
how do you reduce this decision problem...

Given an integer n and an integer k s.t. 1 < k < n, are there any
integers j s.t. j divides n and 1 < j < k?

...to SAT? (Or any other decision problem that the factorization
problem can be Turing reduced to? I suppose that simply asking if
there are any nontrivial factors (i.e., not equal to +/-1 or +/-n)
would work just as well.) If anyone knows how to reduce factorization
to SAT I'd be interested to know how it's done.

Thanks,

Phil

Suppose you want to find a factor of a positive integer n and all you
have is SAT. Construct a combinational circuit that multiplies two binary
numbers, a and b, resulting in a binary number c[1..k] where k is at least
ceil(log_2(n)). Then assert logically that c is equal to n, e.g. make
a k-input AND gate for which the i'th input is c[i] if n[i] is 1, or NOT
c[i] if n[i] is 0, and then assert that the output of this AND gate is 1.
That is, the output of the whole circuit is the output of this AND gate,
and it will only be 1 if a and b are factors of n. Convert this circuit
into CNF-SAT (a subset of general SAT) using the construction you can find
in CLRS, or if you type "to CNF efficiently" as a Google Groups search to
find a post I made a few years ago. The resulting formula is satisfiable
only by values of a and b that are factors of n. If all you have is
something that decides SAT without providing satisfying assignments,
just go setting subsequent bits of a and b to 0 and 1, asking whether
the formula is still satisfiable and keeping values for which the formula
remains satisfiable. This is a little different from the decision problem
formulation of factorization you mention but the result is the same.
--
Daniel Jimenez djimenez@xxxxxxxxxxxxx
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
.

Relevant Pages

  • Re: reducing the factorization decision problem to SAT?
    ... simple way in practice for integer factorization? ... If anyone knows how to reduce factorization ... That is, the output of the whole circuit is the output of this AND gate, ... something that decides SAT without providing satisfying assignments, ...
    (comp.theory)
  • Re: reducing the factorization decision problem to SAT?
    ... simple way in practice for integer factorization? ... If anyone knows how to reduce factorization ... That is, the output of the whole circuit is the output of this AND gate, ... something that decides SAT without providing satisfying assignments, ...
    (comp.theory)
  • reducing the factorization decision problem to SAT?
    ... It's obviously possible to reduce an NP decision problem to SAT using ... Cook-Levin's mapping, but how does one do it in an "intelligible," ... simple way in practice for integer factorization? ... (Or any other decision problem that the factorization ...
    (comp.theory)
  • factorization an NP problem (dont see it)
    ... factorization as a decision problem: given a composite integer m and ... if this can be done for all intergers upto k in polynomial time O, ...
    (sci.math)