5.7.16

Recurring Oddities

I already provided a brute force algorithm for finding the smallest square root of ((n+1)/2)^2 mod n where n is the product of distinct primes. That algorithm simply multiplies progressively larger integers and takes the remainder after dividing n.

I came across a recurrence relation, which can be used to generate squares of consecutive integers  modulo n and it is based on the following observation: each subsequent square term is equal to the previous square term plus an odd integer, which is calculated using the index of the previous term.

Consider the sequence formed by squaring integers consecutively:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225,... [A000290]

Conjecture: If a2 = 4 then ai = ai-1 + (2*(i-1) + 1) where i > 2

This conjecture seems to hold for finite fields as well so it can be easily implemented.

While I still consider it a brute force function, it is a tad more elegant brute forcing than multiplying and dividing to find the remainder. The previous Javascript function used the remainder operator because Javascript doesn't have a modulo operator yet.

Note that by using the recurrence relation above I eliminate the need to use the modulo or remainder operator since there are no large multiplications because the skewy is an integer smaller than (n+1)/2 by definition.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find x such that x the smallest square root of
 ((n+1)/2)^2 mod n called the skewy mod n
 ---------------------------------------------------- */  
//n must be the product of 2 distinct primes, k is ((n+1)/2)^2 mod n
function find_square_root_slowly_recurrence(n, k)
{
 var index = 2;
 var sq_rt = 4;
 while(sq_rt != k)
 { 
  sq_rt = sq_rt + (2*index + 1);
  index = index+1;
  if(sq_rt > n){sq_rt = sq_rt - n;}  
 }
 return index;
}