Example: Begin with two single-digit integers, a and b:

ab mod 10 = r, the remainder;

c =(ab - r)/10 where c is the carry digit.

In general, we do multiplication without numbers except for the use of 10 in division operations…

Multiplying two two-digit integers is a tough challenge. Please give it a try.

tu × sr = ?

tu × sr (top level)

= ГμΩ (level-one digits)

+ ihg0 (level-two digits)

= zpθΩ (level-three digits);

level-one equations:

Ω = us mod 10;

a = (us - Ω)/10;

μ = (ts + a) mod 10;

Г = (ts + a - μ)/10.

level-two equations:

g = ru mod 10;

b = (ru - g)/10;

h = (rt + b) mod 10;

i = (rt + b - h)/10.

level-three equations:

θ = (μ + g) mod 10;

d = (μ + g - θ)/10;

p = (Г + h + d) mod 10;

z = (Г + h + d - p)/10.

General Equation:

100rt + 10(ru + ts) + us = 1000z + 100p + 10θ + Ω.

Example: r = 8, s = 9; t = 6, u = 7;

89 * 67 = 5963;

100×8*6+ 10(8*7 + 6*9) + 7*9 = 5963 = 1000×5 + 100*9 + 10*6 + 3.

Algebra reveals the beauty (dynamic harmony) of simple integer multiplication…

General Equation:

100rt + 10(ru + ts) + us = 1000z + 100p + 10θ + Ω.

Given factors rs and tu, it is easy to compute the product, zpθΩ.

However, given the product, zpθΩ, it is generally harder to compute the factors, rs and tu. What method is effective for this problem?

Given factors, rs and tu, it is easy to compute the product, zpθΩ.

However, given the product, zpθΩ, it is generally harder to compute the factors, rs and tu.

What method is effective for this problem? rs × tu = zpθΩ.

General Equation:

100rt + 10(ru + ts) + us = 1000z + 100p + 10θ + Ω.

Solution:

I. (u, s) ∈ { (v , w) | Ω = vw mod 10 };

II. 160 ≤ ru + ts ≤ 0 where the sum, ru + ts, is a multiple of 10;

III. 10rt + ru + ts = zp0.

Example: Let zpθΩ = 8051. And we assume that zpθΩ is a product of two prime factors, rs and tu. Compute rs and tu.

According to our solution or algorithm, we have:

I. (u, s) ∈ { (v , w) | 1 = vw mod 10 }

= { (1, 1), (9, 9), (3, 7)};

II. a. 160 ≤ r + t ≤ 0;

Or b. 160 ≤ 9r + 9t ≤ 0;

Or. c. 160 ≤ 3r + 7t ≤ 0;

where the sum, ru + ts, is a multiple of 10;

III. a. 10rt + r + t = 800;

Or. b. 10rt + 9r + 9t = 800;

Or c. 10rt + 3r + 7t = 800;

The term, 10rt, suggest we select r and t such that 160 ≤ 800 - 10rt ≤ 0.

Therefore, we have:

(t, r) ∈ { (1, 8), (8, 9), (8, 8)};

We compute (u, s) = (3, 7) and (t, r) = (8, 9).

Hence, 97 * 83 = 8051.

Multiplying two three-digit integers,

rst and uvw, is a tougher challenge.

Find the algebraic equations and the general equation like the previous case for the multiplication of two-digit integers. Please give it a try.

We assume rst × uvw = λzyxϴΩ.

Note: There's a need to change notation to avoid some confusion.

We assume

r_s_t_ × u_v_w_ = λ_z_y_x_ϴ_Ω_

instead of rst × uvw = λzyxϴΩ which

may suggest wrongly, we mean that

r*s*t × u*v*w = λ*z*y*x*ϴ*Ω.

Multiplying two three-digit integers,

r_s_t_ and u_v_w_, is a tougher challenge.

Find the algebraic equations and the general equation like the previous case for the multiplication of two-digit integers.

Please give it a try.

We assume:

r_s_t_ × u_v_w_ = λ_z_y_x_ϴ_Ω_.

We can formulate the general equation without deriving the immediate algebraic equations.

__.______.______r_______s______t

x

__.______.______u_______v______w

__________________________________

__.______._______wr_______ws______wt

__.______vr______vs_______vt_______0

__ur____us______ut________0_______0

General Equation:

10,000ur + 1,000(vr + us) + 100(wr + vs + ut) + 10(ws + vt) + wt

