Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... 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.