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 nonprime factor with 2, and ending in 5 involves a
nonprime 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(i1)) 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 precomputing 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 precomputing
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
