How to "undo" mpz_invert()

[delta trinity]

>From: James Buchanan <james at jamesbuchanan.net>
>To: Sisyphus <kalinabears at iinet.net.au>
>CC: gmp-discuss at swox.com
>Subject: Re: How to "undo" mpz_invert()
>Date: Fri, 03 Dec 2004 09:51:34 +1100
>
>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?
>
>Cheers,
>James

Well, 2209 == 12682271391376756984 (mod 3527).  In plain english, this == 
sign meen 'congruent'.

The relationship is that any number for which k*n+x, where n and x are 
constant, are congruent.  Another way to see it is that they equal the same 
under modulo n.

Any congruent numbers under modulo n will have the same inverse.  The 
inverse given by the inverse function is only the simplest one, which is in 
the range of [0..n-1], as there are infinite number of way to write the 
inverse 'p' in the expression k*n + p (where n is the modulo, and p is your 
inverse).