19.12.15

A Few More Observations

The following is a continuation of the post A Few Observations that I wrote a few weeks ago.

Claim 4: The elements [12, 22, 32, ..., ((n-1)/2)2] mod n when n is the product of two distinct odd primes p and q can be generated using the following relation:

a0 = ((n-1)/2)2 mod n
a1 = (a0 + 2*1) mod n
a2 = (a1 + 2*2) mod n
a3 = (a3 + 2*3) mod n
.
.
.
ai = (ai-1 + 2*i) mod n

If ai = 0 then all elements [12, 22, 32, ..., ((n-1)/2)mod n] have been generated

Example: n = 35 so a0 = ((35-1)/2)2 mod 35 = 9 then 
a1 = a0 + 2*1 mod 35 = 9 + 2 = 11, 
a2 = a1 + 2*2 mod 35 = 11 + 4 = 15, 
a3 = 15 + 2*3 mod 35  = 21, 
a4 = 21 + 2*4 mod 35 = 29,
a5 = 29 + 2*5 mod 35 = 4,
a6 = 4 + 2*6 mod 35 = 16, 
a7 = 16 + 14 mod 35  = 30, 
a8 = 30 + 16 mod 35 = 11, 
a9 = 11 + 18 mod 35  = 29, 
a10 = 29 + 20 mod 35 = 14.
a11 = 14 + 22 mod 35 = 1,
a12 = 1 + 24 mod 35  = 25,
a13 = 25 + 26 mod 35 = 16,
a14 = 16 + 28 mod 35 = 9,
a15 = 9 + 30 mod 35 =  4,
a16 = 4 + 32 mod 35 = 1,
a17 = 1 + 34 mod 35 = 0





Note: In this example the set [a0, a1, a2, a3, ..., a16] is equivalent to the set [182 mod 35,192 mod 35, 202 mod 35, 212 mod 35 ..., 342 mod 35], or the set [172 mod 35, 162 mod 35, 152 mod 35, 142 mod 35 ..., 12 mod 35], which is the inverse of the first half of the column at 2 in the exponentiation table of  Z35 w. In general, if Corollary 2 described here is true then this is the case for all n in Z where n is the product of two distinct odd primes.


Claim 5:  There is an element a < (n-1)/2 in Zn where n is the product of two distinct odd primes p and q  such that:

a2 a mod n and a is either equal to p or q, or a is a small multiple of p or q

Example: 
i) n = 35 a = 15 since 1515 mod 35
ii) n = 77 a = 22 since 2222 mod 35
iii) n = 55 a = 11 since 1111 mod 35

These two claims can be combined in the following function:

a_equal_to_a_squared_mod(n)
{
   index = 0;
   cur = (n-1)/2;
   squared = (((n-1)/2)*((n-1)/2))%n;
   while( squared != cur && squared != 0)
    {
    index = index + 1;
    squared = (squared + 2*index)%n;
    cur = cur - 1;
    }
  return squared;
}
//WARNING! Writing functions based on unproven claims may lead to restless nights and infinite loops.

The implementation in Javascript of the above function is iFramed below.