How to "undo" mpz_invert()
kalinabears at iinet.net.au
Sat Dec 4 04:54:21 CET 2004
James Buchanan wrote:
> Sisyphus wrote:
>> Not sure that I follow.
>> mpz_invert(p, x, n) will set p to the inverse of x, modulo n. The
>> relationship can now be written:
>> px = sn + 1
>> and we're usually not interested in the value of s.
>> Alternatively we say that px = 1 mod n.
>> If you already have 'p' and you want to know what it's the inverse of,
>> then you simply:
>> mpz_invert(p, p, n);
>> and p will now be set to the value of x.
>> Does that help ?
> I have tried it with:
> x = 12682271391376756984
> n = 3527
> Calculating the inverse modulo of x and n is:
> p = 2288
> Now I try to get x back by calculating the inverse modulo of n and p and
> x = 2209
> So what happened to the original big x? Or is there some constant
> multiplier now that I must find so that 2209*k = the original x?
If you really do need to be able to get from 2288 back to the original
value of x, then, yes, you do need to keep track of the multiplier k
(though you haven't specified the value of k correctly).
mpz_tdiv_q(k, x, n); // k = x / n (truncated to an integer)
mpz_invert(p, x, n); // p = 2288
mpz_invert(p, p, n); // p = 2209
mpz_mul(temp, k, n); // temp = k * n
mpz_add(p, p, temp); // p = p + temp = x
Whatever it is you're trying to do, it's *not* modular arithmetic. If we
knew precisely what it was, then we would perhaps be able to specify a
better (alternative) way of doing it. I haven't actually tested any of
that ... hope I got it right :-)
More information about the gmp-discuss