|
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
| N1 | P1 | Q1 | P1 * 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):
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
|
|
 |
|
|
|