mpz reuse test takes too much time

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

>> Now we have two possible strategies:
>>
>> 1. Call mpn_gcdext (B, A), which produces T. And compute S as
>>
>>      S = (G - T B) / A
>
> This means computing both cofactors, right?

Yes.

>> 2. First do a division up front,
>>
>>      B = Q A + R
>>
>>    and call mpn_gcdext(A, R). We then get a cofactor S', of m limbs. But
>>    we also need the other cofactor T', because the wanted cofactor S is
>
> This also means computing both cofactors, don't it?

I think you're right. We compute S' and T' (gcdext after initial
division), and then construct S. So I didn't say that we compute T. But
in fact, T' = T, since T = (B/G)^-1 (mod A/G), T' = (R/G)^-1 (mod A/G),
and B = R (mod A). Right?

> I assume that the best way to compute both cofactors is the one currently
> implemented in mpz_gcdext.

It's best under the theory think that a few large multiplications at the
end is more efficient than building up the other cofactor incrementally.
But might not be true in all cases...

But we should probably reorganize mpn_gcdexp first, before evaluating
other strategies regarding the larger cofactor. The divide-and-conquer
thing should be done slightly different, and that might make it
cheaper to get the other cofactor at least for large operands.

>> And a third strategy could be to extend mpn_gcdext to support A < B, and
>> hence compute the larger cofactor directly. But I'd guess that would be
>> more work, since gcdext uses a quadratic algorithm for much larger sizes
>> than for multiplication and division.
>
> Actually mpn_gcdext supports A<B, but it requires to zero-pad A so that
> its length in limbs is not smaller than the length of B.

Maybe the way mpn_gcdext handles this can be more or less unchanged. But
we shouldn't have to zeropad the input.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.