Generating Large Odd Composites With Two Prime Factors
by
Huen Y.K.
CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~huens/
email: huens@mbox3.singnet.com.sg
(A short communication - 1st released: 3/10/97 )
Abstract
Here is an unconventional way of generating large odd composites with two prime factors. I am sure you
could guess where it might come in handy if you only have access to a Pentium. You could
generate a sequence of odd
composites using an open form generating function with magnitudes of integer as big as 2^500000 and beyond if
you have all the time in the world to wait for them. The use of Maple's isprime function will bring in
probability but so far the author has not found any counter-examples in this primality test
function. As to whether you can crack RSA challenge keys with it, it will depend on your luck
and strategy employed. But the method could easily be orchestrated with thousands of
Pentiums if you have the clout to do it. You will not be able to find a new record for Mersenne'
prime this way since if you use Maple V R 3, you will be stonewalled at around 2^870000
which is nowhere near the current world record.
1. Introduction
The product of two primes will always be an odd composite. It is hard to factor large
composites with hard numbers, i.e., prime factors of about equal magnitudes but it is
very easy to generate a sequence of odd composites each containing two primes by
using either the Oddcomp(z) formulation or simply using Maple's isprime function in
a sequence algebraic formulation [2]. In this paper, the author chooses to use the latter
since he has as yet to find a counter-example for isprime. If Oddcomp(z) is used,
one will need to bring in Prime(z) which is deterministic but Maple does not provide
the Normc( ) function which will be needed.
The general program lines for generating large odd composites which can be factored into
two primes is given in equation (1).
Oddcomp(z):=sort(sum(sum(((isprime(i)-false)*(isprime(j)-false)/(true-
false)^2)/(x^i*y^j),i=1..2^4),j=1..2^4));
............................1.........1..........1..........1..........1..........1..........1..........1..........1.........1........1
Oddcomp(z) := ----- + ----- + ----- + ----- + ----- + ----- + ----- + ----- + ----- + ----- + -----
..........................2 2.......2 3.......3 2.......3 3.......2 5.......5 2.......3 5.......5 3.......2 7.......7 2......3 7
........................y x.......y x........y x.......y x........y x........y x........y x........y x.......y x.......y x......y x
...........1...........1..........1..........1..........1..........1............1..........1..........1..........1.............1
......+ ----- + ----- + ----- + ----- + ------ + ------ + ------ + ----- + ------ + ------ + ------
............5 5.......7 3.......5 7.......7 5.......2 11.....11 2......3 11........7 7......11 3......2 13.....13 2
.........y x.........y x........y x.......y x........y x........y x.......y x...........y x.......y x........y x........y...x
..............1.........1............1...........1...........1...........1...........1...........1...........1...........1.........1
......+ ------ + ------ + ------ + ------ + ------ + ------ + ------ + ------ + ------ + ------+-----
..........3 13..........5..........11........11 5......13 3.......5 13......7 11......11 7......13 5.....7 13....13 7
........y x.........y x...........y x.......y...x .......y...x.......y...x.......y..x........y...x.......y..x......y..x....y...x
............1.............1............1..............1
......+ ------- + ------- + ------- + ------- ...................................................(1).
.........11 11.........11 13......13 11......13 13
.......y....x..........y...x..........y...x.........y...x
If you wish to use this expression for factoring a special odd composite, you could extend
equation (1) as follows:
Oddcomp(z):=sort(sum(sum((z^abs(oddcomp_to_be_factored-i*j)*(isprime(i)-
false)*(isprime(j)-false)/(true-false)^2)/(x^i*y^j),i=3..2^4),j=3..2^4));
...........................abs(oddcomp_to_be_factored - 9).....abs(oddcomp_to_be_factored - 15)
.........................z........................................................z
Oddcomp(z) := ------------------------------------ + ---------------------------------
...............................................3...3..............................................3...5
.............................................x...y..............................................x...y
..........................abs(oddcomp_to_be_factored - 15)....abs(oddcomp_to_be_factored - 21)
..........................z........................................................z
......................+ ----------------------------------- + ---------------------------------
...............................................5...3..............................................3...7
..............................................x...y..............................................x...y
...........................abs(oddcomp_to_be_factored - 21)....abs(oddcomp_to_be_factored - 25)
...........................z.........................................................z
.......................+ ----------------------------------- + ---------------------------------
................................................7...3.............................................5...5
...............................................x...y.............................................x...y
......................+------------------------------------+---------------------------.................
...........................abs(oddcomp_to_be_factored - 143)....abs(oddcomp_to_be_factored - 143)
..........................z...........................................................z
.......................+ ---------------------------------- + ----------------------------------
.............................................11...13..........................................13...11
............................................x....y.............................................x....y
............................abs(oddcomp_to_be_factored - 169)
..........................z
.......................+ ---------------------------------- ..............................................................(2).
.............................................13...13
.............................................x...y
Here is a real example on how to weed out all the unfactored terms in equation (2) to get at
the factored composites. Unfactored terms are not necessarily primes but these simply
do not possess two prime factors.
Let oddcomp_to_be_factored = 5*13 = 65.
Oddcomp:=sort(sum(sum((z^abs(65-i*j)*(isprime(i)-false)*(isprime(j)-false)/(true-
false)^2)/(x^i*y^j),i=3..2^4),j=3..2^4));
........................104.......78...........78...........56........50........50.........56.........44.........44........40
.......................z...........z.............z.............z...........z..........z...........z...........z............z..........z
Oddcomp := ------- + ------- + ------- + ----- + ----- + ----- + ------- + ----- + ----- + -----
......................13..13....11...13....13..11.....3...3.....3...5.....5...3.....11..11....3...7.....7...3....5..5
.....................x...y.......x....y........x....y......x...y......x...y.....x...y......x...y........x...y......x...y....x..y
..............32........32.........30..........30........26........26.........26.........26........16........12...........12
.............z..........z...........z............z..........z...........z............z...........z...........z...........z............z
......+ ------ + ------ + ----- + ----- + ------ + ------ + ------ + ------ + ----- + ------ + ------
..........3...11....11..3......5...7......7...5.....3..13.....13...3......7..13....13...7....7...7.....7...11.....11...7
.........x...y......x...y........x...y......x...y.....x..y.......x....y.......x...y......x....y......x...y.....x...y........x...y
..............10.........10
.............z...........z............1...........1
......+ ------ + ------ + ------ + ------
...........5..11....11..5......5..13.....13..5
..........x...y......x...y......x...y.......x....y
To sieve the factored terms from the unfactored terms, put:
..............................z := 0
This yields two factored terms which are exact images:
................................1...........1
.............................------ + ------
..............................5..13....13..5
.............................x..y.......x..y
2. A Big Example
Maple can generate odd composites in the 512-bit key size range with ease. You can also
use the method described above to sieve the factored composites. In a real example, the
range of computation will be very big and time consuming and you may encounter harddisk
trashing or memory limitation.
Oddcomp:=sort(sum(sum((isprime(i)-false)*(isprime(j)-false)/(true-false)^2)/(x^i*y^j),
i=2^512..2^512+1000),j=2^512+50..2^512+100));
Oddcomp := 1/(x^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084171
y^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084171
) + 1/(x^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084241
y^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084171
) + 1/(x^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084381
y^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084171
) + 1/(x^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084823
y^
134078079299425970995740249982058461274793658205923933777235614437217640300
7354697680187429816690342\
7690031858186486050853753882811946569946433649006084171
)
3. Conclusions
This paper gives you window into computing in the really big integer region using
a low-cost symbolic package without relying on multiprecisions subroutines which are
difficult to come by. Large odd composites with hard numbers are quite easy
to generate. However, the assumption that large integers with hard numbers are difficult to
factor is unproven. Readers who are unfamiliar with sequence algebra are recommended
to read at least the three papers in the reference section. Have funs.
4. Reference:
1. Huen Y.K.: Lemmata, Corollaries, And Theorems In Sequence Order Analysis. URL site:
http://web.singnet.com.sg/~huens/ .
2. Huen Y.K.: Detecting False Reports In Primality Tests By The Oddcomp(z) Method, URL
site: http://web.singnet.com.sg/~huens/ .
3. Huen Y.K.: The Throwing Power Of Oddcomp(z), URL site: http://web.singnet.com.sg/
~huens/.
======================== END OF PAPER ======================