how to calculate inverse of modulus function
조회 수: 61 (최근 30일)
이전 댓글 표시
If ax=1mod N , here x is the inverse of a, how to calculate x using matlab?
댓글 수: 0
채택된 답변
John D'Errico
2022년 1월 7일
편집: John D'Errico
2022년 1월 7일
The modular inverse you desire exists as long as a and N are relatively prime. If not, then there is a problem. The trick in MATLAB is to use GCD. For example, suppose we wish to compute the modular inverse of 3, mod 7? That is equivalent to solving the problem
mod(3*x,7) == 1
Again, we use GCD. First, read the help for GCD.
help GCD
Do you see the comment in there about the other return arguments of GCD?
[G,C,D] = gcd(3,7)
The first thing to do is to note that G, thus the GCD, is equal to 1. If it is not equal to 1, then the modular inverse will fail.
Next, see what C and D tell you.
We are told that G = A*C + B*D. So now take the modulas of that expression, with respect to B. If you look carefully, then we see that B*D is a MULTIPLE of B. So, taken mod B, that relation turns into
G = mod(A*C,B)
Do you see it now? The modular inverse of A, taken with respect to B will be the argument C from GCD. Lets try it out.
x = C
mod(3*x,7)
So -2, which is congruent to 5, mod 7, is the modular inverse of 3.
Now let me try it on another problem. what is the modular inverse of 6, mod 14?
[G,C] = gcd(6,14)
Here we seee that G = 2, so NO modular inverse exists in this case. Of course, her e we see the reason why the modular inverse fails, when the GCD (thus G) is not equal to 1. In this example, the result we get is that
2 = mod(6*C,14)
where C = -2, (or if you prefer, 12, since it is all mod 14). There is NO integer you can multiply 6 by, taken mod 14, and get 1 as a result.
Finally, one more example. what is the modular inverse of 134, mod 9937?
[G,C] = gcd(134,9937)
X = mod(C,9937) % just in case C was negative, as we saw before
mod(134*X,9937)
The modular inverse will be unique modulo N, IF an inverse exists at all. It should be clear though, that we can add any integer multiple of N to the solution X, and the result will still be a multiplicative inverse modulo N.
Finally, some years ago, I wrote a little toy called modinv. It does the computation I describe above. I've attached it to this answer.
댓글 수: 8
추가 답변 (0개)
참고 항목
카테고리
Help Center 및 File Exchange에서 Matrix Indexing에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!