Re: inverse modulos

From: Ted Hwa (hwatheod_at_xenon.Stanford.EDU)
Date: 12/03/04 

Date: Fri, 3 Dec 2004 05:12:53 +0000 (UTC)

Johnathan Doe <No-spam-here-johnathan_doe@!!!nospamthanks!!!fastmail.com.au> wrote:
: Pawel Gladki wrote:
:> Solving diophantine equations is easy... it uses the extended Euclidean
:> algorithm, for details see e.g.:
:>
:> "http://www.win.tue.nl/~ida/demo/c1s3f2.html"

: Hi, thanks for this. There is a function in the GMP library that makes
: use of the extended Euclidean algorithm, but it's not giving the result
: I want. I thought that the inverse modulo was supposed to be unique
: where it existed, but I must have misunderstood that.

The inverse of a modulo m is unique *modulo m*, if it exists.

For example, a = 17, m = 5. The inverse of 17 modulo 5 is 3, since
17*3 = 51 = 1 + 5*10. (k=10 in the notation of your earlier posts).
I could add any multiple of m (in this case 5) to 3, and it would
still be an inverse: for example 8,13,18,... but these are all
congruent modulo 5 (i.e. they differ from each other by a multiple
of 5). The inverse is unique modulo 5.

In general, if a-b is divisible by m, then we say that a and b are
"congruent" modulo m, and write a = b (mod m).

Ted

Relevant Pages

  • Re: Is there any COBOL program for verify the SSN?
    ... Modulus 11 is NOT the same as Modulo 11. ... The Luhn algorithm or Luhn formula, also known as the "modulus 10" or "mod 10" algorithm, is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. ...
    (comp.lang.cobol)
  • Re: Testing RAM
    ... Is there something that the test does on that particular motherboard AND memory stick combo? ... If I use two sticks in any combination of the three available slots, then errors will arise during the MemTest86+ Modulo 20 algorithm. ...
    (microsoft.public.windowsxp.hardware)
  • 8-bit CRC
    ... I have the spec ETSI TS 101 369 which describes the CRC ... divided (modulo 2) by the generator polynomial ... What I really want is the C code that implements the algorithm. ...
    (comp.arch.embedded)
  • Re: RSA Proof using CRTs
    ... Because then modulo q we have ... When two integers are congruent modulo p and modulo q, CRT says they ... is the keyword 'Garner's algorithm'. ...
    (sci.crypt)
  • Re: index calculus and (Zn*,*)
    ... > modulo a composite, but doing it will require factoring n. ... > it first and then applying index calculus modulo the prime divisors. ... for solving equation c=m^d mod n on d. ... But can we use any other algorithm for solving DLP in this ...
    (sci.crypt)