How to "undo" mpz_invert()

[Sisyphus]

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 
> get:
> 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 :-)

Cheers,
Rob