Re: [PrimeNumbers] r*s = 1 mod p
- On Thursday 05 May 2005 16:41, you wrote:
> Hi allYes, of course, that's the operation of modular inversion. You can use
> 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?
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 satisfiesSure, that's trivial.
> 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?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.
[Non-text portions of this message have been removed]