How to "undo" mpz_invert()
Sisyphus
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
> 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
More information about the gmp-discuss
mailing list