Factoring numbers with boolean algebra: public domain source code
in [Cryptography]
|
From: Willow on 5 Nov 2009 23:37 Hi, I recently finished a program that factors the product of two unequal prime numbers using boolean algebra. You can find the source here: http://vm64dec.googlecode.com/files/unmultiply.cpp It is currently demonstrated factoring a 24-bit number with these properties: 1. The product (call it C) is known and is 24 bits 2. Each prime number fits in 12 bits (call them A and B) 3. The prime numbers are not equal. In particular, the low x bits of A and B are equal but A[x] (bit x of A) is 1 and B[x] is 0. We have to know x in advance - presently it's hardwired to bit 7 but it can be changed. It's possible to modify the program to brute force this bit, this can be done with an extra for loop. If W is the width of A and B (so that C has width 2W) then this would require W trials. However, for large W, each trial will take a long time. 4. If C = A * B then we can recover both A and B using boolean algebra. It really works! It factors the product of 3571 and 3187 (two small primes that fit in 12 bits each). It has good spatial complexity. I tried it with the same prime numbers, but using a 32-bit word size instead of 12 bit word size and it took too long (plus I'm impatient). Does anyone out there care to factor other numbers or care to speculate about how this approach compares to the current state-of- the- art for factoring? It CAN factor 4096-bit numbers, it would simply take a LOONGGG time. As for how long, that depends on the complexity. I think I have an exponential-time algorithm here, but I can't prove it. I don't think it's faster than brute force, but it is possible to speed this up with more intelligence, whereas brute force is so dumb it can't be sped up. Please see the source code at the above link for full details. It's hereby released into the public domain. Basically, here is how it works: I express multiplication using ANDs and XORs (actually a generalized logic gate of the form y = c0 ^ c1 x1 ^ c2 x2 ^ c12 x1 x2). Then I create a system of nonlinear, discrete equations such that for the correct (A,B) values plugged in, each equation evaluates to 1; if ANY key bits we guess are wrong, then at least one of these equations will evaluate to 0. In particular, I might try A[0] = 0. If this is wrong, then an equation will not only evaluate to 0, but it will be an identity for 0 leading to 0 = 1 and thus a logical contradiction. Once a logical contradiction is detected, I know that, since there's one unique solution (as A and B are different and we know one of their bits for which A[x] = 1 but B[x] = 0; A[i] = B[i] for i < x), the trial bit must be the opposite of what we tried. In theory you can use the distributive property to tell whether or not an expression that is a function of A and B bits is an identity for 0 (i.e. if we tried A[0] = 0 when in fact A[0] = 1), or if it isn't an identity for 0. We can't say anything at all if it is NOT an identity for zero. Mathematically, each equation has a solution set. The intersection is the empty set if any equations are 0 = 1 (identity). That tells us there are no solutions, so we can choose A[0] = 1 if we tried A[0] = 0. Once we know A[0], we move on to deduce B[0]. It's easy and fast. But when it comes time to deduce A[1], the distributive property has bad spatial complexity. In principle, for instance, we might be faced with a graph that expands to more nodes than fits in a 'double' (C data type). After such a thing is expanded, if you cross off duplicates, you will either have 0 or 1. But I discovered some shortcuts to speed it up. You can plug in 0's for all key bits (A or B) that remain unknown. You can then tell whether the equation is odd or even (+1 in expanded/simplified form). If it's odd, it can't be an identity for 0. If it's even, you have to try e.g. a[1] = 1 and see if there's a logical contradiction or not, then try a[1] = 0. If there's a logical contradiction for both of these trials, then the system is inconsistent and has no solutions, i.e. is in fact an identity for 0. Is anyone interested in this? I can explain it more if you like.... Willow P.S. Sorry to post this in several newsgroups, but sci.crypt.research is apparently moderated.
From: Enrico on 6 Nov 2009 00:17 On Nov 5, 9:37 pm, Willow <wrschlan...(a)gmail.com> wrote: > Hi, > I recently finished a program that factors the product of two unequal > prime numbers using boolean algebra. > > You can find the source here:http://vm64dec.googlecode.com/files/unmultiply.cpp > > It is currently demonstrated factoring a 24-bit number with these > properties: > 1. The product (call it C) is known and is 24 bits > 2. Each prime number fits in 12 bits (call them A and B) > 3. The prime numbers are not equal. > In particular, the low x bits of A and B are equal but A[x] (bit x > of A) is 1 and B[x] is 0. > We have to know x in advance - presently it's hardwired to bit 7 > but it can be changed. > It's possible to modify the program to brute force this bit, this > can be done with an extra for loop. > If W is the width of A and B (so that C has width 2W) then this > would require W trials. However, for large > W, each trial will take a long time. > 4. If C = A * B then we can recover both A and B using boolean > algebra. > > It really works! It factors the product of 3571 and 3187 (two small > primes that fit in 12 bits each). > It has good spatial complexity. > I tried it with the same prime numbers, but using a 32-bit word size > instead of 12 bit word size and it took too long (plus I'm impatient). > > Does anyone out there care to factor other numbers or care to > speculate about how this approach compares to the current state-of- > the- > art for factoring? It CAN factor 4096-bit numbers, it would simply > take a LOONGGG time. As for how long, that depends on the complexity. > I think I have an exponential-time algorithm here, but I can't prove > it. I don't think it's faster than brute force, but it is possible to > speed this up with more intelligence, whereas brute force is so dumb > it can't be sped up. > > Please see the source code at the above link for full details. It's > hereby released into the public domain. > > Basically, here is how it works: > I express multiplication using ANDs and XORs (actually a generalized > logic gate of the form y = c0 ^ c1 x1 ^ c2 x2 ^ c12 x1 x2). Then I > create a system of nonlinear, discrete equations such that for the > correct (A,B) values plugged in, each equation evaluates to 1; if ANY > key bits we guess are wrong, then at least one of these equations will > evaluate to 0. In particular, I might try A[0] = 0. If this is wrong, > then an equation will not only evaluate to 0, but it will be an > identity for 0 leading to 0 = 1 and thus a logical contradiction. > > Once a logical contradiction is detected, I know that, since there's > one unique solution (as A and B are different and we know one of their > bits for which A[x] = 1 but B[x] = 0; A[i] = B[i] for i < x), the > trial bit must be the opposite of what we tried. > > In theory you can use the distributive property to tell whether or not > an expression that is a function of A and B bits is an identity for 0 > (i.e. if we tried A[0] = 0 when in fact A[0] = 1), or if it isn't an > identity for 0. We can't say anything at all if it is NOT an identity > for zero. > > Mathematically, each equation has a solution set. The intersection is > the empty set if any equations are 0 = 1 (identity). That tells us > there are no solutions, so we can choose A[0] = 1 if we tried A[0] = > 0. Once we know A[0], we move on to deduce B[0]. It's easy and fast. > > But when it comes time to deduce A[1], the distributive property has > bad spatial complexity. In principle, for instance, we might be faced > with a graph that expands to more nodes than fits in a 'double' (C > data type). After such a thing is expanded, if you cross off > duplicates, you will either have 0 or 1. > > But I discovered some shortcuts to speed it up. You can plug in 0's > for all key bits (A or B) that remain unknown. You can then tell > whether the equation is odd or even (+1 in expanded/simplified form). > > If it's odd, it can't be an identity for 0. If it's even, you have to > try e.g. a[1] = 1 and see if there's a logical contradiction or not, > then try a[1] = 0. If there's a logical contradiction for both of > these trials, then the system is inconsistent and has no solutions, > i.e. is in fact an identity for 0. > > Is anyone interested in this? I can explain it more if you like.... > > Willow > P.S. Sorry to post this in several newsgroups, but sci.crypt.research > is apparently moderated. =================================================== I'd need to look at details of the theory plus some examples to get an idea how it works. A few years back, I tried to build factors of an odd composite one bit at a time, from right to left, keeping track of all valid bit patterns. I ran into some very involuted Xor functions and got swamped by the rapidly rising number of bit patterns that had to be saved and checked. I'm curious how you approached this. What's a .cpp file? C programming language? Do you have a text file description? Enrico
From: Willow on 6 Nov 2009 00:57 On Nov 5, 9:17 pm, Enrico <ungerne...(a)aol.com> wrote: > On Nov 5, 9:37 pm, Willow <wrschlan...(a)gmail.com> wrote: > > > > > Hi, > > I recently finished a program that factors the product of two unequal > > prime numbers using boolean algebra. > > > You can find the source here:http://vm64dec.googlecode.com/files/unmultiply.cpp > > > It is currently demonstrated factoring a 24-bit number with these > > properties: > > 1. The product (call it C) is known and is 24 bits > > 2. Each prime number fits in 12 bits (call them A and B) > > 3. The prime numbers are not equal. > > In particular, the low x bits of A and B are equal but A[x] (bit x > > of A) is 1 and B[x] is 0. > > We have to know x in advance - presently it's hardwired to bit 7 > > but it can be changed. > > It's possible to modify the program to brute force this bit, this > > can be done with an extra for loop. > > If W is the width of A and B (so that C has width 2W) then this > > would require W trials. However, for large > > W, each trial will take a long time. > > 4. If C = A * B then we can recover both A and B using boolean > > algebra. > > > It really works! It factors the product of 3571 and 3187 (two small > > primes that fit in 12 bits each). > > It has good spatial complexity. > > I tried it with the same prime numbers, but using a 32-bit word size > > instead of 12 bit word size and it took too long (plus I'm impatient). > > > Does anyone out there care to factor other numbers or care to > > speculate about how this approach compares to the current state-of- > > the- > > art for factoring? It CAN factor 4096-bit numbers, it would simply > > take a LOONGGG time. As for how long, that depends on the complexity. > > I think I have an exponential-time algorithm here, but I can't prove > > it. I don't think it's faster than brute force, but it is possible to > > speed this up with more intelligence, whereas brute force is so dumb > > it can't be sped up. > > > Please see the source code at the above link for full details. It's > > hereby released into the public domain. > > > Basically, here is how it works: > > I express multiplication using ANDs and XORs (actually a generalized > > logic gate of the form y = c0 ^ c1 x1 ^ c2 x2 ^ c12 x1 x2). Then I > > create a system of nonlinear, discrete equations such that for the > > correct (A,B) values plugged in, each equation evaluates to 1; if ANY > > key bits we guess are wrong, then at least one of these equations will > > evaluate to 0. In particular, I might try A[0] = 0. If this is wrong, > > then an equation will not only evaluate to 0, but it will be an > > identity for 0 leading to 0 = 1 and thus a logical contradiction. > > > Once a logical contradiction is detected, I know that, since there's > > one unique solution (as A and B are different and we know one of their > > bits for which A[x] = 1 but B[x] = 0; A[i] = B[i] for i < x), the > > trial bit must be the opposite of what we tried. > > > In theory you can use the distributive property to tell whether or not > > an expression that is a function of A and B bits is an identity for 0 > > (i.e. if we tried A[0] = 0 when in fact A[0] = 1), or if it isn't an > > identity for 0. We can't say anything at all if it is NOT an identity > > for zero. > > > Mathematically, each equation has a solution set. The intersection is > > the empty set if any equations are 0 = 1 (identity). That tells us > > there are no solutions, so we can choose A[0] = 1 if we tried A[0] = > > 0. Once we know A[0], we move on to deduce B[0]. It's easy and fast. > > > But when it comes time to deduce A[1], the distributive property has > > bad spatial complexity. In principle, for instance, we might be faced > > with a graph that expands to more nodes than fits in a 'double' (C > > data type). After such a thing is expanded, if you cross off > > duplicates, you will either have 0 or 1. > > > But I discovered some shortcuts to speed it up. You can plug in 0's > > for all key bits (A or B) that remain unknown. You can then tell > > whether the equation is odd or even (+1 in expanded/simplified form). > > > If it's odd, it can't be an identity for 0. If it's even, you have to > > try e.g. a[1] = 1 and see if there's a logical contradiction or not, > > then try a[1] = 0. If there's a logical contradiction for both of > > these trials, then the system is inconsistent and has no solutions, > > i.e. is in fact an identity for 0. > > > Is anyone interested in this? I can explain it more if you like.... > > > Willow > > P.S. Sorry to post this in several newsgroups, but sci.crypt.research > > is apparently moderated. > > =================================================== > > I'd need to look at details of the theory plus some examples > to get an idea how it works. > > A few years back, I tried to build factors of an odd composite > one bit at a time, from right to left, keeping track of all valid > bit patterns. I ran into some very involuted Xor functions and > got swamped by the rapidly rising number of bit patterns that > had to be saved and checked. > > I'm curious how you approached this. > > What's a .cpp file? C programming language? > Do you have a text file description? > > Enrico CPP files are C++ programming language files. We don't speak the same programming language but the system of nonlinear equations shown below is solvable. It's just boolean algebra. + means XOR, multiplication means and. a1, b1, etc. are unknown bits (we know a0 = b0 = 1 already). Also we know a7 = 1 and b7 = 0 because we guessed that bit. Now given such a system of equations, I basically try a1 = 0 and a1 = 1. If any of the equations at the bottom (the ones whose value is known) becomes an identity for 0 = 1 then I know there are no solutions - there's a logical contradiction - so we can be sure the opposite value is to be used. Willow s63 = a1 b1 + 0 s64 = a2 b1 + 0 s65 = a3 b1 + 0 s66 = a4 b1 + 0 s67 = a5 b1 + 0 s68 = a6 b1 + 0 s70 = a8 b1 + 0 s71 = a9 b1 + 0 s72 = a10 b1 + 0 s75 = a1 b2 + 0 s76 = a2 b2 + 0 s77 = a3 b2 + 0 s78 = a4 b2 + 0 s79 = a5 b2 + 0 s80 = a6 b2 + 0 s82 = a8 b2 + 0 s83 = a9 b2 + 0 s87 = a1 b3 + 0 s88 = a2 b3 + 0 s89 = a3 b3 + 0 s90 = a4 b3 + 0 s91 = a5 b3 + 0 s92 = a6 b3 + 0 s94 = a8 b3 + 0 s99 = a1 b4 + 0 s100 = a2 b4 + 0 s101 = a3 b4 + 0 s102 = a4 b4 + 0 s103 = a5 b4 + 0 s104 = a6 b4 + 0 s111 = a1 b5 + 0 s112 = a2 b5 + 0 s113 = a3 b5 + 0 s114 = a4 b5 + 0 s115 = a5 b5 + 0 s116 = a6 b5 + 0 s123 = a1 b6 + 0 s124 = a2 b6 + 0 s125 = a3 b6 + 0 s126 = a4 b6 + 0 s127 = a5 b6 + 0 s147 = a1 b8 + 0 s148 = a2 b8 + 0 s149 = a3 b8 + 0 s159 = a1 b9 + 0 s160 = a2 b9 + 0 s171 = a1 b10 + 0 s198 = a1 1 + b1 s200 = a1 b1 + 0 s202 = a2 1 + s63 s203 = s202 s200 + 0 s204 = a2 s63 + s203 s205 = s202 1 + s200 s206 = a3 1 + s64 s207 = s206 s204 + 0 s208 = a3 s64 + s207 s209 = s206 1 + s204 s210 = a4 1 + s65 s211 = s210 s208 + 0 s212 = a4 s65 + s211 s213 = s210 1 + s208 s214 = a5 1 + s66 s215 = s214 s212 + 0 s216 = a5 s66 + s215 s217 = s214 1 + s212 s218 = a6 1 + s67 s219 = s218 s216 + 0 s220 = a6 s67 + s219 s221 = s218 1 + s216 s222 = 1 1 + s68 s223 = s222 s220 + 0 s224 = 1 s68 + s223 s225 = s222 1 + s220 s226 = a8 1 + b1 s227 = s226 s224 + 0 s228 = a8 b1 + s227 s229 = s226 1 + s224 s230 = a9 1 + s70 s231 = s230 s228 + 0 s232 = a9 s70 + s231 s233 = s230 1 + s228 s234 = a10 1 + s71 s235 = s234 s232 + 0 s236 = a10 s71 + s235 s237 = s234 1 + s232 s238 = a11 1 + s72 s241 = s238 1 + s236 s298 = s205 1 + b2 s300 = s205 b2 + 0 s302 = s209 1 + s75 s303 = s302 s300 + 0 s304 = s209 s75 + s303 s305 = s302 1 + s300 s306 = s213 1 + s76 s307 = s306 s304 + 0 s308 = s213 s76 + s307 s309 = s306 1 + s304 s310 = s217 1 + s77 s311 = s310 s308 + 0 s312 = s217 s77 + s311 s313 = s310 1 + s308 s314 = s221 1 + s78 s315 = s314 s312 + 0 s316 = s221 s78 + s315 s317 = s314 1 + s312 s318 = s225 1 + s79 s319 = s318 s316 + 0 s320 = s225 s79 + s319 s321 = s318 1 + s316 s322 = s229 1 + s80 s323 = s322 s320 + 0 s324 = s229 s80 + s323 s325 = s322 1 + s320 s326 = s233 1 + b2 s327 = s326 s324 + 0 s328 = s233 b2 + s327 s329 = s326 1 + s324 s330 = s237 1 + s82 s331 = s330 s328 + 0 s332 = s237 s82 + s331 s333 = s330 1 + s328 s334 = s241 1 + s83 s337 = s334 1 + s332 s398 = s305 1 + b3 s400 = s305 b3 + 0 s402 = s309 1 + s87 s403 = s402 s400 + 0 s404 = s309 s87 + s403 s405 = s402 1 + s400 s406 = s313 1 + s88 s407 = s406 s404 + 0 s408 = s313 s88 + s407 s409 = s406 1 + s404 s410 = s317 1 + s89 s411 = s410 s408 + 0 s412 = s317 s89 + s411 s413 = s410 1 + s408 s414 = s321 1 + s90 s415 = s414 s412 + 0 s416 = s321 s90 + s415 s417 = s414 1 + s412 s418 = s325 1 + s91 s419 = s418 s416 + 0 s420 = s325 s91 + s419 s421 = s418 1 + s416 s422 = s329 1 + s92 s423 = s422 s420 + 0 s424 = s329 s92 + s423 s425 = s422 1 + s420 s426 = s333 1 + b3 s427 = s426 s424 + 0 s428 = s333 b3 + s427 s429 = s426 1 + s424 s430 = s337 1 + s94 s433 = s430 1 + s428 s498 = s405 1 + b4 s500 = s405 b4 + 0 s502 = s409 1 + s99 s503 = s502 s500 + 0 s504 = s409 s99 + s503 s505 = s502 1 + s500 s506 = s413 1 + s100 s507 = s506 s504 + 0 s508 = s413 s100 + s507 s509 = s506 1 + s504 s510 = s417 1 + s101 s511 = s510 s508 + 0 s512 = s417 s101 + s511 s513 = s510 1 + s508 s514 = s421 1 + s102 s515 = s514 s512 + 0 s516 = s421 s102 + s515 s517 = s514 1 + s512 s518 = s425 1 + s103 s519 = s518 s516 + 0 s520 = s425 s103 + s519 s521 = s518 1 + s516 s522 = s429 1 + s104 s523 = s522 s520 + 0 s524 = s429 s104 + s523 s525 = s522 1 + s520 s526 = s433 1 + b4 s529 = s526 1 + s524 s598 = s505 1 + b5 s600 = s505 b5 + 0 s602 = s509 1 + s111 s603 = s602 s600 + 0 s604 = s509 s111 + s603 s605 = s602 1 + s600 s606 = s513 1 + s112 s607 = s606 s604 + 0 s608 = s513 s112 + s607 s609 = s606 1 + s604 s610 = s517 1 + s113 s611 = s610 s608 + 0 s612 = s517 s113 + s611 s613 = s610 1 + s608 s614 = s521 1 + s114 s615 = s614 s612 + 0 s616 = s521 s114 + s615 s617 = s614 1 + s612 s618 = s525 1 + s115 s619 = s618 s616 + 0 s620 = s525 s115 + s619 s621 = s618 1 + s616 s622 = s529 1 + s116 s625 = s622 1 + s620 s698 = s605 1 + b6 s700 = s605 b6 + 0 s702 = s609 1 + s123 s703 = s702 s700 + 0 s704 = s609 s123 + s703 s705 = s702 1 + s700 s706 = s613 1 + s124 s707 = s706 s704 + 0 s708 = s613 s124 + s707 s709 = s706 1 + s704 s710 = s617 1 + s125 s711 = s710 s708 + 0 s712 = s617 s125 + s711 s713 = s710 1 + s708 s714 = s621 1 + s126 s715 = s714 s712 + 0 s716 = s621 s126 + s715 s717 = s714 1 + s712 s718 = s625 1 + s127 s721 = s718 1 + s716 s898 = s709 1 + b8 s900 = s709 b8 + 0 s902 = s713 1 + s147 s903 = s902 s900 + 0 s904 = s713 s147 + s903 s905 = s902 1 + s900 s906 = s717 1 + s148 s907 = s906 s904 + 0 s908 = s717 s148 + s907 s909 = s906 1 + s904 s910 = s721 1 + s149 s913 = s910 1 + s908 s998 = s905 1 + b9 s1000 = s905 b9 + 0 s1002 = s909 1 + s159 s1003 = s1002 s1000 + 0 s1004 = s909 s159 + s1003 s1005 = s1002 1 + s1000 s1006 = s913 1 + s160 s1009 = s1006 1 + s1004 s1098 = s1005 1 + b10 s1100 = s1005 b10 + 0 s1102 = s1009 1 + s171 s1105 = s1102 1 + s1100 1 = c0 = s1157 = 1 1 + 0 0 = c1 = s1161 = s198 1 + 0 0 = c2 = s1165 = s298 1 + 0 1 = c3 = s1169 = s398 1 + 0 0 = c4 = s1173 = s498 1 + 0 1 = c5 = s1177 = s598 1 + 0 0 = c6 = s1181 = s698 1 + 0 0 = c7 = s1185 = s705 1 + 0 0 = c8 = s1189 = s898 1 + 0 0 = c9 = s1193 = s998 1 + 0 0 = c10 = s1197 = s1098 1 + 0 s1198 = s1105 1 + b11 1 = c11 = s1201 = s1198 1 + 0
From: Willow on 6 Nov 2009 16:20 On Nov 5, 9:17 pm, Enrico <ungerne...(a)aol.com> wrote: > =================================================== > > I'd need to look at details of the theory plus some examples > to get an idea how it works. > > A few years back, I tried to build factors of an odd composite > one bit at a time, from right to left, keeping track of all valid > bit patterns. I ran into some very involuted Xor functions and > got swamped by the rapidly rising number of bit patterns that > had to be saved and checked. > > I'm curious how you approached this. > > What's a .cpp file? C programming language? > Do you have a text file description? > > Enrico I will describe the theory here. Basically, we have 3 numbers: A, B, C. We know C; in particular C = A * B and we want to recover A and B. Now A and B each have w bits and are unsigned numbers; C has 2w bits. Let 0 <= x < w be a number such that A[i] = B[i] for i < x and such that A[x] = 1 but B[x] = 0. Since there are only w possible values for x, we can brute force x. Now we can use boolean algebra (such as XOR's and AND's) to express C as a function of A and B. This can be written as C_i = C_i(A, B) with 0 <= i < w. So we have w equations of the form C_i = C_i(A, B). For instance we have C_0 = A_0 B_0. C_i for i > 0 are more complex. One trick we need is: each C_i can make use of substitutions, i.e. we can define intermediate variables S_0, S_1, S_2, etc. that are also functions of A and B bits. We can then refer to the S_i bits. Now if x = 0, we know A_0 and B_0. Otherwise, we know A_0 = B_0. So from C_0 = A_0 B_0 we really have C_0 = A_0 = B_0 if x > 0. In that case, we can easily recover A_0 and B_0 when needed. Now given our 'w' equations, we have the task of identifying A_j and B_i for j > 0, i > 0. This can be done by making a set of unknown (A, B) "key" bits. We can then pick an element from the set, and replace it in the directed acyclic graph that represents our system of nonlinear discrete equations, with 0. If ANY equation that results becomes an identity for 0 = 1 or 1 = 0 then we know we have to pick the opposite value, namely 1. If we plug in 1 and ANY equation becomes an identity for 0 = 1 or 1 = 0, then we know that key bit has a value of 0. In short, this is a constraint solver. We have to ask the following question about a system of nonlinear discrete (i.e. each unknown variable is 0 or 1) equations: is its solution set the empty set? In particular, given a simultaneous system of equations, each equation has a solution set; the intersection of the sets is the set of values that solves the system of equations. This is the set of A, B values that works here. To simplify matters, we know A[x] = 1 and B[x] = 0. This distinguishes between A and B and avoids there being two possible values for A and B. There is a way around this, but I didn't implement it. So it boils down to this: given a system of equations, can you tell whether or not ANY equation has an empty solution set? Consider for instance this set of equations: 1 = a 1 = b 1 = a + b + ab Is that a logical contradiction? To find out we solve the constraints using backtracking and a heuristic. The heuristic is simply: if the equation is odd (i.e. plugging in 0 for all key bits that are still unknown and not yet being tried equal to a particular value) then it cannot be an identity for 0. Let's plug in a = 0: 1 = 0 1 = b 1 = b The first line is a logical contradiction. We then have to try a = 1. 1 = 1 1 = b 1 = b + b A human can tell there's a contradiction at this point (everything here is modular two arithmetic). How can a computer program tell the third equation is false? By recursively applying the heuristic. First of all, is the third equation odd or even? It's even (try b = 0 and evaluate). Now is it a function of anything? It is a potential function of b. So we take 1 = b + b and try b = 0 1 = 0 + 0 = 0 then try b = 1 1 = 1 + 1 = 0 Since we get a logical contradiction for BOTH b = 0 and b = 1, we know 1 = b + b is the same as 1 = 0 and thus has no solutions. Willow
From: Enrico on 6 Nov 2009 17:48
On Nov 6, 2:20 pm, Willow <wrschlan...(a)gmail.com> wrote: > On Nov 5, 9:17 pm, Enrico <ungerne...(a)aol.com> wrote: > > > > > > > =================================================== > > > I'd need to look at details of the theory plus some examples > > to get an idea how it works. > > > A few years back, I tried to build factors of an odd composite > > one bit at a time, from right to left, keeping track of all valid > > bit patterns. I ran into some very involuted Xor functions and > > got swamped by the rapidly rising number of bit patterns that > > had to be saved and checked. > > > I'm curious how you approached this. > > > What's a .cpp file? C programming language? > > Do you have a text file description? > > > Enrico > > I will describe the theory here. Basically, we have 3 numbers: A, B, > C. We know C; in particular C = A * B and we want to recover A and B. > Now A and B each have w bits and are unsigned numbers; C has 2w bits. > Let 0 <= x < w be a number such that A[i] = B[i] for i < x and such > that A[x] = 1 but B[x] = 0. Since there are only w possible values for > x, we can brute force x. > > Now we can use boolean algebra (such as XOR's and AND's) to express C > as a function of A and B. This can be written as C_i = C_i(A, B) with > 0 <= i < w. > > So we have w equations of the form C_i = C_i(A, B). For instance we > have C_0 = A_0 B_0. C_i for i > 0 are more complex. > One trick we need is: each C_i can make use of substitutions, i.e. we > can define intermediate variables S_0, S_1, S_2, etc. that are also > functions of A and B bits. We can then refer to the S_i bits. > > Now if x = 0, we know A_0 and B_0. Otherwise, we know A_0 = B_0. So > from C_0 = A_0 B_0 we really have C_0 = A_0 = B_0 if x > 0. In that > case, we can easily recover A_0 and B_0 when needed. > > Now given our 'w' equations, we have the task of identifying A_j and > B_i for j > 0, i > 0. This can be done by making a set of unknown (A, > B) "key" bits. We can then pick an element from the set, and replace > it in the directed acyclic graph that represents our system of > nonlinear discrete equations, with 0. If ANY equation that results > becomes an identity for 0 = 1 or 1 = 0 then we know we have to pick > the opposite value, namely 1. If we plug in 1 and ANY equation becomes > an identity for 0 = 1 or 1 = 0, then we know that key bit has a value > of 0. > > In short, this is a constraint solver. We have to ask the following > question about a system of nonlinear discrete (i.e. each unknown > variable is 0 or 1) equations: is its solution set the empty set? > > In particular, given a simultaneous system of equations, each equation > has a solution set; the intersection of the sets is the set of values > that solves the system of equations. This is the set of A, B values > that works here. > > To simplify matters, we know A[x] = 1 and B[x] = 0. This distinguishes > between A and B and avoids there being two possible values for A and > B. There is a way around this, but I didn't implement it. > > So it boils down to this: given a system of equations, can you tell > whether or not ANY equation has an empty solution set? Consider for > instance this set of equations: > > 1 = a > 1 = b > 1 = a + b + ab > > Is that a logical contradiction? To find out we solve the constraints > using backtracking and a heuristic. The heuristic is simply: if the > equation is odd (i.e. plugging in 0 for all key bits that are still > unknown and not yet being tried equal to a particular value) then it > cannot be an identity for 0. > > Let's plug in a = 0: > > 1 = 0 > 1 = b > 1 = b > > The first line is a logical contradiction. We then have to try a = 1. > > 1 = 1 > 1 = b > 1 = b + b > > A human can tell there's a contradiction at this point (everything > here is modular two arithmetic). How can a computer program tell the > third equation is false? > By recursively applying the heuristic. > First of all, is the third equation odd or even? It's even (try b = 0 > and evaluate). > Now is it a function of anything? It is a potential function of b. > > So we take > 1 = b + b > > and try b = 0 > 1 = 0 + 0 = 0 > then try b = 1 > 1 = 1 + 1 = 0 > > Since we get a logical contradiction for BOTH b = 0 and b = 1, we know > 1 = b + b is the same as 1 = 0 and thus has no solutions. > > Willow- Hide quoted text - > > - Show quoted text - =================================================== Are you sure this is right? You have: > > 1 = a > 1 = b > 1 = a + b + ab > with the product defined as the And operator, with + defined as the Exclusive Or operator with a = 1, b = 1, the equations become: 1 = 1 1 = 1 1 = 1 + 1 + 1 = 0 + 1 = 1 Still, this is at the level I'll need to get the general idea of how to set up and solve the set of equations. Using 4 bit values for A and B is probably a good starting point for me. The set of equations in your earlier posts just left me reeling in confusion - too much too soon. For programming, I use Excel Visual Basic. Gives an easy to use input / output area thats easy to modify. Enrico |