Tonelli-Shanks algorithm

[Ramón T. B.]

Taking advantage of the beautiful implementation of the Tonelli-Shanks algorithm made by David (modular_sqrt), I have adapted an implementation for calculating the modular square root of a composite number, that I took from M. Welschenbach. Working with a composite number 'n'  that factorize in a simple way of two primes: n = p * q
With this function (I call it 'modular_sqrt_pq' in accordance with David suggestion) it is easy to implement a simple-raw version of the Rabin encryption.
I'm sure it can be improved. Please let me know any suggestions.

Regards: framontb

// find x^2 = a mod p*q
// return
// 0 if a is quadratic residue mod p*q
//-1 otherwise
// x[0], x[1], x[2], x[3] are the four solutions

int modular_sqrt_pq(mpz_t x[], mpz_t a, mpz_t p, mpz_t q)
{
mpz_t n, xp, xq, u, v;
mpz_inits(n, xp, xq, u, v, NULL);

if (!mpz_sgn(a))  // a is zero
{
mpz_set_ui(x[0], 0UL);
mpz_set_ui(x[1], 0UL);
mpz_set_ui(x[2], 0UL);
mpz_set_ui(x[3], 0UL);
return 0;
}

if ( 1 != modular_sqrt(xp, a, p) || 1 != modular_sqrt(xq, a, q) )  // a is quadratic non-residue mod p or q
{
return -1;
}

mpz_mul(n, p, q);
mpz_gcdext(x[0], u, v, p, q);
mpz_mul(u, p, u);
mpz_mul(u, xq, u);
mpz_mul(v, q, v);
mpz_mul(v, xp, v);
mpz_add(x[0], u, v);
mpz_mod(x[0], x[0], n);

mpz_sub(x[1], n, x[0]);
mpz_sub(x[2], u, v);
mpz_mod(x[2], x[2], n);
mpz_sub(x[3], n, x[2]);

mpz_clears(n, xp, xq, u, v, NULL);
return 0;
}



________________________________
 De: David Gillies <daggillies at gmail.com>
Para: gmp-discuss <gmp-discuss at gmplib.org> 
Enviado: Miércoles 17 de abril de 2013 0:01
Asunto: Re: Tonelli-Shanks algorithm
 

OK, fair enough, good point, then the prototype should be changed to int
modular_sqrt(mpz_t x,mpz_t q,mpz_t n); for clarity




On Tue, Apr 16, 2013 at 3:38 PM, David Harvey <d.harvey at unsw.edu.au> wrote:

>
> On Apr 17, 2013, at 6:30 AM, David Gillies wrote:
>
> > There was a bit of discussion last week about finding quadratic residues,
> > so I decided to implement Tonelli-Shanks for fun. I coded it up last
> night
> > and here it is. It seems to work but if anyone can spot any glaring holes
> > then let me know.
>
> no comment on the code, I only want to correct a nomenclature problem that
> has occurred a few times on this list:
>
> you mean finding a (modular) square root, not a quadratic residue. Finding
> a quadratic residue is a much easier problem!
>
> david
>
>


-- 
David Gillies
San Jose
Costa Rica
_______________________________________________
gmp-discuss mailing list
gmp-discuss at gmplib.org
https://gmplib.org/mailman/listinfo/gmp-discuss