## 18.6.16

### 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)2) where smallest_sqrt is the smallest square root of the element at (((n-1)/2)+1)2 mod n since I also conjectured that (((n-1)/2)+1)2 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)2 mod n):
1.  Calculate k=(((n-1)/2)+1)
2.  Calculate b = the smallest square root of((((n-1)/2)+1)2 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)2 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)2 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.