Year 12s: what will be the first way you research your future options? >>

Year 12s: what will be the first way you research your future options? >>

Year 12s: what will be the first way you research your future options? >>

Inverse of a number

In congruences, I have a number 'a', which is co prime with another number 'n'. I factorized 'n' into primes and have worked out phi of 'n'.

The question is to do with RSA.

The question is to workout the decoding element x, and in brackets it's written, i.e a^(-1) mod phi(n).

So does that mean that I need to workout the inverse of a and that will give me the decoding element x?

If so, how do I do this?

(edited 13 years ago)

The inverse of

a

mod

\phi (n)

is the unique integer

x

satisfying

ax \equiv 1

mod

\phi (n)

To find

x

, write the above congruence as a linear equation and use Euclid's Algorithm.

(edited 13 years ago)

OP

Original post by Dragon

The inverse of

a

mod

\phi (n)

is the unique integer

x

satisfying

ax \equiv 1

mod

\phi (n)

To find

x

, write the above congruence as a linear equation and use Euclid's Algorithm.

By linear equation, do you mean writing it like ax + by = 1

Where a is just a and b is phi(n)?

Yep.

Quick Reply

Latest

Trending

Trending

Articles for you

What jobs could you do with a business degree?

What jobs could you do with a business degree?

Should you choose a campus or city university?

Should you choose a campus or city university?

Writing a history personal statement: expert advice from universities

Writing a history personal statement: expert advice from universities

English and history students share why they loved their degrees

English and history students share why they loved their degrees