= 100,000λ +10,000z + 1000y+ 100x + 10ϴ + Ω.

Verification of General Equation:

10,000ur + 1,000(vr + us) + 100(wr + vs + ut) + 10(ws + vt) + wt

= 100,000λ +10,000z + 1000y+ 100x + 10ϴ + Ω.

Let r_s_t_ = 967; u_v_w_ = 859;

Therefore, λ_z_y_x_ϴ_Ω_ = 830,653.

10,000*8*9 + 1,000(5*9+ 8×6) + 100(9*9 + 5*6+ 8*7) + 10(9*6 + 5*7) + 9*7 = 830,653. Okay.

Alan Turing — "Those who can imagine anything, can create the impossible."

Please keep in mind the following important problem as we develop some methods to factor composites efficiently.

Big Problem (BP):

Given a 2n-digit composite (a product of two unknown and unequal prime factors each with n digits where n ≥ 450), develop an algorithm which factors the composite in polynomial time.

As we work our way up Mount BP, let us make some discoveries/ innovations to expedite our journey successfully. Amen!

TENTATIVE CONCLUSION: For n ≥ 450, our big problem is practically unsolvable in real time. Why?

We recall our Big Problem (BP):

Given c, a 2n-decimal digit composite (a product of two unknown and unequal prime factors, a and b, each with n decimal digits where n ≥ 450), develop an algorithm which factors the composite in polynomial time.

We have c = a * b such b < a.

Furthermore, we know c.

c = c_(2n - 1) * 10^(2n - 1) + c_(2n - 2) * 10^(2n - 2) + ... + c_0.

But a and b are unknown to us.

a = a_(n - 1) * 10^(n - 1) + a_(n - 2) * 10^(n - 2) + ... + a_0;

b = b_(n - 1) * 10^(n - 1) + b_(n - 2) * 10^(n - 2) + ... + b_0.

To compute a and b from c, we must correctly select the following points in order from left to right:

(a_0, b_0), (a_1, b_1), (a_2, b_2), ...,

( a_(n-1), b_(n-1) ).

There are two or three random ways to compute (a_0, b_0) given c_0.

And there are at most 10 random ways to ( a_(n-1), b_(n-1) ) given c_(2n - 1).

But the number of random ways to compute points, (a_k, b_k), between k=0 and k=n_1, exclusively, is at most 100.

For n ≥ 450 it will take generally at least 10^(2n - 2) calculations to compute a and b.

Can we significantly reduce our calculations? We are extremely doubtful it can be done.

For n ≥ 450 it will take generally at least 10^(2n - 2) random calculations to compute a and b.

Can we significantly reduce our calculations?

HYPOTHESIS: If we can show that for k ≥ 2, the correct point, (a_k, b_k), does not affect the previous correct points whose subscripts are less than k, then we can significantly reduce our calculations and solve our problem hopefully in polynomial time.

Let's conduct an experiment to test our hypothesis.

Let c = 6,432,934,577 which is a composite of two unknown prime factors, a and b.

c^.5 ≈ 80,206

