Finding Selfie Squares Slowly

Some time ago I conjectured that there is an element k such that k^2=k mod n when n is the product of two distinct primes.

In fact, I conjectured that there are exactly 2 such elements mod n when n is the product of two distinct primes, located at equal distance from the element at (((n-1)/2)+1).

Furthermore, I conjectured that these two elements, which I called "selfie squares"*, are at a distance of smallest_sqrt((((n-1)/2)+1)²) where smallest_sqrt is the smallest square root of the element at (((n-1)/2)+1)² mod n since I also conjectured that (((n-1)/2)+1)² mod n has exactly 4 square roots.

And just to top things up, I conjectured that the element k such that k² = k mod n when n is the product of two distinct primes p<q is either equal to p or a small multiple of p if k < ((n-1)/2)+1),  or it is equal to q or a small multiple of q if k > ((n-1)/2)+1)

That's a lot of conjecturing so I decided to implement the algorithm for finding selfie squares with the square root of the middle-ish element using Javascript. By the way, vanilla Javascript doesn't magically take care of bigints behind the scenes as I had hoped for years so the largest n that this implementation can handle is about 8 digits long.

To recap, these are the main steps of the algorithm for finding an integer k such that  k² = k mod n  using the square root of ((((n-1)/2)+1)² mod n):

1.  Calculate k=(((n-1)/2)+1) 
2.  Calculate b = the smallest square root of((((n-1)/2)+1)² mod n)
3.  Return m = k + b mod n

This algorithm returns the largest selfie square. To get the smallest selfie square, replace m = k + b mod n with m = k - b mod n

Obviously, the potential bottleneck here is finding the smallest square root of((((n-1)/2)+1)² mod n). Luckily there appears to be a nifty pattern that could help predict exactly where that smallest square root is without having to do what I'm doing below.

Below is a brute force implementation of finding the smallest square root of((((n-1)/2)+1)² mod n) because I really don't want to find out if I'm wrong about that pattern just yet.

/* -------------------------------------------------  
 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 = k 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_selfie_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 largest selfie square, replace the + with a -
 var selfie = (halfie + sq_rt)%n;
 return selfie;
}

And below is the full implementation, which finds the bigger selfie square. For faster factoring of n both selfie squares are required.



*In this blog I come up with new definitions mostly because Mathematics has less definitions to memorize and is more fun to do than Biology yet Biology attracts more students than Mathematics so I figured maybe it is because of the lack of definitions.