The Development Of Equation Of Factoring
by
Huen Y.K.
CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~activweb/
Related URL-sites: http://web.singnet.com.sg/~huens/
email: huens@mbox3.singnet.com.sg
(A short communication - 1st released: 5/12/97. Revised 5/12 )
Abstract
This paper describes the development a global generalised Equation of Factoring via
the Equation of Composites or Divisibles [2,3].
Like the latter, the Equation
of Factoring is a super-generating function. An integer number with n distinct prime
factors is defined to have a factoring order of n. For reasons of computational efficiency,
only the probabilistic version of the Equation of Factoring is described in detail. It is
probabilistic because it makes use of a probabilistic primality test for the generation of
prime sequences.
1. Introduction
The Equation of Divisibles or Composites is given by equation (1) [2,3]. This is a super-
generating function consisting of an infinite summation of primitive generating functions.
.....................ub
...................-----
....................\..........1
Comp(z) :=....) ----------- .....................................(1).
..................../.........i...i
...................----- z (z - 1)
...................i = 2
Using Maple V R 3, one can generate a finite sequence of composites as shown in equation
(2):
Comp(z):=sort(series(sum(1/(z^i*(z^i-1)),i=2..20),z=infinity,20));
........................1.........1........2........2........1........2.......4.......2.......2......3......4
Comp(z) := O(---) + ---- + ---- + ---- + ---- + --- + --- + --- + --- + --- + --- ..........(2).
.........................20........4........6........8........9.......10.....12.....14.....15....16.....18
.......................z..........z.........z........z.........z........z........z........z.......z.......z......z
The numerator coefficiens only give the number of factors but do not discriminate between
prime and composite factors. We can modify the numerator expression of equation (1) such
that on series expansions, only prime divisors are displayed. Each divisor i is represented by
an indexed array x(i) where i is also the index to the order variable z in the denominator.
Whenever a number n is divisible by i, the same i also enters as an index in x(i) but the array
elements remain as algebraic quantities until values are assigned to them if necessary.
Furthermore, we introduce a prime filter given by (isprime(i)-false)/(true-false) in the
numerators to suppress displays of composite factors. Since Maple's isprime function is a
probabilistic primality test, this puts the Equation of Factoring into the probabilistic category.
Number theorists are used to accepting probabilistic primes but unused to probabilistic
factoring. Well, we need to change our mindset in this paper. The author has conducted
quite extensive search for counter-examples by subjecting the Lucas' primality
used in Maple's isprime function to long runs of large odd composites but he has
so far found no counter-examples. The Equation of Factoring given
by equation (3) is thus an industrial grade factoring equation.
Comp(z):=sort(series(sum(x(i)*(isprime(i)-false)/(true-false)/(z^i*(z^i-1)),i=2..20),
z=infinity,20));
................ ......1.......x(2)....x(2) + x(3)...x(2)....x(3)...x(2) + x(5)....x(2) + x(3)....x(2) + x(7)
Comp(z) := O(---)+ ---- + -----------+ ---- + ---- + ----------- + ----------- + --------
.........................20........4.............6.............8........9............10................12................14
.......................z.........z..............z..............z........z.............z...................z..................z
...x(3) + x(5).....x(2)....x(2) + x(3)
+ ----------- + ---- + ----------- .......................................................(3).
..........15.............16............18
.........z...............z.............z
If one assigns all array elements to the value of unity, the numerators will give the counts of
distinct prime factors as shown in equation (4).
......1.........1........2........1........1.......2.......2.......2.......2.......1......2
O(---) + ---- + ---- + ---- + ---- + --- + --- + --- + --- + --- + --- ..........(4).
.......20........4........6........8........9......10.....12......14....15.....16.....18
......z.........z........z.........z.........z........z.......z........z.......z.......z.......z
Let us define factoring order in an integer number n as the number of distinct primes found in
it. For example, in equation (3), the integers 4,8,9, and 16 have factoring order of 1 and the
remaining factoring order of 2. If the above series is further expanded we will find numerator
coefficients greater than 2. There is no proof, but intuitively, it is reasonable to assume an
infinity of factoring order. To derive the generalised Equation of Factoring, modifications are
done to the original equation (2) by inverting the fractional representation in each term as
shown in equation (5).
Prime1:=sum(i*(isprime(i)-false)/(true-false)/x(i),i=2..10);
...................2......3........5..........7
Prime1 := ---- + ---- + ---- + ---- ..................................(5).
................x(2)...x(3).....x(5)....x(7)
Using equation (3) as the primitive sequence, we can find a sequence called Factor_2 which
contains only integers with factoring order of 2 as shown in equation (6). Equation (6) returns
10 terms instead of 16 terms because some terms have identical factoring and are lumped
together. These lumping could cause confusions for large sequence expansions but
this can be easily overcome by an improved version given from equations (9) to (11).
Factor_2:=sort(expand(Prime1^2));
Factor_2 :=
..4..........12..............20............28..........9..........30................42.........25...........70............49
-----+ ---------+ ---------+ --------+ ----- + --------- + --------- + ----- + --------- + -----
.....2....x(2) x(3)...x(2) x(5)..x(2) x(7).........2...x(3) x(5).....x(3) x(7)..........2....x(5) x(7)..........2
x(2).....................................................x(3).........................................x(5)........................x(7)
..............................................................................................................................................(6).
Thus the generalised Equation of Factoring for a factoring order n can be written down
as follows:
First the generalised sequence for Prime1 is written as shown in equation (7):
...................ub
.................-----
..................\......i*(isprime(i) - false)
Prime1 :=.....) ----------------------- ...........................(7).
................../......(true - false)*x(i)
.................-----
.................i = 2
The generalised Equation of Factoring for a specific factoring order n is written down as
shown in equation (8). Note that terms with identical factoring will be lumped as a single
term. If this is undesirable, then the order variable x(i) should be converted into a 2-
dimensional array x(i,j) in the improved version where the index j will identify its
contribution from the jth prime sequence as shown in equation (9).
............................../..ub........................................\..n
..............................|-----.......................................|
..........................n..| \ ..../i*isprime(i) false*i.....\......|
......................(-1)..|...)..|------------ - ------- |......|
..............................| / ....\....x(i)...........x(i)......./......|
..............................|-----.......................................|
..............................\i = 2......................................./
Factor_n := --------------------------------------- ...........................(8).
................................................................n
..........................................(- true + false)
2. Improved Version of Equation of Factoring
In this version, double indexed arrays are used for x in the form x(i,j) in the denominators
and the RHS of Factor_n consists of a nested summation within a product operator shown in
equation (9).
Factor_n:=product(sum(i*(isprime(i)-false)/(true-false)/x(i,j),i=2..ub),j=1..n);
........................n....../ ub...................................\
.....................----'....|-----..................................|
....................'..|..|.....| \.....i (isprime(i) - false)......|
Factor_n :=....|..|.....|...) --------------------......| .......................(9).
.......................|..|.....| /.....(true - false) x(i, j).......|
.......................|..|.....|-----..................................|
.....................j = 1....\i = 2................................./
Verification:
Equation (10) shows the unexpanded form in order to check that we are on the right track.
Factor_n:=product(sum(i*(isprime(i)-false)/(true-false)/x(i,j),i=2..10),j=1..2);
..................../....2.............3............5............7........\ /....2.............3............5............7...\
Factor_n := | ------- + ------- + ------- + -------...| | ------- + ------- + ------- + -----|
....................\x(2, 1)....x(3, 1).....x(5, 1).....x(7, 1)../ \.x(2, 2)...x(3, 2)...x(5, 2)...x(7, 2)./.......(10)
Equation (11) is the expanded form:
Factor_n:=sort(expand(product(sum(i*(isprime(i)-false)/(true-false)/x(i,j),i=2..10)
,j=1..2)));
...........................4.....................6....................10....................14......................6
Factor_n := -------------+ -------------+ --------------+ -------------+ ------------
.................x(2, 1) x(2, 2)..x(2, 1) x(3, 2)..x(2, 1) x(5, 2)..x(2, 1) x(7, 2)..x(3, 1) x(2, 2)
...........................9....................15...................21....................10....................15
................+ -------------+ -------------+ --------------+ -------------+ ------------
.................x(3, 1) x(3, 2)..x(3, 1) x(5, 2)..x(3, 1) x(7, 2)..x(5, 1) x(2, 2)..x(5, 1) x(3, 2)
..........................25...................35...................14....................21....................35
................+ -------------+ -------------+ --------------+ -------------+-------------
.................x(5, 1) x(5, 2)..x(5, 1) x(7, 2)..x(7, 1) x(2, 2)..x(7, 1) x(3, 2)..x(7, 1) x(5, 2)
.....................49
..........+-------------- ..........................................................................(11).
...........x(7, 1) x(7, 2)
3. A Big Example
Here we demonstrate with integers in the region of 120 digits. Within an
interval of 1000 integers
in the range from 2^200 to 2^200+1000, there are only two industrial grade primes in
Prime1(x) as shown in equation (12). Equation (13) shows the computations of Factor_2.
Prime1(x):=sum(i/x(i)*(isprime(i)-false)/(true-false),i=2^200..2^200+1000);
Prime1(x) :=
1606938044258990275541962092341162602522202993782792835301611
----------------------------------------------------------------
x(1606938044258990275541962092341162602522202993782792835301611)
1606938044258990275541962092341162602522202993782792835302073
+ ----------------------------------------------------------------
x(1606938044258990275541962092341162602522202993782792835302073) ....(12).
Factor_2:=sort(expand(Prime1(x)^2));
Taking the square of Prime1(x) yields all the integers with factoring order of 2
in this range given by:
Factor_2 :=
258224987808690858965591917200301187432970579282922351283141461742144934744
6345916813045699703323266
842981084605339195321
.../...............................................................................................................................2
../ x(1606938044258990275541962092341162602522202993782792835301611) +
./
516449975617381717931183834400602374865941158565844702566431404559579400190
7292606599414633651377049
252217469790497079206 (note: there are two terms with identical factoring here).
.../
../ x(1606938044258990275541962092341162602522202993782792835301611)
./
x(1606938044258990275541962092341162602522202993782792835302073) +
258224987808690858965591917200301187432970579282922351283289942817434465446
0946689786368933948053
409236385185158097329
.../...............................................................................................................................2
../ x(1606938044258990275541962092341162602522202993782792835302073) ......(13).
./
4. Deterministic Equation Of Factoring
Theoretically, it is possible to develop the deterministic Equation of Factoring. We outline
this as follows:
Prime(x):= Nat(z) - Normc(Oddcomp(z)) ..............................(14).
This will ensure that Prime(x) will be in a normalised form, i.e., all numerator coefficients will
have unity values. Then the deterministic Equation of Factoring will be given by equation (14):
................................................................n
Factor_n := (Nat(x) - Normc(Comp(z))) ...............................(15).
Whilst equation (15) appears decidely simpler than equation (9), one will need to address the
programming problem for the normalising operator Normc( ) which is designed to reduce all
numerator coefficients to unity values. Keeping in mind that the deterministic version is
available, one will have to decide whether it is worth the effort to improve the accuracy when
the probablistic version can be made extremely accurate. So far, the author has yet to encoutner a
counter-example in Lucas' primality algorithm used in Maple's isprime function [5].
5. Conclusions
A generalised Equation of Factoring has been successfully developed by which one could
factor integers with any factor order from 2 to a large upperbound. From amongst those with
n = 2, obviously we can collect together integers which can be factored into two strong
primes. The Equation of Factoring shows that integers with strong primes or weak primes
have about the same degree of ease or difficulty of factoring. The availablility of both the
probabilistic and deterministic version of Equation of Factoring does not imply that the
security of public key cryptographic systems are about to fall. As Scheier mentioned in his
book [1]: "...a list of just the 512-bit primes would weigh so much that it would exceed the
Chandrasar limit and collapse into a black hole ... so you couldn't retrieve the data anyway".
Based on 4-bits to represent a decimal integer, a 512-bit prime could have 128 digits about
the same order as the big example given in section 4. Anyone attempting to produce a
Lehmer's style table of integers with factoring order of 2 will never finish it in his lifetime. Even if he
could, we pity all the trees on Planet Earth.
6. Reference:
[Comments: Not all papers are directly referenced in the main paper. These are
considered relevant to readers who are not familiar with sequence algebra.]
1. Schneier B.( 1996): Applied Cryptography, John Wiley & Sons Inc., Second Edition,
USA, pp 255 to 261.
========================================================
2. Huen Y.K.:
A matrix map for primes and nonprimes, Int. J. Math.Educ.Sci.Technol., 1994,
Vol.25, No.6, pp 913 - 920.
=======================================================
3. Huen Y.K.:
Visual algebra and its applications, Int. J. Math. Educ. Sci. Technol., 1997,
Vol.28, No.3, 333-344.
=======================================================
4. A Simple Introduction To Sequence
Algebra - by Huen Y.K.
(date release: 15.3.97) (38 KBytes, 11*A4 pages).
========================================================
5. The Canonical Generating Function
or CGF(z) ... - by Huen Y.K.
(date released : 27.5..97) (24 KBytes, 7*A4s).
========================================================
6. Methods Of Developing Sequence
Algebraic Formulations For Comp(z) and Prime(z) - by Huen Y.K. (date released : 20.6.97) (36.8 KBytes, 10*A4s).
========================================================
7. Lemmata, Corollaries, And
Theorems In Sequence Order Analysis. - by Huen Y.K. (date released : 6.7.97) (38.3 KBytes, 12*A4s).
========================================================
8. Some Interesting Contiguity
Properties Of Odd(z)^2 - by Huen Y.K. (date released : 15.8.97) (36.3 KBytes, 10*A4s).
========================================================
9. Improved Formulations For Comp(z)
and Prime(z)
- by Huen Y.K. (date released : 16.9.97) (17 KBytes ).
========================================================
10. Detecting False Reports
in Primality Tests By The Oddcomp(z) Method.
- by Huen Y.K. (date released : 18.9.97, Revised 20/9) (26 KBytes ).
========================================================
11. The Throwing Power Of
Oddcomp(z).
- by Huen Y.K. (date released : 24.9.97 ) (15 Kbytes).
========================================================
12. Sequence Algebraic
Approach To Prime Number Theorem
- by Huen Y.K. (date released : 28.9.97 ) (21 Kbytes).
========================================================
13. Generating Functions -
Closed Forms vs Open Forms
- by Huen Y.K. (date released : 1.10.97 ) (21 Kbytes).
========================================================
14. Generating Large
Odd Composite With Two Prime Factors
- by Huen Y.K. (date released : 3.10.97 ) (13.5 Kbytes).
========================================================
15. In Search Of Counter-
Examples In Maple's Isprime Function.
- by Huen Y.K. (date released : 4.10.97 ) (18 Kbytes).
========================================================
16. A Sequence Algebraist's
View Of Lehmann's Primality Test
- by Huen Y.K. (date released : 6.10.97 ) (26 Kbytes).
========================================================
17. On Odd(z), Oddcomp(z),
Seq1(z) and Seq2(z)
- by Huen Y.K. (date released : 10.10.97 ) (17 Kbytes).
========================================================
18. How To Generate A Short
And Contiguous Oddcomp(z) Sequence?
- by Huen Y.K. (date released : 15.10.97 ) (13 Kbytes).
======================== END OF PAPER =========