Browse Groups

• Hi all If we are given a prime p and r
Message 1 of 2 , May 5, 2005
View Source
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?

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

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

Mark
• ... 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.