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]