[Reference Source Code for c:

http://m.wolframalpha.com/input/?i=prime%28RandomInteger%28%7B3500%2C+9550%7D%29%29×prime%28RandomInteger%28%7B3500%2C+9550%7D%29%29 ]

So, 64,329 < a < 80,206 < b < 99,999.

Since c_0 = 7, we have:

(a_0, b_0) ∈ { (7, 1), (3, 9)}.

And c_9 = 6 and c_8 = 4, we have:

(a_4, b_4) ∈ { (7, 8), (8, 8)}.

.....

Factoring c is a big challenge and a really beautiful problem....

Given c, a 2n-decimal digit composite (a product of two unknown and unequal prime factors, a and b, each with n decimal digits where n ≥ 450), develop an algorithm which factors the composite in polynomial time.

We have c = a * b such b < a.

Furthermore, we know c.

c = c_(2n - 1) * 10^(2n - 1) + c_(2n - 2) * 10^(2n - 2) + ... + c_0.

We let c = 6,432,934,577.

But a and b are unknown to us.

a = a_(n - 1) * 10^(n - 1) + a_(n - 2) * 10^(n - 2) + ... + a_0;

b = b_(n - 1) * 10^(n - 1) + b_(n - 2) * 10^(n - 2) + ... + b_0.

To compute a and b from c, we must correctly select the following points in order from left to right:

(a_0, b_0), (a_1, b_1), (a_2, b_2), ...,( a_(n-1), b_(n-1) ).

Relevant Algebraic Equations including carry decimal, k_i, from i=0 to i=8 with n=10:

c_0 = b_0 * a_0 mod 10;

k_0 = (b_0 * a_0 - c_0)/10;

c_1 = (b_1 * a_0 + b_0 * a_1 + k_0) mod 10;

k_1 = (b_1 * a_0 + b_0 * a_1 + k_0 - c_1)/10;

c_2 = (b_2 * a_0 + b_1 * a_1 + b_0 * a_2 + k_1) mod 10;

k_2 = (b_2 * a_0 + b_1 * a_1 + b_0 * a_2 + k_1 - c_2)/10;

c_3 = (b_3 * a_0 + b_2 * a_1 + b_1 * a_2 + b_0 * a_3 + k_2) mod 10;

k_3 = (b_3 * a_0 + b_2 * a_1 + b_1 * a_2 + b_0 * a_3 + k_2 - c_3)/10;

c_4 = (b_4 * a_0 + b_3 * a_1 + b_2 * a_2 + b_1 * a_3 + b_0 * a_4 + k_3) mod 10;

k_4 = (b_4 * a_0 + b_3 * a_1 + b_2 * a_2 + b_1 * a_3 + b_0 * a_4 + k_3 - c_4)/10;

c_5 = (b_4 * a_1 + b_3 * a_2 + b_2 * a_3 + b_1 * a_4 + k_4) mod 10;

k_5 = (b_4 * a_1 + b_3 * a_2 + b_2 * a_3 + b_1 * a_4 + k_4 - c_5)/10;

c_6 = (b_4 * a_2 + b_3 * a_3 + b_2 * a_4 + k_5) mod 10;

k_6 = (b_4 * a_2 + b_3 * a_3 + b_2 * a_4 + k_5 - c_6) / 10;

c_7 = (b_4 * a_3 + b_3 * a_4 + k_6) mod 10;

k_7 = (b_4 * a_3 + b_3 * a_4 + k_6 - c_7) / 10;

c_8 = (b_4 * a_4 + k_7) mod 10;

k_8 = (b_4 * a_4 + k_7 - c_8) / 10;

c_9 = k_8.

Note: (a_k, b_k) or (b_k, a_k) are possible for k=0 to k=8.

c^.5 ≈ 80,206

[Reference Source Code for c:

http://m.wolframalpha.com/input/?i=prime%28RandomInteger%28%7B3500%2C+9550%7D%29%29×prime%28RandomInteger%28%7B3500%2C+9550%7D%29%29 ]

So, 64,329 < a < 80,206 < b < 99,999.

Since c_0 = 7, we have:

(a_0, b_0) ∈ { (7, 1), (3, 9)}.

And c_9 = 6 and c_8 = 4, we have:

(a_4, b_4) ∈ { (7, 8), (8, 8)}.

Important Fact: Casting Out Nines

(https://en.m.wikipedia.org/wiki/Casting_out_nines)

[ (b_(n - 1) + b_(n - 2) + ... + b_0) mod 9

* (a_(n - 1) + a_(n - 2) + ... + a_0) mod 9 ] mod 9

= (c_(2n - 1) + c_(2n - 2) + ... + c_0) mod 9

So, 64,329 < a < 80,206 < b < 99,999.

Since c_0 = 7, we have:

(a_0, b_0) ∈ { (7, 1), (3, 9)}.

And c_9 = 6 and c_8 = 4, we have:

(a_4, b_4) ∈ {(6,9), (7, 9), (7, 8), (8, 8)}.

SUMMARY FOR FACTORING c:

We have 2n - 2 unknowns and 2n - 2 equations. Therefore, our problem should be solvable in polynomial time. We need to generate appropriate data sets for each appropriate pair of equations. And select the unique solution from those data sets. In practice, this may or may not be difficult. But in theory, it should work...

Excellent Reference Sources:

1. 'Fundamentals of Algorithmics', by G. Brassard and P. Bratkey, 1996, ISBN: 0-13-335068-1;

2. 'Combinatorial Optimization: Theory and Algorithms' 2nd ed., by B. Korte and J. Vygen, 2002, ISBN: 3-540-43154-3.

Work (study, research, and algorithm development) on this question continues...