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

Boolean algebra solver?

Expand Messages
  • Ron
    Does anyone know of a computer software package that will solve large systems of boolean equations in which everything is either 0 or 1? Though many in number,
    Message 1 of 13 , May 29, 2004
    • 0 Attachment
      Does anyone know of a computer software package that will solve large
      systems of boolean equations in which everything is either 0 or 1?
      Though many in number, the only operators used in the equations are
      either exclusive-or (^) or AND (&). For example, the system:

      a1 ^ b1 = 1
      a2 ^ a1&b1 ^ b2 ^ c1 = 0
      a2&b1 ^ a1&b2 ^ c2 = 0
      a2&b2 ^ c3 ^ c4 = 0
      c5 = 1

      Where:
      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))

      Has the solutions:
      (a1=1, a2=1, b1=0, b2=1) or (a1=0, a2=1, b1=1, b2=1)


      In actual practice, the ASCII files containing the equations and the
      c<n> definitions total well over 100 MB in size (a single c<n>
      definition can exceed 4 million ASCII characters!).

      Any suggestions?

      I'd hate to have to try to write such a solver system myself. I'm not
      even sure if it's even possible to solve systems of equations of the
      type and size I need(?)

      Thanks,

      Ron

      P.S.
      Yes, this has to do with factoring. ;-)

      P.P.S.
      I like to add my congratulations to the folks at GIMPS. I loved the
      prime number posters at:
      http://www.perfsci.com/novelties.htm#framed :-)
    • Décio Luiz Gazzoni Filho
      ... Hash: SHA1 ... OK, I may be wrong here, but isn t this related to (if not the same as) the famous SAT problem that S.A. Cook proved to be NP-complete in
      Message 2 of 13 , May 29, 2004
      • 0 Attachment
        -----BEGIN PGP SIGNED MESSAGE-----
        Hash: SHA1

        On Saturday 29 May 2004 10:33, you wrote:
        > Does anyone know of a computer software package that will solve large
        > systems of boolean equations in which everything is either 0 or 1?

        OK, I may be wrong here, but isn't this related to (if not the same as) the
        famous SAT problem that S.A. Cook proved to be NP-complete in 1971? Because
        in that case, if you have 100 MB of data to solve as you state below, I don't
        think it is going to be pratical.

        Just my 2 cents.

        > Though many in number, the only operators used in the equations are
        > either exclusive-or (^) or AND (&). For example, the system:
        >
        > a1 ^ b1 = 1
        > a2 ^ a1&b1 ^ b2 ^ c1 = 0
        > a2&b1 ^ a1&b2 ^ c2 = 0
        > a2&b2 ^ c3 ^ c4 = 0
        > c5 = 1
        >
        > Where:
        > 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))
        >
        > Has the solutions:
        > (a1=1, a2=1, b1=0, b2=1) or (a1=0, a2=1, b1=1, b2=1)
        >
        >
        > In actual practice, the ASCII files containing the equations and the
        > c<n> definitions total well over 100 MB in size (a single c<n>
        > definition can exceed 4 million ASCII characters!).
        >
        > Any suggestions?
        >
        > I'd hate to have to try to write such a solver system myself. I'm not
        > even sure if it's even possible to solve systems of equations of the
        > type and size I need(?)
        >
        > Thanks,
        >
        > Ron

        Décio
        -----BEGIN PGP SIGNATURE-----
        Version: GnuPG v1.2.4 (GNU/Linux)

        iD8DBQFAuKCcFXvAfvngkOIRAikJAJ9duj/8DKrZ6EaOzh0WjddCEuVfDQCePk/2
        lx748lpBKAdCNnrYy6tr1p4=
        =TQvr
        -----END PGP SIGNATURE-----
      • Ron
        ... Hash: SHA1 I just wanted to publicly thank Décio Luiz Gazzoni Filho for his insightful reply to my question and for suggesting that I look into the
        Message 3 of 13 , May 30, 2004
        • 0 Attachment
          -----BEGIN PGP SIGNED MESSAGE-----
          Hash: SHA1

          I just wanted to publicly thank Décio Luiz Gazzoni Filho for his
          insightful reply to my question and for suggesting that I look
          into the "famous SAT problem that S.A. Cook proved to be
          NP-complete in 1971." A Google search for that phrase turned up
          very enlightening links to (among other things)
          http://snipurl.com/6r72 which has a through explanation of the
          type of problem I'm trying to solve, as well as its level of
          difficulty.

          When I responded to Décio's public forum reply, I failed to notice
          that the default "Reply to" address is the individual poster
          rather than the entire forum, so my reply went directly to Décio
          via email who has since graciously responded with further
          clarification via private email to me off the list.

          In any case, the answer to Décio's question to me, is that I'm
          dealing with 640 binary variables in 640 equations. More
          specifically, I'm dealing with equations in which the
          right-hand-side values are the binary digits (0 or 1)
          of the RSA-640 challenge number at:
          http://www.rsasecurity.com/rsalabs/node.asp?id=2093#RSA640 ;-)

          Regards,

          Ron

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

          iQA/AwUBQLqmghpqFjUCnHWBEQI67wCdFpq3dffVVUYZRAWqYXb2+y4f2tsAoMh6
          H7uP5Q8rngazYg4AbZVyTujW
          =qP3W
          -----END PGP SIGNATURE-----
        • Décio Luiz Gazzoni Filho
          ... Hash: SHA1 ... Maybe you could share your method with the group. Maybe you have figured something novel, which allows someone else to work out a connection
          Message 4 of 13 , May 30, 2004
          • 0 Attachment
            -----BEGIN PGP SIGNED MESSAGE-----
            Hash: SHA1

            On Monday 31 May 2004 00:33, you wrote:
            > I just wanted to publicly thank Décio Luiz Gazzoni Filho for his
            > insightful reply to my question and for suggesting that I look
            > into the "famous SAT problem that S.A. Cook proved to be
            > NP-complete in 1971."

            Heh, it was no big deal, I just beat others to it (:

            > <snip>
            >
            > In any case, the answer to Décio's question to me, is that I'm
            > dealing with 640 binary variables in 640 equations. More
            > specifically, I'm dealing with equations in which the
            > right-hand-side values are the binary digits (0 or 1)
            > of the RSA-640 challenge number at:
            > http://www.rsasecurity.com/rsalabs/node.asp?id=2093#RSA640 ;-)

            Maybe you could share your method with the group. Maybe you have figured
            something novel, which allows someone else to work out a connection between
            SAT and factoring, thus evaluating the real difficulty of factoring from a
            complexity-theoretic point of view -- as far as I know, little is known in
            the way of which complexity class factoring belongs to, for instance.

            Décio
            -----BEGIN PGP SIGNATURE-----
            Version: GnuPG v1.2.4 (GNU/Linux)

            iD8DBQFAurzzFXvAfvngkOIRAjkaAJ4piGuyG9g9KL+NxLplkz3JDO0kcgCggvsA
            UiQRTOObpSuIdPkID1i7RnE=
            =YWx8
            -----END PGP SIGNATURE-----
          • Ron
            ... Hash: SHA1 ... 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
            Message 5 of 13 , May 31, 2004
            • 0 Attachment
              -----BEGIN PGP SIGNED MESSAGE-----
              Hash: SHA1

              > --- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
              > <decio@r...> wrote: Maybe you could share your method with
              > the group. Maybe you have figured something novel, which
              > allows someone else to work out a connection between SAT and
              > factoring, thus evaluating the real difficulty of factoring
              > from a complexity-theoretic point of view -- as far as I know,
              > little is known in the way of which complexity class factoring
              > belongs to, for instance.

              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.

              What I'm trying (unsuccessfully) to do, is to factor a number (or
              prove that it's prime) by solving the set of simultaneous
              equations formed by multiplying two binary polynomials (the
              factors I'm looking for) together and equating powers of two in
              the result with the powers of two in the composite number being
              factored (on a bitwise basis). It's difficult for me to describe
              without drawing pictures, but it was the most simple and direct
              way of factoring I could think of - and yet I haven't read
              anything about it in the books on factoring I've seen (most likely
              because the method doesn't work very well! ;-).

              For example, it takes a program written in Waterloo Maple only a
              few minutes to form the symbolic ASCII multiplication of two 320
              bit binary numbers (say a320,a319,...,a0 and b320,b319,...,b0.
              Note that a0 and b0 are already known to be = 1), provided that
              you put the carry terms into a separate file and don't try to
              expand them. Actually I suppose I should be using a larger number
              of bits to generate more variables and equations, say 328 bits
              each or so, to account for the possibility that one of the factors
              may be several binary orders of magnitude larger or smaller than
              the other. In any case, imagine doing "long-hand" multiplication
              so that you have columns of numbers (which INCLUDE the carry
              terms) all lined up, each column representing one binary digit
              (bit) of the composite challenge number. The vertical columns are
              your equations, and the right hand sides of the equations are the
              individual bits of the composite number. All you have to do is
              solve those equations, and you've found two of the factors of the
              composite number. In the case of the RSA Challenge numbers,
              they're guaranteed to have only two factors.

              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.

              Anyhow, it's a fun hobby to keep my mind occupied during
              retirement. :-)

              - -- Ron

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

              iQA/AwUBQLsavhpqFjUCnHWBEQJx2ACfRT4HCV6Gb1VFZnPoKF3hRoyY2h8AoIxw
              /iz0D8U+KCTqpZA/Lv3do/sw
              =1Ovx
              -----END PGP SIGNATURE-----
            • 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 6 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 7 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 8 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 9 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 10 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 11 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 12 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 13 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.