"Marco Bodrato" <bodr...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel