## Re: [PrimeNumbers] r*s = 1 mod p

Expand Messages
• ... Yes, of course, that s the operation of modular inversion. You can use Euclid s extended algorithm to find it, or maybe compute r^(p-2) mod p since
Message 1 of 2 , May 5, 2005
On Thursday 05 May 2005 16:41, you wrote:
> Hi all
>
> If we are given a prime p and r < p, can we easily find the (unique)
> s < p such that
>
> r*s = 1 mod p?

Yes, of course, that's the operation of modular inversion. You can use
Euclid's extended algorithm to find it, or maybe compute r^(p-2) mod p since
r*r^(p-2) == r^(p-1) == 1 mod p.

> Let's assume we can. Then of course the t < p that satisfies
>
> r*t = n mod p
>
> for any n < p is exactly
>
> t = (s*n) mod p

Sure, that's trivial.

> But can we find the original s (easily) in the first place?

You just assumed up there that it was possible. Or do you mean `more easily
than computing rs == 1 mod p'? If so, not that I know of, unless rt < p and s
= rt/n by exact division, but that rarely happens.

You should be more exact in your queries, and avoid stating trivialities,
otherwise you're just going to confuse others that try to help.

Décio

[Non-text portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.