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;
}