Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: Boolean algebra solver?

Expand Messages
  • Paul Leyland
    ... Unfortunately, people have been trying this approach, unsuccessfully so far, for quite a few years. If you make progress, it will be *very* interesting!
    Message 1 of 13 , May 31, 2004
    • 0 Attachment
      On Mon, 2004-05-31 at 12:49, Ron wrote:

      > Ha - that would be really neat Décio, if I had actually
      > discovered a new or novel method of doing something, but
      > considering my lack of background in math, the technique is
      > probably as old as the hills and I just don't know the correct
      > name for it.

      Unfortunately, people have been trying this approach, unsuccessfully so
      far, for quite a few years. If you make progress, it will be *very*
      interesting!

      > I guess what I've done is to transform the factoring problem into
      > a boolean satisfiability problem (SAT), but I thought factoring
      > was already known (or at least widely believed to be) a very
      > difficult problem - I guess "NP-Hard" is the way to describe it(?)
      > Since it should be trivial to transform the SAT equations (if
      > that's what they are) back into the product of two binary
      > polynomials, I would assume the transformation of these particular
      > equations is "isomorphic," if I understand the meaning of that
      > term correctly.

      You've shown that factoring is no harder than SAT, something that is
      moderately well-known.

      Factoring is clearly in NP. If you guess the factors of an integer, a
      polynomial time algorithm (multiplication takes (log n)^2 or better)
      will verify the guess. SAT is also in NP.

      What is not yet known is what complexity class factoring belongs to.
      It's possible it may be NP-complete or NP-hard. It's possible that it's
      in P. Until very recently primality testing wasn't known to be in P.


      Paul
    • Ron
      ... Hash: SHA1 I see. Thank you Paul, as well as Décio for saving me countless hours of unnecessarily wasted effort. As I understand it then, the real problem
      Message 2 of 13 , Jun 1, 2004
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:
        > What is not yet known is what complexity class factoring
        > belongs to.

        -----BEGIN PGP SIGNED MESSAGE-----
        Hash: SHA1

        I see. Thank you Paul, as well as Décio for saving me countless
        hours of unnecessarily wasted effort. As I understand it then, the
        real problem in this particular case would be to "reverse" the
        equations I mentioned so that the a's and b's are solved for in
        terms of the bits of the composite number to be factored rather
        than the way I show them? In other words, what I need (for
        example) is to convert equations like these:

        n1 = a1 ^ 1
        n2 = a1 ^ b1
        (Where n1 and n2 are binary bits of the composite number to be
        factored)

        Into something like this:

        a1 = n1 ^ 1
        b1 = n1 ^ n2 ^ 1

        I realize this is probably impossible in general, but if it *were*
        possible it would show that factoring is in P, right?

        Thanks,

        Ron

        -----BEGIN PGP SIGNATURE-----
        Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

        iQA/AwUBQL1FbhpqFjUCnHWBEQJV7ACg4+muUEwxKT/Mwx60WWW2w81Md1IAoO4S
        cL/ybm7yzzuaSm/X6gHDco6P
        =+2jM
        -----END PGP SIGNATURE-----
      • Milton Brown
        Sorry, what is the purpose of n1 = a1 ^ 1 and a1 = n1 ^ 1 ? Aren t these just n1 = a1 and a1 = n1 ? It would be helpful to explain these, or have
        Message 3 of 13 , Jun 2, 2004
        • 0 Attachment
          Sorry, what is the purpose of n1 = a1 ^ 1 and a1 = n1 ^ 1 ?
          Aren't these just n1 = a1 and a1 = n1 ?

          It would be helpful to explain these, or have your mathematics
          thought out more before posting.

          Thanks.

          Milton L. Brown
          miltbrown at earthlink.net
          miltbrown@...

          ----- Original Message -----
          From: "Ron" <Yaho6Hb3c@...>
          To: <primenumbers@yahoogroups.com>
          Sent: Tuesday, June 01, 2004 8:13 PM
          Subject: [PrimeNumbers] Re: Boolean algebra solver?


          --- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:
          > What is not yet known is what complexity class factoring
          > belongs to.

          -----BEGIN PGP SIGNED MESSAGE-----
          Hash: SHA1

          I see. Thank you Paul, as well as Décio for saving me countless
          hours of unnecessarily wasted effort. As I understand it then, the
          real problem in this particular case would be to "reverse" the
          equations I mentioned so that the a's and b's are solved for in
          terms of the bits of the composite number to be factored rather
          than the way I show them? In other words, what I need (for
          example) is to convert equations like these:

          n1 = a1 ^ 1
          n2 = a1 ^ b1
          (Where n1 and n2 are binary bits of the composite number to be
          factored)

          Into something like this:

          a1 = n1 ^ 1
          b1 = n1 ^ n2 ^ 1

          I realize this is probably impossible in general, but if it *were*
          possible it would show that factoring is in P, right?

          Thanks,

          Ron

          -----BEGIN PGP SIGNATURE-----
          Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

          iQA/AwUBQL1FbhpqFjUCnHWBEQJV7ACg4+muUEwxKT/Mwx60WWW2w81Md1IAoO4S
          cL/ybm7yzzuaSm/X6gHDco6P
          =+2jM
          -----END PGP SIGNATURE-----





          Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          The Prime Pages : http://www.primepages.org/


          Yahoo! Groups Links
        • David Cleaver
          ... No they are not. When he uses the ^ operator, he means the xor (exclusive or) operator. If you don t know about the xor operator, here s a quick tut: 0^0
          Message 4 of 13 , Jun 2, 2004
          • 0 Attachment
            Milton Brown wrote:
            >
            > Sorry, what is the purpose of n1 = a1 ^ 1 and a1 = n1 ^ 1 ?
            > Aren't these just n1 = a1 and a1 = n1 ?

            No they are not. When he uses the ^ operator, he means the xor (exclusive
            or) operator. If you don't know about the xor operator, here's a quick
            tut:
            0^0 = 0
            0^1 = 1
            1^0 = 1
            1^1 = 0
            So, what n1 = a1 ^ 1 basically means is if a1 is 0 then n1 is 1, and vice
            versa. HTH.

            -David C.

            >
            > It would be helpful to explain these, or have your mathematics
            > thought out more before posting.
            >
            > Thanks.
            >
            > Milton L. Brown
          • Ron
            ... Hash: SHA1 Justin asked me for a real life example of how this technique can be used to find factors, so at the risk of boring everyone else, I thought I d
            Message 5 of 13 , Jun 3, 2004
            • 0 Attachment
              -----BEGIN PGP SIGNED MESSAGE-----
              Hash: SHA1

              Justin asked me for a real life example of how this technique
              can be used to find factors, so at the risk of boring everyone
              else, I thought I'd post it here on the forum. Here is a sample
              Maple code snippet ('#' begins a comment) that illustrates the
              problem:

              n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

              c1:=a1*b1:
              c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):
              c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):
              c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):
              c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):

              eqn := {a1+b1 = 1,
              a2+a1*b1+b2+c1 = 1,
              a2*b1+a1*b2+c2 = 1,
              a2*b2+c3+c4 = 0,
              c5 = 0};

              solve(eqn,{a1,a2,b1,b2}); # <= Maple can't solve this

              # But the solution is:

              a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal
              b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

              # Where a=3 and b=5 are the factors of 15.

              Ron Dotson
              6/03/2004

              -----BEGIN PGP SIGNATURE-----
              Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

              iQA/AwUBQL97thpqFjUCnHWBEQIOeQCgpMXLFGkaEsNQ/nshYRRMxNVi3+8An3RQ
              20UaohAI3jTT0B9S1XCz0Fj2
              =Zgga
              -----END PGP SIGNATURE-----
            • Edwin Clark
              ... Actually one can solve the system eqn with Maple (in two ways): First way: (note in this case one has free variables b1,b2,c1,c4 so we allow them to be
              Message 6 of 13 , Jun 3, 2004
              • 0 Attachment
                On Thu, 3 Jun 2004, Ron wrote:

                >
                > n:= [0,0,1,1,1,1]:  # factor binary 001111 = decimal 15 = 3*5
                >
                > c1:=a1*b1:
                > c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):
                > c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):
                > c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):
                > c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):
                >
                > eqn := {a1+b1 = 1,
                > a2+a1*b1+b2+c1 = 1,
                > a2*b1+a1*b2+c2 = 1,
                > a2*b2+c3+c4 = 0,
                > c5 = 0};
                >
                > solve(eqn,{a1,a2,b1,b2});  # <= Maple can't solve this

                Actually one can solve the system eqn with Maple (in two ways):

                First way: (note in this case one has free variables b1,b2,c1,c4 so we
                allow them to be any of 0 or 1 and see what works)

                Sol:=solve(eqn);
                2
                Sol := {c5 = 0, a1 = -b1 + 1, a2 = b1 - b1 - b2 - c1 + 1,

                3 2
                c2 = -b1 + b1 + 2 b2 b1 + b1 c1 - b1 - b2 + 1,

                2 2
                c3 = -b2 b1 + b2 b1 + b2 + b2 c1 - b2 - c4, b1 = b1,

                b2 = b2, c1 = c1, c4 = c4}

                > for b1 from 0 to 1 do
                > for b2 from 0 to 1 do
                > for c1 from 0 to 1 do
                > for c4 from 0 to 1 do
                > a:=eval(a2*4+a1*2+1,Sol);
                > b:=eval(b2*4+b1*2+1,Sol);
                > if a*b = 15 then print(a,b); fi;
                > od;
                > od;
                > od;
                > od:




                Second way: Us msolve to solve modulo 2. It gives 5 solutions, but it can
                pick the one that works: (It may just be luck that this works?) Here's
                how:

                > eqn := {a1+b1 = 1,
                > a2+a1*b1+b2+c1 = 1,
                > a2*b1+a1*b2+c2 = 1,
                > a2*b2+c3+c4 = 0,
                > c5 = 0}:
                > Sol:=msolve(eqn,2);

                Sol := {c5 = 0, b1 = 1, a1 = 0, c2 = 1, c1 = 1, a2 = 0, b2 = 0,

                c3 = c4}, {c5 = 0, b1 = 1, a1 = 0, c2 = 1, c1 = 0, b2 = 1,

                a2 = 0, c3 = c4}, {c5 = 0, b1 = 1, a1 = 0, a2 = 1, c1 = 0,

                b2 = 0, c3 = c4, c2 = 0}, {c5 = 0, b1 = 1, a1 = 0, a2 = 1,

                c1 = 1, b2 = 1, c2 = 0, c3 = c4 + 1}, {c5 = 0, a1 = 1, c2 = 1,

                c1 = 1, a2 = 0, b2 = 0, c3 = c4, b1 = 0}

                > for i from 1 to nops([Sol]) do
                > a:=eval(a2*4+a1*2+1,Sol[i]);
                > b:=eval(b2*4+b1*2+1,Sol[i]);
                > if a*b = 15 then print(a,b); fi
                > od:

                5, 3

                I'm not sure why we don't also get 3,5 this way.

                --Edwin Clark


                >
                > # But the solution is:
                >
                > a2:=0: a1:=1:  # a0:=1, so that a= "011" binary = 3 decimal
                > b2:=1: b1:=0:  # a0:=1, so that b= "101" binary = 5 decimal
                >
                > # Where a=3 and b=5 are the factors of 15.
                >
                > Ron Dotson
                > 6/03/2004
                >
                > -----BEGIN PGP SIGNATURE-----
                > Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>
                >
                > iQA/AwUBQL97thpqFjUCnHWBEQIOeQCgpMXLFGkaEsNQ/nshYRRMxNVi3+8An3RQ
                > 20UaohAI3jTT0B9S1XCz0Fj2
                > =Zgga
                > -----END PGP SIGNATURE-----
                >
                >
                >
                >
                > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                > The Prime Pages : http://www.primepages.org/
                >
                >
                >
                >
                > Yahoo! Groups Sponsor
                > ADVERTISEMENT
                > click here
                > [rand=153996665]
                >
                > ________________________________________________________________________________
                > Yahoo! Groups Links
                > * To visit your group on the web, go to:
                > http://groups.yahoo.com/group/primenumbers/
                >  
                > * To unsubscribe from this group, send an email to:
                > primenumbers-unsubscribe@yahoogroups.com
                >  
                > * Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
                >
                >

                --
                ---------------------------------------------------------
                W. Edwin Clark, Math Dept, University of South Florida
                http://www.math.usf.edu/~eclark/
                ---------------------------------------------------------
              • Ron
                ... Hash: SHA1 Very perceptive Edwin. I didn t know we had any Maple users in this group. You are correct that if you copy/paste the following lines into a
                Message 7 of 13 , Jun 4, 2004
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, Edwin Clark <eclark@m...> wrote:
                  >
                  > Actually one can solve the system eqn with Maple (in two ways):
                  >

                  -----BEGIN PGP SIGNED MESSAGE-----
                  Hash: SHA1

                  Very perceptive Edwin. I didn't know we had any Maple users
                  in this group. You are correct that if you copy/paste the
                  following lines into a Maple worksheet:

                  c1:=a1*b1:
                  c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):
                  c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):
                  c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):
                  c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):
                  eqn := {a1+b1 = 1,
                  a2+a1*b1+b2+c1 = 1,
                  a2*b1+a1*b2+c2 = 1,
                  a2*b2+c3+c4 = 0,
                  c5 = 0}:
                  Sol:=msolve(eqn,2);

                  Maple provides the solutions immediately:
                  Sol := {a1 = 0, b1 = 1, a2 = 1, b2 = 0},
                  {a1 = 1, b1 = 0, a2 = 0, b2 = 1}

                  I should have used "msolve()" in my example instead of
                  "solve()." *However*, if you use the actual RSA-640 carry
                  definitions and equations (all 135MB of them!) instead of the
                  equations in this simple example, Maple's "msolve()" also fails.
                  If you don't include the carry definitions it fails immediately,
                  and if you include them it runs for awhile (hours) and then
                  terminates with an "Out of Memory" error while trying to expand
                  the carry definitions (if I recall correctly). If anyone wants
                  to try it themselves, you can download the carry definition file
                  (Carries.txt) and the equation file (equ.dat) as a single gzipped
                  tar file from:
                  http://snipurl.com/6uqu/rsa640.tar.gz

                  or as a Windows ZIP file from:
                  http://snipurl.com/6uqu/rsa640.zip

                  (They are both about 10MB in size)

                  To have Maple try to solve them, paste the following
                  into a Maple worksheet and execute it from the same directory
                  you unzipped "equ.dat" and "Carries.txt" into:

                  restart:
                  print("Reading Equations");
                  read "equ.dat":
                  print("Reading Carries");
                  read "Carries.txt":
                  print("Solving");
                  Sol:=msolve(equ,2);

                  Maybe it will work on a computer that's faster than
                  mine and has more RAM, but I doubt it. I have
                  an Athlon 1.1 GHz AMD processor with 1 GB RAM.

                  Ron Dotson
                  6/04/2004


                  -----BEGIN PGP SIGNATURE-----
                  Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

                  iQA/AwUBQMA8TRpqFjUCnHWBEQJCuACgiJx8iXGukS9pxZpbIsNBtwbRG5gAn29u
                  PVyC48adMZA1O0PDOq7aJfFL
                  =ulm/
                  -----END PGP SIGNATURE-----
                • Justin
                  Hi Ron, R Justin asked me for a real life example of how this technique R can be used to find factors, so at the risk of boring everyone R else, I thought
                  Message 8 of 13 , Jun 4, 2004
                  • 0 Attachment
                    Hi Ron,

                    R> Justin asked me for a real life example of how this technique
                    R> can be used to find factors, so at the risk of boring everyone
                    R> else, I thought I'd post it here on the forum. Here is a sample
                    R> Maple code snippet ('#' begins a comment) that illustrates the
                    R> problem:

                    Thanks Ron. I think I've finally understood the idea of the technique. I
                    also understand long-hand multiplication at long last ;)

                    R> n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

                    R> eqn := {a1+b1 = 1,
                    R> a2+a1*b1+b2+c1 = 1,
                    R> a2*b1+a1*b2+c2 = 1,
                    R> a2*b2+c3+c4 = 0,
                    R> c5 = 0};

                    As you know, these equations in the Z(2) field are equivalent to boolean
                    expressions. So they can be transformed the following way to eliminate the
                    equality:

                    lhs == 1 -> lhs
                    lhs == 0 -> NOT(lhs) -> lhs+1 (equivalent to NOT using only xor)

                    now all the ex-equations can be combined to one with AND (ie multiplication
                    in Z(2)) to form one expression:

                    (a1+b1) (a2+a1*b1+b2+c1) (a2*b1+a1*b2+c2) (a2*b2+c3+c4+1) (c5+1)

                    This can be reduced algebraically and transformed to boolean:

                    (a1 && b2 && ! a2 && ! b1) || (a2 && b1 && ! a1 && ! b2)

                    Which in effect is indeed your solution:

                    R> # But the solution is:

                    R> a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal
                    R> b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

                    R> # Where a=3 and b=5 are the factors of 15.


                    I use Mathematica, and am not familiar with Maple, but I suppose it is
                    just as capable of these transformations.

                    I'm not sure about the practicability though. It already took a few seconds
                    to reduce your example expressions (albeit with somewhat straightforward
                    and probably not really efficient reduction algorithm).

                    But then, what do I know? ;P

                    --
                    Justin
                    ICQ 37456745
                    AIM jasticle
                  Your message has been successfully submitted and would be delivered to recipients shortly.