Re: Integer factorization reduction to SAT

cplxphil@xxxxxxxxx wrote:


Hello,

Does anyone know if there is in existence an already-programmed
executable (for Windows, preferably) that reduces an instance of the
integer factorization problem to an instance of SAT? I posted on here
a while ago asking how to perform such a reduction, and someone was
kind enough to answer, but I do not know how to perform the reduction
myself. If anyone knows the location of any such program, I would
really appreciate it if someone could point me in the direction of
it. (There is something resembling one here (http://
www.is.titech.ac.jp/~watanabe/gensat/a2/), but it doesn't seem to
allow the user to enter a single integer and reduce the identity of
one of its factors to a decision problem.)

If anyone can help I'd really appreciate it.

-Phil

Hi,
a rough outline of the reduction is that :
we assume x = a*b, and a =a0a1a2a3...an,b=b0b1b2...bn
x=x0x1x2...x2n

Now create a non recurrent logic circuit of that multiplication.
then convert that logic circuit to sat.
assert x0,x1,x2...x2n to the correspondintg bits of the integer to be
factorized.
then start your favorite sat solver.
then extract a0,a1...an,b0,b1,...bn.

TK
.

Relevant Pages

  • Re: Integer factorization reduction to SAT
    ... integer factorization problem to an instance of SAT? ... but I do not know how to perform the reduction ... a rough outline of the reduction is that: ... I'm running Windows, could that be it? ...
    (comp.theory)
  • Re: Integer factorization reduction to SAT
    ... executable (for Windows, preferably) that reduces an instance of the ... integer factorization problem to an instance of SAT? ... but I do not know how to perform the reduction ... Now create a non recurrent logic circuit of that multiplication. ...
    (comp.theory)
  • Re: Integer factorization reduction to SAT
    ... Does anyone know if there is in existence an already-programmed ... executable (for Windows, preferably) that reduces an instance of the ... integer factorization problem to an instance of SAT? ... but I do not know how to perform the reduction ...
    (comp.theory)
  • Integer factorization reduction to SAT
    ... Does anyone know if there is in existence an already-programmed ... executable (for Windows, preferably) that reduces an instance of the ... integer factorization problem to an instance of SAT? ... but I do not know how to perform the reduction ...
    (comp.theory)