Re: reducing the factorization decision problem to SAT?

On Jul 16, 6:28 pm, djime...@xxxxxxxxxxxxx (Daniel A. Jimenez) wrote:
In article <73f0758f-8c5b-4682-803e-c509edcd9...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,



<cplxp...@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 djime...@xxxxxxxxxxxxx
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage


I think that is similar to the Cook-Levin mapping, isn't it? The
alternate version that deals with circuits instead of Turing
machines is what yours sounds like.

Is there any simpler algorithm, or is that the best that can be done?
I'm looking for the sort of algorithm that I would actually know how
to program in C++...

Thanks for the reply...I figure that is probably the best that can be
done. I wish that there were a simpler reduction.

-Phil
.

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?
    ... It's obviously possible to reduce an NP decision problem to SAT using ... (Or any other decision problem that the 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: Matrix is close to singular or badly scaled.
    ... % QR factorization ... and so when I put the same circuit in spice and obtain Y parameters, they are different from what i get from the above method. ... I know that SPICE circuit simulator also uses modified nodal analysis to convert a circuit to the 'A' matrix,but they must be doing some sort of scaling or other factorization methods. ... Please suggest some scaling techniques or methods to rearrange the A matrix so that it is not ill-conditioned /singular ...
    (comp.soft-sys.matlab)
  • Re: cubic equation - is it really solvable?
    ... >>> are trial and error methods where the number of trials is happily ... > BTW, the number of digits is not the problem, the integer factorization is. ... > If the first and last coefficients are easily factored, ...
    (sci.math)