_{p}when p is prime and I argued(not very convincingly) that the multiplication tables of Z

_{n}when n is composed of 2 distinct primes are much different and would require a different algorithm.

In fact, the same algorithm can be used to generate multiplication tables of Z

_{n}when n is composed of 2 distinct primes.

When called with the following parameters: (0, 1, 15, []) the function described in Multiplication Tables returns the first (n-1)/2 rows of Z

_{15}correctly, and then it proceeds onto pondering the meaning of life, the universe, and everything.

Input: HammerTime(0, 1, 15, [])

Output:

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,

0,2,4,6,8,10,12,14,1,3,5,7,9,11,13,

0,3,6,9,12,

0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,

0,5,10,

0,6,12,3,9,

0,7,14,6,13,5,12,4,11,3,10,2,9,1,8,

Adolescent ramblings:

0,8,1,5,9,13,2,6,10,14,3,7,11,0,5,10,0,6,12,3,9,0,7,14,6,13,5,12

To ensure the function stops short of adolescent ramblings when faced with a composite n, a small change needs to be made like so:

```
//Author: Marina Ibrishimova
//Purpose: Generate the first half of the multiplication table of Z
```_{n}
//without actually computing the GCD(each_row_index*each_column_index, n)
function StopHammerTime(ki, k, n, table_so_far) {
var len = table_so_far.length;
var half_table_slots = n*((n-1)/2);
if(len == half_table_slots) {return;}
else {
while ( ki <= (n - 1)) {
table_so_far.push(ki);
ki = ki + k;
}
len = table_so_far.length;
var last_inset = table_so_far[len-1];
var k_dist = n - last_inset;
var new_ki = k - k_dist;
var n_k = k + 1;
if(last_inset == n-(k-1) && k < n/2) { StopHammerTime(1, k, n, table_so_far); }
**else** if(last_inset == n-k && k < n/2) { StopHammerTime(0, n_k , n, table_so_far); }
else if(last_inset < n && k < n/2){ StopHammerTime(new_ki, k, n, table_so_far); }
}
return table_so_far;
}

StopHammerTime((0, 1, n, [])) generates the first half of any multiplication table skipping repetitions.

Input: StopHammerTime(0, 1, 15, [])

Output:

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,

0,2,4,6,8,10,12,14,1,3,5,7,9,11,13,

0,3,6,9,12,

0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,

0,5,10,

0,6,12,3,9,

0,7,14,6,13,5,12,4,11,3,10,2,9,1,8,

Note: when k = 3 the row is 0,3,6,9,12,0,3,6,9,12,0,3,6,9,12 but StopHammerTime stops short of repetitions in addition to stopping short of adolescent ramblings.

Also note: the actual output of StopHammerTime is a 1D array, the above output is just for eyeball convenience.

Just like with addition tables, multiplication tables are also simply a shift, or a skip, or a cyclic permutation of a row, namely the row, which lists the elements of Z

_{n.}

In addition tables it was always a shift, or a skip of 1 from the row, which lists the elements of Z

_{n.}but in multiplication tables each row k is a shift or a skip by k - 1.

**Example:**in the multiplication table of Z

_{6}the row at k = 1 simply lists the elements of Z

_{6}= [0,1,2,3,4,5] because 1 times any other integer is the integer itself:

What would the row at k = 2 of the multiplication table of Z

_{6}look like without calculating 2*x mod 6 for every x from 0 to n-1?

Well, looking at the row at k = 1, namely [0,1,2,3,4,5], reveals that the element 2 is at index 2, which is a skip by 1 not counting 0 the first time because it is the first element of any row; the second element will be a skip by 1 after the element 0 in the row at k = 1, which is 2; the element after 2 in the row at k = 2 will be a skip by 1 after the element 2 in the row at k = 1, which is 4; the element after 4 in the row at k = 2 will be a skip by 1 after the element 4 in the row at k = 1, which is 0. Now the row at 2 has 4 elements - we keep skipping and populating it in the same manner until there are exactly 6 not necessarily unique elements because every row of Z

_{6}must have 6 elements by definition.

In essence, the row at k = 2 is every second element of the row at k = 1:

k=1 is [

**0**,1,

**2**,3,

**4**,5]

k=2 is [

**0,2,4,0,2,4**]

Similarly for the other rows:

Looking back at the row at k = 1, namely [0,1,2,3,4,5] reveals that k = 3 is a skip by 2 not counting 0 the first time so the row at 3 is

[0,3,0,3,0,3]

Looking back at the row at k = 1, namely [0,1,2,3,4,5] reveals that 4 is a skip by 3 not counting 0 the first time so the row at 4 is:

[0,4,2,0,4,2]

Looking back at the row at k = 1, namely [0,1,2,3,4,5] reveals that 5 is a skip by 4 not counting 0 the first time so the row at 5 is:

[0,5,4,3,2,1]

So the table then becomes:

* 0 1 2 3 4 5

0 [0 0 0 0 0 0]

1 [0 1 2 3 4 5]

2 [0 2 4 0 2 4]

3 [0 3 0 3 0 3]

4 [0 4 2 0 4 2]

5 [0 5 4 3 2 1]

Note: It can be verified with a scientific calculator that this is indeed the multiplication table of Z sub 6 by multiplying each row by each column and then modulo 6 in case the result of multiplying each row by each column is greater than 6. Note that no such calculations were needed in the described algorithm.

The algorithm for factoring n then becomes:

```
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Factor n without any multiplication or addition
---------------------------------------------------- */
```
- Populate A= [0, 1, 2, ... n-1]
- Shift A consecutively for each element in A by its index-1 with an initial starting point of 1.
- If 0 is encountered AND the index at that entry where 0 is encountered is greater than 0, then stop the looping and call that index p.
- Divide n by p, the result will be q,
- Return p and q

Obviously, if #3, 4, 5 are omitted and replaced by a simple if statement, the entire multiplication table will be generated but who cares about that anyway.