|Does anyone have any comment on my factoring algo below:
A new method to factor large semi primes.
The plan is to factor large semi prime numbers. Start by picking 2 Prime Numbers of
appropriate digit size. Choose one as a 200 digit Prime Number, and the other as a 300
digit Prime Number, where their product would be a 500 digit prime number. Then convert
the two decimal digit prime numbers to binary values, and multiply them to form the binary
semi prime product. Calculate the bit size of the binary product. Save a copy of this semi
prime into another value whose bit size is the size of the semi prime rounded up to a
DWORD (mod 32 bit) bound, but left shift it until it fills the largest DWORD. Then save
another copy of this left shifted semi prime, but this time right shifted by 1 bit. These
copies of the semi prime will be used to compare the products of the highest test DWORDS
calculated in the algorithm below (see below for the explanation of why two copies are
The semi prime product would then be factored using a new algorithm.
It has been suggested (by S. C. Coutinho in "The Mathemetics of Cipher", Chapter 11) that
to select the prime numbers for a key of a digit size of r, select one between a digit
size of ((4 / 10) * r) and ((45 / 100) * r). The starting point for the factoring will be
chosen as the middle value between these limits, and will step alternately higher and
lower until the factors are discovered. The first starting factor will then be the p (the
smaller number), and the other starting factor will be q (the larger number) which will be
set to ((10^r ) / p).
With an r of 500, the lowest limit (in digits) will be:
p = ((4 / 10) * r)
p = ((4 / 10) * 500)
p = (4 * 50)
p = 200 digits
The upper limit will be:
p = ((45 / 100) * r)
p = ((45 / 100) * 500)
p = (45 * 5)
p = 225 digits
The mid-point will be:
P = ((200 + 225) / 2)
p = 212 digits
Thus the starting p is a 212 digit number. The other starting factor will be:
q = ((10^r) / p)
q = ((10^500) / (10^212))
q = 288 digits
The p value is then the calculated digit size (converted to bits and then DWORDS), but
the q value must be calculated by subtracting the selected p value bit size from the
selected semi prime bit size (and then rounded up to DWORDS). These bit sizes define bit
fields that will be filled in from both ends with actual values during the factoring
The bit size, digit size, and DWORD sizes of these values are as follows (all of these
powers of 2 are the largest exponent that would not exceed the associated power of 10,
and the DWORD count is the minimum count of DWORDS to contain that binary bit count):
2^707 = 10^212 = 23 DWORDS starting low
2^960 = 10^288 = 30 DWORDS starting high
2^999 = 10^300 = 32 DWORDS max high
2^1664 = 10^500 = 52 DWORDS max product
Three sets of pre-computed tables must be constructed to aid (actually enable) the
factoring of this semi prime.
The first table is saved as 32 bit odd factors (DWORDS), which, when multiplied and
masked to a DWORD, give the same masked product value. This table is saved as multiple
files with names matching the masked product value.
A second, similar, table is constructed for factors which all have the most significant
bit set and saved as files with names matching the highest 32 bits of the product value
(masked to 32 bits).
The third table is just a list of the prime numbers to be considered (all prime numbers
less than 300 decimal digits), but saved in a special way as a multi-level directory
structure as described below.
The entries for this third table consist of DWORD pairs where one of the DWORDS is the
lowest DWORD of the prime number and the other DWORD is the highest 32 bits of the prime
number. All prime numbers that share both of these end values and have the same bit size
will be saved in a directory whose name matches the two DWORDS (high DWORD value and low
DWORD value). The directory sets will be saved under a directory that relates to the bit
One bit of explanation about the information that follows. When a string is enclosed in
quotation marks (""), it is an encoded alphanumeric string. When the characters are not
enclosed in quotes, then the characters are treated as independent decoded DWORD values.
At this point, a diagram may be appropriate. Consider a large prime number with DWORDS
indicated as Hx and Lx, and bit size as a 3 BYTE value indicated by Sx:
H1 H2 H3 H4 ... L4 L3 L2 L1 length Sx
The lowest level directory structure would be (where "Sx" are the different prime number
bit sizes from 2 to 1664):
Beneath each of these size directories would be a layer of directories named "H1x L1x"
(whose prime number bit size is "Sx" and where "H1x" and "L1x" are the first level
different highest and lowest DWORD values of the semi prime):
Beneath each of these directories would be another layer of directories named "H2x L2x":
Essentially, you are creating piecemeal path names on some drive or drives (at some
directory level) as a relative path name:
".\Sx\H1x L1x\H2x L2x\H3x L3x\H4x L4x\ ..."
".\Sx\H1y L1y\H2y L2y\H3y L3y\H4y L4y\ ...
".\Sx\H1z L1z\H2z L2z\H3z L3z\H4z L4z\ ..."
".\Sy\H1x L1x\H2x L2x\H3x L3x\H4x L4x\ ..."
".\Sy\H1y L1y\H2y L2y\H3y L3y\H4y L4y\ ...
".\Sy\H1z L1z\H2z L2z\H3z L3z\H4z L4z\ ..."
".\Sz\H1x L1x\H2x L2x\H3x L3x\H4x L4x\ ..."
".\Sz\H1y L1y\H2y L2y\H3y L3y\H4y L4y\ ...
".\Sz\H1z L1z\H2z L2z\H3z L3z\H4z L4z\ ..."
One other thing to note is that this method greatly reduces the duplication of some of
the DWORD values that would otherwise occur if the actual prime numbers were given as
just a list of full N digit values, i.e., consider 32 DWORD prime numbers of the
following form (where each prime number contained the same low 4 DWORDS and same high 4
H1 H2 H3 H4 ... ... ... L4 L3 L2 L1
The "... ... ..." represent 24 DWORDS, some of which must be different (remember, this
is from a list of prime numbers that are all unique), yet H1 H2 H3 H4 and L4 L3 L2 L1
DWORDS would all be the same and thus not duplicated in this level structure. In the
maximum duplication form, the H1 through H15 and L1 through L15 DWORDS could all be the
same, and only the H16 and L16 DWORDS would be different.
Note that the data is not really binary data, but directory names which must be formed
with alphanumeric or special characters. What will be done to reduce the size of the data
is that the numeric DWORD values will be converted to encoded character values. Several
things were considered in this quest. If decimal conversion were done (0-9), then the
DWORDS would need 10 characters for each DWORD or 20 characters total. If 4 bit hex
conversions were used (0-9 and A-F), then the DWORDS would need 8 characters for each
DWORD or 16 characters total. If 6 bit ASCII64 encoding were used, then the DWORDS would
need 6 characters for each DWORD or 12 characters total but the resulting upper and lower
case letters would require the use of Unicode filenames, and this alone would double the
size of the data to 24 BYTES. Using a character set of upper case and numeric characters
and allowed special characters (26 + 10 + 16 or a 52 character conversion set) would allow
6 character conversions for each DWORD or 12 characters total, but would require divisions
to be used to extract the actual character indexes. Using a 32 character conversion set
(A-Z and 0-5) would result in 7 character conversions for each DWORD (splitting each
DWORD into seven 5 bit fields and then encoding each 5 bits) giving 14 characters for
both DWORDS, but since it would be better to treat both DWORDS as a single QWORD and
split the 64 bits into 13 parts saving even one more character, that method will be
selected. A multi-level table lookup will be used to convert the encoded 13 characters
back into a binary value (a column of 32 QWORD values indexed by the character value, and
13 columns of these QWORD values indexed by which character of the encoded value was
being decoded, all 13 resulting values would be accumulated by adding to yield the QWORD
binary value, then split to two DWORDS).
The size values in the first (lowest level) directory (three BYTE size values) also need
to be converted to character values. For small prime number size values (2, 3, 4, ...)
this would create character strings such as "AAAAB", and there would also be no need for
the High DWORD, thus such small prime numbers would be saved as only a truncated size
field (delete any leading 'A' characters) and would only contain a single DWORD value in
the next lower directory level (second level) such as:
"B" for 2 bits
"AAAAAAB" for prime number 2
"AAAAAAC" for prime number 3
"C" for 3 bits
"AAAAAAE" for prime number 5
"AAAAAAG" for prime number 7
"D" for 4 bits
"AAAAAAK" for prime number 11
No attempt will be made to delete the leading 'A' characters in these short prime numbers.
When the bit size exceeds 32 bits, the second DWORD would be created to precede the first
DWORD in the directory name. This second (most significant) DWORD would consist of the
most significant 32 bits of the prime number and would always have the most significant
bit set (always be at least an encoded "B..."), and would result in an encoded 13
character directory name.
The max size of a prime number of 300 digits is 32 DWORDS or 16 QWORDS which would convert
to a directory name of 232 characters ((13 + 1) * 16) + (5 + 1) + (1 + 1)) (max directory
name size plus a separator times 16 sub directory levels plus size directory name plus a
separator plus the drive name plus a separator). This is well within the MAX_PATH for a
directory entry which is 260 BYTES so unicode path names are not required.
The factoring algorithm starts out by factoring the semi prime's lowest DWORD and highest
32 bits into lists of DWORD pairs (masked to a low DWORD for the low DWORD pair and to a
high DWORD for a high 32 bit pair) whose DWORD products match the appropriate end values
of the semi prime. Prime numbers whose ends match these pairs are the only prime numbers
that need to be considered in the factoring process, all other prime numbers cannot
possibly be the correct values. All four of the possibilities must be considered (one at
a time) when considering which value of a pair belongs to the larger prime number and
which value belongs to the smaller prime number. Assume that the end values for the first
(odd number) table pair values were A and B and the second (MSD bit set) table values were
C and D. The possible test primes would then be:
Small and Large
C ... A and D ... B
C ... B and D ... A
D ... A and C ... B
D ... B and C ... A
Start the building process by creating four number buffers (bit fields) whose bit size is
the bit size of the semi prime extended to a mod 32 bit size. Now process each of the
above mentioned 4 possible pairs, let us say, starting with the C ... A and D ... B pair.
Multiply them as follows:
C ... A
* D ... B
RS = B * A (R ignored)
TU = D * C (U ignored)
One word about my selection of variable names R, S, T, U, W, X, Y, and Z (in the
example above and in the example below). I did not use the letter "V" because in my
text editor (PFE), while using the OEM fixed pitch font, the "U" (Uniform) and "V"
(Victor) letters appear almost the same and are easily confused.
Now, S would be equal to the lowest DWORD of the semi prime because the A and B characters
were entries in the factor table for the lowest DWORD in the semi prime, but R needs to be
calculated and saved. T would be equal to the highest 32 bits of the semi prime for the
same reason and U needs to be calculated. S and T will always match the end DWORDS of the
left shifted semi prime (also, see below). The R must be calculated as (A * B) >>= 32 and
T must be calculated as (C * D) >>= 32. This will be done once as the factor pair lists are
read and the R values and U values (1 for each pair) saved in two arrays for later use.
Look up the directory ".\Ss\C A" and the directory ".\Sl\D B" (where "Ss" is the small
test prime number size and "Sl" is the large prime number size), and the lowest of their next
level sub-directories (treat the sub-directories as a list of possible useful matches). If
either such directory or sub-directory entry does not exist, then skip to the next low or
high list entry and retry.
Access the first of the ".\Ss\C A" sub-directory entries and assume that it contains the 2
DWORDS as E F and that the first of the ".\Sl\D B" sub-directory entries contains the 2
DWORDS as G H. Combine the sub directory values with the parent directory values to
continue building the prime numbers as:
C E ... F A
* D G ... H B
Multiply F A and H B and mask the product to a QWORD and check if the result matches the
least significant QWORD of the semi prime:
* H B
RS = B * A (already computed above)
TU = B * F (T ignored)
WX = H * A (W ignored)
YZ = H * F (YZ ignored)
IJKL (IJ ignored)
K ((R + U + X) / DWORD) should match second lowest DWORD of the semi prime. If not, select
the next low pair and try again,
Multiply C E and D G and check if the most significant 64 bits of the product matches the
most significant 64 bits of the semi prime:
* D G
RS = G * E
TU = G * C
WX = D * E
YZ = D * C (already computed above)
MNOP (OP ignored)
MNOP may possibly need to be adjusted because the product may just be 127 bits and not 128
bits. If and only if (IFF) the most significant two bits of C and D are both set, then the
product would be 128 bits, otherwise it would be 127 bits and require a shift to be
correct for a compare with the high semi prime value (the semi prime high end would be
already left shifted to set the most significant bit of a DWORD). Because of this anomoly,
all products starting with these pairs (for all 16 levels) must be left shifted by one
bit. This is time comsuming. To avoid this, the left shifted semi prime has been also
saved as a right shifted by one bit value. When the high factor pair is first selected, a
check will be made and the correct pointer to the semi prime check value will be
established for that pair, and product shifting will not be required.
M and N should match the highest 64 bits of the check semi prime. If not, select a new
high pair and reset the low pair to the beginning (working with a new high pair) and start
again until both pairs match. Note that O and P cannot be checked at this time because it
is unknown how much the carry DWORDS will be until the next level testing can select the
third DWORD pair.
If the end of either factor list is reached before the double match, change which of the
four initial pairs is being used, and if all four pairs have been checked, then change the
test number bit sizes (alternate lower and higher around the smaller value mid-point that
was selected and then recalculate the larger number bit count), and reset the lists and
start again until the actual factors are found.
If both end points match then check if you are at the lowest level. Do this by maintaining
the bit sizes by decrementing by 64 as you go to each next level - when the smaller test
number lower size is less than 64, then hold the smaller test number and just process the
larger test number for subsequent levels.
If both sizes are less than 64 then you have the final test primes. Just multiply out the
DWORD values (to get all middle carries) to verify whether this is a valid solution. To
get these values (they are split into 4 parts during this testing), the low DWORD values
are correct, it is only the high values that need to be adjusted and concatenated to the
top of the low values and then multiplied. To do this for the smaller test value, subtract
the bit size of the smaller test value lower test DWORDS (DWORD count * 32) from the total
bit size of the smaller test value. Divide the result by 32 (a shift works really well)
and what remains is the bit count to right shift the smaller test value high DWORD values
deleting low bits that are shifted out of the lowest DWORD value in the high piece (use
right shift double on pairs of adjacent DWORDS), then concatenate the result to the low
DWORDS. Do the same thing to adjust the larger test value high DWORDS. Then multiply and
check the product with the semi prime itself.
If both sizes are > 63 then drop down both of the directory levels and get the next two
pair of DWORDS for the test prime numbers and extend the multiplies by a DWORD each and
check again until you have the final test primes.
Obviously, quit when you find the two final prime numbers that, when multiplied, result in
the semi prime product.