Re: inverse mod n

In article <1143649185.676109.291850@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"perltcl@xxxxxxxxx" <perltcl@xxxxxxxxx> wrote:
given x,n
x,n:integers
n is not prime, maybe large

is it a hard problem to find x*y=1 mod n
i.e. the inverse of x mod n

It is quite easy unless x and n have a common factor greater than 1.
To check whether there is a common factor and solve for the inverse,
take a look at <http://www.whim.org/nebula/math/euclid-wallis.html>.

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
.

Relevant Pages

  • Re: Modular cube root question
    ... Paul Rubin wrote: ... > Yes, that's correct, e must have no common factors with phi. ... suppose it's just because when I read "this is a hard problem", ... using gcd in determining e. ...
    (sci.crypt)
  • Re: Euler integration
    ... maybe explain your symbols a bit, what are the signals uand ... it were to be read in a monospaced font because that can be the only ... common assumption. ...
    (comp.dsp)
  • Join on multiple columns?
    ... I have two tables of about 10 columns each, which share 5 common ... to be viewed in a monospaced font: ... Desired Query Output ...
    (microsoft.public.access.queries)