The Constructive Approach to Integer Factorization

Main Page
Introduction
Sun Microsystems T1000
The RSA Factoring Challenge
The Constructive Approach
Evaluation Summary
Future Research
Evaluation Chronology
System Configurations
Financial Disclaimer
Postscript

© Grebyn Corp. 2006

 

Theory

The basic premise of the constructive approach is to create the digits in the candidate factors, P and Q, in such a way that the resulting product (which we will denote by X) has all the digits in each round that match the digits in the challenge number.

First, we consider some properties of the challenge number. The challenge number, N, has to end in 1, 3, 7 or 9 as ending in 0, 2, 4, 6, 8 involves a non-prime factor with 2, and ending in 5 involves a non-prime factor with 5. Number the digits from the right to the left (N1 being the ones digit, N2 being the tens digit, etc.).

Based upon the final digit of the challenge number, we can determine all possible final digit combinations in candidate factors according to the following table, utilizing the equation:

(P1 * Q1) mod 10 = N1

N1P1Q1P1 * Q1
1 1 1 1
3 7 21
7 3 21
9 9 81
3 1 3 3
3 1 3
7 9 63
9 7 63
7 1 7 7
3 9 27
7 1 7
9 3 27
9 1 9 9
3 3 9
7 7 49
9 1 9

Table 1. First Digit Generation

Note that for all combinations, the product X at this round has the correct X1 digit, that matches the challenge numbers N1 digit.
Also, and only for the first digit, "duplicates" (matching P Q pairs) can be discarded by selecting the pair with the smaller first value.

For subsequent rounds (instantiated for round i), the equation for determining digits in candidate factors that is used is:

((Pi * Q1) + (Qi * P1) + X(i-1)) mod 10 = Ni

Where Pi and Qi vary over the range 0 to 9, X is taken from the previous candidate combination and Ni is obtained from the challenge number.

TBD: Might want to include additional discussion on the "theory" of why this works.

Where P and Q are relatively close, the number of rounds needed to generate possible factors would be equal to or slightly greater than one half of the number of digits in the challenge number plus one. For RSA Challenge Numbers, it is known that the numbers are products of a multiple of 8 bit integers.

Worked Example

Given a challenge number N, the product of two primes, solve for the smallest unknown digit in two possible prime factors P and Q as follows.

Example, N = 14759443, P = 3803, Q = 3881.

Candidate combinations for the first (rightmost) unknown digit can be determined from Table 1 above, or simply by looping (various time / space tradeoffs can be made by pre-computing tables containing various of these values) over values for P1 and Q1 in the range 1 .. 9 and selecting P1, Q1 according to the equation:

(P1 * Q1) mod 10 = 3

The resulting set of candidate combinations is (where X is the resulting product of P and Q):

P Q X
1 3 3
3 1 3
7 9 63
9 7 63


Order the combinations smallest to largest in pairs where there are "duplicates" (this reordering step only applies to the first round):

P Q X
1 3 3
7 9 63


Now, solve for values of P2 and Q2 for the second digit (N2 = 4), using the equation (where X2 is taken from the above results):

(Q2 * P1 + P2 * Q1 + X2) mod 10 = N2

Again, note that for all combinations, the product X at this round has the correct X1 and X2 digits matching the N1 and N2 digits, namely 3 and 4, in the challenge number. Also note that the number of combinations has increased by a factor of ten in this round, from 2 to 20.

This results in the following set of numbers:

P Q X
01 43 43
11 13 143
21 83 1743
31 53 1643
41 23 943
51 93 4743
61 63 3843
71 33 2343
81 03 243
91 73 6643
07 49 343
17 79 1343
27 09 243
37 39 1443
47 69 3243
57 99 5643
67 29 1943
77 59 4543
87 89 7743
97 19 1843


Round 2

Now, we solve for values of P3 and Q3 for the third digit (N3 = 4), using the equation (again, where X3 is taken from the above results):

(Q3 * P1 + P3 * Q1 + X3) mod 10 = N3

Again, note that for all combinations, the product X at this round has the correct X1, X2 and X3 digits, namely 3, 4 and 4, that match the challenge number. The number of combinations has again increased by a factor often in this round, from 20 to 200, although only the first and last ten, and ten around the actual solution, are shown below.

P Q X
001 443 443
101 143 14443
201 843 169443
301 543 163443
401 243 97443
501 943 472443
601 643 386443
701 343 240443
801 043 34443
901 743 669443
... ... ...
081 203 16443
181 903 163443
281 603 169443
381 303 115443
481 003 1443
581 703 408443
681 403 274443
781 103 80443
881 803 707443
981 503 493443
... ... ...
097 819 79443
197 119 23443
297 419 124443
397 719 285443
497 019 9443
597 319 190443
697 619 431443
797 919 732443
897 219 196443
997 519 517443

Round 3

Finally we solve for values of P4 and Q4 for the fourth digit (N4 = 9), using the equation:

(Q4 * P1 + P4 * Q1 + X4) mod 10 = N4

Not surprisingly, we get 2000 combinations (again, ten times as many as the previous round - all not shown), including the one (marked in bold below) that solves our factorization:

P Q X
0001 9443 9443
1001 6443 6449443
2001 3443 6889443
3001 0443 1329443
4001 7443 29779443
5001 4443 22219443
6001 1443 8659443
7001 8443 59109443
8001 5443 43549443
9001 2443 21989443
0101 5143 519443
... ... ...
0881 2803 2469443
1881 9803 18439443
2881 6803 19599443
3881 3803 14759443
4881 0803 3919443
5881 7803 45889443
6881 4803 33049443
7881 1803 14209443
8881 8803 78179443
9881 5803 57339443
... ... ...
0997 6519 6499443
1997 9519 19009443
2997 2519 7549443
3997 5519 22059443
4997 8519 42569443
5997 1519 9109443
6997 4519 31619443
7997 7519 60129443
8997 0519 4669443
9997 3519 35179443


Round 4

Implementation

Various approaches, starting with arrays of single digits through multiple digits, finally settling on powers of two, with various data management strategies for handling the increase of data at each round and pre-computing various tables have been implemented and tested. More detailed information is available in the Evaluation Chronology page.

Explanation

I like to say of this approach, as with Dr. McCoy ("Bones" to his friends :-)) of Star Trek while reattaching Spock's Brain:

"It's so simple. A child could do it!"

This really is so much more simpler mathematics than the Generalized Number Field Sieve mentioned earlier.

Previous Next