How to "undo" mpz_invert()
james at jamesbuchanan.net
Wed Dec 1 16:19:22 CET 2004
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
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
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.
More information about the gmp-discuss