How to "undo" mpz_invert()
delta trinity
deltatrinity at hotmail.com
Fri Dec 3 17:52:11 CET 2004
>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).
More information about the gmp-discuss
mailing list