 |
| Constraint and Consequence |
|
|
 | |
| Craig Holman Research Jabberwocky Quotations Contact | |
Home >
Jabberwocky 
Previous
Next
|
|
| |
Jabberwocky for December 27, 2008 |
|
Factoring IntegersI'm going to ease back into regular posting by writing up some of my work on integer factoring. This is a beautiful problem that has interested me for decades. I included this problem in my post on Some favorite problems. The following problem description is an excerpt from that post: Problem - Factoring a composite integer into two integer factors We all know how to multiply two positive integers. Most of us can still do so without using a calculator. Given two positive integers X and Y, we know how to calculate X * Y = Z. What about the reverse operation? I don't mean division; I mean factoring. Give the equation X * Y = Z, we'll refer to Z as the 'product' of X and Y, and to X and Y as the 'factors' of Z. Remember that a positive integer is 'prime' if it is has no factors other than 1 and itself. 1 is not considered to be prime for technical reasons. The smallest prime number is 2. The factoring problem involves finding two factors X and Y of an integer Z greater than 1 such that X and Y are each greater than 1. If either X or Y are not prime, there is more than one way to factor Z into two factors. Think of factoring as reverse multiplication. Factoring 15 is pretty easy. We can do it in our heads: 15 = 3 * 5 . What about factoring 391? Not so easy. Its factors are 17 and 23, both of which are prime. What about factoring 356971? Not easy at all. Its factors are 487 and 733, both of which are prime. While multiplying two numbers is easy, factoring numbers is hard, and no one has found a very efficient algorithm for factoring numbers. The difficulty in factoring numbers has been taken advantage of in cryptography, where the secureness of some cryptographic methods is based upon the difficulty of factoring the product of two large primes into its prime factors. Where I'm heading Consider the equation X * Y = Z, where X, Y, and Z are integers greater than 1. This equation has a solution if and only if Z is not a prime number. I've always thought of this problem in terms of a system of constraints that can be solved by the exhaustive application of a complete set of simplifying transformations. If the system of constraints is consistent, Z is composite and the values of X and Y can be extracted from the resolved system of constraints; otherwise, Z is prime. My work on this problem has led me to believe that the factoring problem is in P, that an algorithm exists that can solve every instance of the factoring problem in polynomial time. I have not discovered this algorithm, but I have developed a framework which may lead to such an algorithm. A system of constraints It may sound strange to say that a single number, Z, induces a system of constraints, but it does so in the context of the equation, X * Y = Z, and the requirement that X, Y, and Z be integers greater than 1. Let's begin by considering the process of multiplication 11 and 13. In grade school, we learned to organize the calculation as follows: 29 : X x 11 : Y ___ 29 = 1 x 29 x 10^0 + 29 = 1 x 29 x 10^1 ___ 319 : Z While we're used to working in base 10, it can often simplify things to work instead in base 2. Here is the same problem written in base 2:
11101 : X
x 1011 : Y
_________
11101 = 1 x 11101 x 2^0
11101 = 1 x 11101 x 2^1
0 = 0 x 11101 x 2^2
+ 11101 = 1 x 11101 x 2^3
__________
100111111 : Z
I'll refer to the maximum factor as X and the minimum factor as Y. Some notation: I'll refer to the least significant (the right-most) digit of X as X0, the digit to its left as X1, and so on; similarly for Y and Z. The index may be written at the same level as the variable in diagrams. Observe how the multiplication problem is transformed into an addition problem. The carries aren't being displayed, but they are essential. The structure of the addition problem led me to approach this problem in terms of a grid of processing elements (processors), each of which represents the same set of logical functions. Row 0 is the top row and column 0 is the right-most column. The inputs/outputs of this grid are the bits of X, Y, and Z. Each processor has six connectors. The connectors for the processor in row i and column j are:
I'll represent a processor graphically as:
SI
| x
_|_/
| |-Y
| |
CO-|___|-CI
|
|
SO
A processor doesn't have inputs or outputs - it has connectors. If we momentarily regard SI, x, y, and CI as inputs, however, here is how the outputs SO and CO are calculated:
The connectors will be represented in a grid with a chain of '0' (constrained to 0), '1' (constrained to 1), or '?' (constraint not yet known). For example,
0 1
_0_1
| |11
| |
??|___|??
?
?
The relationships between these six connectors is defined by the following truth table, in which the State will be used refer to the set of values:
The set of constraints for the six connectors of a processor is the context of the processor. Some subset of the twelve possible states for a processor are consistent with the context of the processor. The elements of this subset may be written inside the rectangle representing the processor. For example,
0 1
_0_1
| 3|11
| 5 |
??|___|??
?
?
This machinery is overkill for multiplication, but it will be instructive to see what a grid for X = 29 and Y = 11
looks like before and after multiplication. This is the grid before multiplication - the bits of X have been
applied along the top of the grid and the bits of Y have been applied along the right of the grid:
X7 X6 X5 X4 X3 X2 X1 X0
0 0 0 1 1 1 0 1
__0__0 __0__0 __0__0 __0__1 __0__1 __0__1 __0__0 __0__1
| |1 | |1 | |1 | |1 | |1 | |1 | |1 | |11 Y0
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
??????|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|0
? ? ? ? ? ? ? ? 1
__?__0 __?__0 __?__0 __?__1 __?__1 __?__1 __?__0 __?__1 1
| |1 | |1 | |1 | |1 | |1 | |1 | |1 | |1111 1 1111 Y1
| | | | | | | | | | | | | | | | 1
| | | | | | | | | | | | | | | | 1
0|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|0 1
? ? ? ? ? ? ? ? 1
__?__0 __?__0 __?__1 __?__1 __?__1 __?__0 __?__1 ? 1
| |0 | |0 | |0 | |0 | |0 | |0 | |0000 ? 000000 1 0000 Y2
| | | | | | | | | | | | | | ? 1
| | | | | | | | | | | | | | ? 1
0|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|0 ? 1
? ? ? ? ? ? ? ? 1
__?__0 __?__1 __?__1 __?__1 __?__0 __?__1 ? ? 1
| |1 | |1 | |1 | |1 | |1 | |1111 ? 111111 ? 111111 1 1111 Y3
| | | | | | | | | | | | ? ? 1
| | | | | | | | | | | | ? ? 1
0|_____|??|_____|??|_____|??|_____|??|_____|??|_____|0 ? ? 1
? ? ? ? ? ? ? ? 1
? ? ? ? ? ? ? ? 1
Z8 Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0
This is the grid after multiplication -
constraints at the boundary of the grid have been propagated exhaustively until all constraint issues have been resolved:
X7 X6 X5 X4 X3 X2 X1 X0
0 0 0 1 1 1 0 1
__0__0 __0__0 __0__0 __0__1 __0__1 __0__1 __0__0 __0__1
| |1 | |1 | |1 | |1 | |1 | |1 | |1 | |11 Y0
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
000000|_____|00|_____|00|_____|00|_____|00|_____|00|_____|00|_____|00|_____|0
0 0 0 0 1 1 1 0 1
__0__0 __0__0 __0__0 __0__1 __1__1 __1__1 __1__0 __0__1 1
| |1 | |1 | |1 | |1 | |1 | |1 | |1 | |1111 1 1111 Y1
| | | | | | | | | | | | | | | | 1
| | | | | | | | | | | | | | | | 1
0|_____|00|_____|00|_____|11|_____|11|_____|11|_____|00|_____|00|_____|0 1
0 0 1 0 1 0 1 1 1
__0__0 __0__0 __1__1 __0__1 __1__1 __0__0 __1__1 1 1
| |0 | |0 | |0 | |0 | |0 | |0 | |0000 1 000000 1 0000 Y2
| | | | | | | | | | | | | | 1 1
| | | | | | | | | | | | | | 1 1
0|_____|00|_____|00|_____|00|_____|00|_____|00|_____|00|_____|0 1 1
0 0 1 0 1 0 1 1 1
__0__0 __0__1 __1__1 __0__1 __1__0 __0__1 1 1 1
| |1 | |1 | |1 | |1 | |1 | |1111 1 111111 1 111111 1 1111 Y3
| | | | | | | | | | | | 1 1 1
| | | | | | | | | | | | 1 1 1
0|_____|11|_____|11|_____|00|_____|00|_____|00|_____|0 1 1 1
1 0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1
Z8 Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0
In order to factor 319, the bits of 319 are applied to the bottom of the grid. This is the grid for factoring 319 prior to factoring.
X7 X6 X5 X4 X3 X2 X1 X0
? ? ? ? ? ? ? ?
__0__? __0__? __0__? __0__? __0__? __0__? __0__? __0__?
| |? | |? | |? | |? | |? | |? | |? | |?? Y0
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
??????|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|0
? ? ? ? ? ? ? ? 1
__?__? __?__? __?__? __?__? __?__? __?__? __?__? __?__? 1
| |? | |? | |? | |? | |? | |? | |? | |???? 1 ???? Y1
| | | | | | | | | | | | | | | | 1
| | | | | | | | | | | | | | | | 1
0|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|00 1
? ? ? ? ? ? ? 1 1
__?__? __?__? __?__? __?__? __?__? __?__? __?__? 1 1
| |? | |? | |? | |? | |? | |? | |???? 1 ?????? 1 ???? Y2
| | | | | | | | | | | | | | 1 1
| | | | | | | | | | | | | | 1 1
0|_____|??|_____|??|_____|??|_____|??|_____|??|_____|??|_____|00 1 1
? ? ? ? ? ? 1 1 1
__?__? __?__? __?__? __?__? __?__? __?__? 1 1 1
| |? | |? | |? | |? | |? | |???? 1 ?????? 1 ?????? 1 ???? Y3
| | | | | | | | | | | | 1 1 1
| | | | | | | | | | | | 1 1 1
|_____|??|_____|??|_____|??|_____|??|_____|??|_____|00 1 1 1
1 0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1
Z8 Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0
This is the grid after factoring. It is identical to the grid after multiplying 29 and 11.
X7 X6 X5 X4 X3 X2 X1 X0
0 0 0 1 1 1 0 1
__0__0 __0__0 __0__0 __0__1 __0__1 __0__1 __0__0 __0__1
| |1 | |1 | |1 | |1 | |1 | |1 | |1 | |11 Y0
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
000000|_____|00|_____|00|_____|00|_____|00|_____|00|_____|00|_____|00|_____|0
0 0 0 0 1 1 1 0 1
__0__0 __0__0 __0__0 __0__1 __1__1 __1__1 __1__0 __0__1 1
| |1 | |1 | |1 | |1 | |1 | |1 | |1 | |1111 1 1111 Y1
| | | | | | | | | | | | | | | | 1
| | | | | | | | | | | | | | | | 1
0|_____|00|_____|00|_____|11|_____|11|_____|11|_____|00|_____|00|_____|0 1
0 0 1 0 1 0 1 1 1
__0__0 __0__0 __1__1 __0__1 __1__1 __0__0 __1__1 1 1
| |0 | |0 | |0 | |0 | |0 | |0 | |0000 1 000000 1 0000 Y2
| | | | | | | | | | | | | | 1 1
| | | | | | | | | | | | | | 1 1
0|_____|00|_____|00|_____|00|_____|00|_____|00|_____|00|_____|0 1 1
0 0 1 0 1 0 1 1 1
__0__0 __0__1 __1__1 __0__1 __1__0 __0__1 1 1 1
| |1 | |1 | |1 | |1 | |1 | |1111 1 111111 1 111111 1 1111 Y3
| | | | | | | | | | | | 1 1 1
| | | | | | | | | | | | 1 1 1
0|_____|11|_____|11|_____|00|_____|00|_____|00|_____|0 1 1 1
1 0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1
Z8 Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0
So far, so good. We have a framework within which we can resolve a system of constraints, whether that system is initialized for multiplication or factoring. Multiplication is easy, however, and factoring is more difficult - how difficult is not yet known. This isn't surprising, since there are fewer bits in the boundary conditions for factoring than there are for multiplication. Fewer bits, but enough to solve the problem. We've got one leg to stand on, but we're going to need another one if we're to walk around. As with most things, I thought of this as a graph problem. I have found it helpful to maintain a graph in which nodes correspond to processor states and non-edges correspond to known incompatibilities. In other words, there is an edge between two nodes if those two states have not yet been proven to be incompatible. This graph will contain a group of nodes for each processor in the grid. Each processor has a set of possible states that is a subset of 12 states, so each group contains 12 nodes. The grid in our continuing example contains 29 processors, so its corresponding graph contains 348 nodes. If the graph contains a k-clique, where k is the number of processors, then the bits of the values of X and Y can be read from the processor/states that correspond to the nodes in the k-clique. If the graph contains only one k-clique, then both X and Y are prime. If the graph does not contain a k-clique, then Z is prime. Initially, each processor-associated group of nodes is an independent set - there are no edges between any of its nodes. Whenever a processor loses a possible state, the edges in the graph that are incident with the corresponding node are removed. Similarly, reduction operations within the graph may result in the lost of one or more states in the processor grid. Over the next several posts in this thread, I'll present some of the reductive transformations that can be applied to the processor grid and to the graph. |
| |
| Home >
Jabberwocky
Previous
Next
|
|
| Craig Holman Research Jabberwocky Quotations Contact | |
| |
| Patterncraft™ and Constraint and Consequence™ are trademarks of Craig Stewart Holman Copyright © 2008 - 2009 Craig Stewart Holman All Rights Reserved. |
|
| | |
|
|