23.6.16

Finding Lonely Squares Slowly

Previously I talked about how the smallest square root of a certain element can be used to find an integer k such that k^2 = k mod n where n is the product of distinct primes. It looks like the smallest square root of the same element can also be used to find an integer k such that k^2 = 1 mod n, or a lonely square.

Claim: If m is the smallest square root of (((n-1)/2)+1)2 mod n then 2*m is a lonely square.

In other words, if m is the smallest square root of (((n-1)/2)+1)2 then (2m)2 = 1 mod n

Proof: Coming soon

Example: n = 77
So ((n-1)/2)+1=39 and (((n-1)/2)+1)2 mod n = 58
The smallest square root of 58 mod 77 is 17 since 17*17 = 58 mod 77 and 17 is the smallest such element modulo 77.
Furthermore, 2*17 = 34 and 342 = 1 mod 77

ASo clearly the algorithm for finding a non-trivial lonely square consists of 2 parts:

1. Find m the smallest square root of (((n-1)/2)+1)2 mod n
2. Return 2*m, a selfie square
Below is the implementation in Javascript. Last time I checked Javascript still doesn't have a mod operator so I still use the % operator instead, which I imagine to be slower than a designated mod operator.

/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find k such that k^2 = 1 mod n where n
must be the product of two distinct primes
---------------------------------------------------- */

function find_square_root_slowly(n, k)
{
var index = 1;
var sq_rt;
while(sq_rt != k)
{
index = index+1;
sq_rt = (index*index)%n;
}
return index;
}

function find_lonely_squares_slowly(n)
{
var halfie = ((n-1)/2)+1;
var square = (halfie*halfie)%n;
var sq_rt = find_square_root_slowly(n, square);
//to get another lonely square, subtract this one from n
var lonely = 2*sq_rt;
return lonely;
}