Re: question on trying to use quadratic residues to eliminate needless checks

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* American Citizen [2025-03-25 01:09]:
[...]
> > This strategy reduces the number of full tests by a factor 1/2^(k+1).
> 
> But am I still facing the (r^2+s^2) mod N cost?

Certainly not: you precomputed the r^2 mod N (and the s^2 mod N) separately
[a linear cost, not quadratic as your number of checks]

Hence r^2 + s^2 mod N is an simple addition mod N

  ulong
  Fl_add(ulong a, ulong b, ulong N)
  {
    ulong res = a + b;
    return (res >= N || res < a) ? res - N : res;
  }

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/