Squaring Question

[Marc Glisse]

On Thu, 19 Feb 2009, Digital Parasite wrote:

> If I need to square a value many times in a loop, is using mpz_mul the
> fastest way in GMP to achieve this or is there another function that
> is better specifically for squaring?

mpz_mul already checks whether the 2 arguments are the same and uses a 
special code in this case, so mpz_mul seems appropriate indeed.

> For example, some sample code below:
>
> // r = 6
> mpz_set_ui(r,6);
> // q = 350000
> mpz_set_ui(q,6);
> // p = 2^q so in this case 350000 bits
>
> for (j=1; j <= mpz_get_ui(q); j++)

Not crucial here, but it is better to avoid the function call here and do 
it once before starting the loop.

> {
> 	// t = r^2 - 2
> 	mpz_mul(t, r, r);
> 	mpz_sub_ui(t, t, 2);
> 	// r = t | p
> 	mpz_mod(r, t, p);

Note that there is a special version of mpz_mod for powers of 2.

> }

I think the biggest issue here is to prevent gmp from computing more than 
q bits in the product. Although it is doable, I don't know of a gmp 
function that does this. Someone more familiar with the code may know 
better.

-- 
Marc Glisse