Sorry, an error occurred while loading the content.

## Re: [PrimeNumbers] Calculating the inverse of a (mod p)

Expand Messages
• ... Hash: SHA1 ... For the purposes of what you re doing (I ve been at Mikko Tommila s page before and implemented the same thing), this is just a
Message 1 of 5 , Aug 5, 2004
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thursday 05 August 2004 21:28, you wrote:
> The web page: http://www.apfloat.org/crt.html contains the tantalizing but
> (to me) mysterious line,
>
> "Tk is the inverse of P/pk (mod pk). The inverse of a (mod p) can be found
> for example by calculating a^(p-2) (mod p). Note that a*a^(p-2)=a^(p-1)=1
> (mod p)."
>
> Can someone explain this to me in a little more operational detail so I can
> try to do it?

For the purposes of what you're doing (I've been at Mikko Tommila's page
before and implemented the same thing), this is just a precomputation. This
is evidenced by the fact that the page suggests using a powering procedure --
nobody implements modular inversion that way for `on-line' computations. So
if you don't want to, you don't need to know about it: just grab Pari/GP at
http://pari.math.u-bordeaux.fr/ and do something like

lift(Mod(a,pk)^(-1))

and you're done. Now if you really want to learn about computing inverses, the
best freely available literature I know is the Handbook of Applied
Cryptography, by Menezes, van Oorschot and Vanstone. There you can learn a
more useful algorithm for modular inversion, called Euclid's Extended
Algorithm for GCDs. You can download the book at
http://www.cacr.math.uwaterloo.ca/hac/.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFBEt2/MvCZlCdExvkRAmoFAJ9ssUJpvCbwfuoHNRna8ZAWbzq9KwCeMm7I
+GEPI2rRC3VTiiDwW2E/+aQ=
=fyS9
-----END PGP SIGNATURE-----
Your message has been successfully submitted and would be delivered to recipients shortly.