How to "undo" mpz_invert()
Saverio Trioni
saverio at mat.uab.es
Mon Dec 27 17:52:37 CET 2004
As the word suggests, making the "inverse" of an integer modulo p has
two properties:
1) it is an inverse, so the inverse of the inverse should be the
original number.
2) it is modulo p, so it cannod tell between x and x+p.
So what?
Well, the inverse modulo 13 of 2 is 7 (2*7=14) and the inverse of 7 is
2. But the inverse of 15 is 7 too. You cannot retrieve 15.
From the manual:
"If the inverse exists, the return value is non-zero and rop will
satisfy 0 <= rop < op2."
You can retrieve the original number if it was already less than the
"modulo". In this case you have just to re-invert your result!
Bye.
> Once mpz_invert has been applied to find an inverse modulo, is there
> some way to "undo" it?
>
> Say I have p which I want to be the inverse modulo, if it exists (assume
> it does). And I have x and n (n is the number for which gcd(x, n) = 1
> is true.)
>
> Knowing only p and n, how to find x? Apparently px + sn = 1, if p
> exists. I have no idea what s is supposed to be or how to find it. I'm
> not a mathematician, as you can see... ;-) If that's true, then I can
> find x:
>
> px + sn = 1
> px +sn - sn = 1 - sn
> px = 1 - sn
> px/p = (1-sn)/p
> x = (1-sn)/p
>
> But what is s and where does it come from/how do I get it with only p
> and n?
>
> It's been a long time since I studied algebra.
>
> Thanks,
> James
>
>
More information about the gmp-discuss
mailing list