inverse of mod function

80 次查看（过去 30 天）
aaru sri
aaru sri 2019-1-7
评论： Jan 2019-1-7
x=amod(256);
now i hv to find a where x is given
  5 个评论
显示 3更早的评论
Jan
Jan 2019-1-7
@aaru sri: "have" and "can" is easier to read for non-native speakers than "hv" and "cn". Thanks.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Star Strider
Star Strider 2019-1-7
As a general rule, no, you cannot uniquely determine whatever ‘a’ is. The mod function returns the remainder after division, so you can only get a set of possible numbers (that is infinite).
Example:
a_in = 1234
x=mod(a_in,256);
a_out = (0:8)*256 + x
mod_a = mod(a_out,256)
producing:
a_out =
210 466 722 978 1234 1490 1746 2002 2258
mod_a =
210 210 210 210 210 210 210 210 210
  3 个评论
显示 1更早的评论
John D'Errico
John D'Errico 2019-1-7
Modular inverses are indeed terribly useful in mathematics. When the modulus (m) is prime, then all numbers (except for 0) have a modular inverse, and that inverse is unique within the set of integers 0<x<m.
Even when the modulus is composite, you need the modulus to be co-prime to the value in question for a modular inverse to exist. For example, if we consider the multiplicative group of integers modulo 12, then 7 has an inverse, since it is co-prime with 12. In fact, 7 is its own inverse. So we have
mod(7*7,12)
ans =
1
However, 3 does not have an inverse in this group, since there is no integer x such that mod(3*x,12)==1.
Star Strider
Star Strider 2019-1-7
The mod function works with 3D matrices:
M = randi(999, 3, 3, 3);
modM = mod(M,256);
The same approach applies, as do the conditions I mention in my Answer.
However, it now seems that you are actually using a different function (that appears to do modulation and demodulation), not the MATLAB mod function.

请先登录，再进行评论。

更多回答（1 个）

John D'Errico
John D'Errico 2019-1-7
编辑：John D'Errico 2019-1-7
Not that difficult to do.
I implemented it in the form of minv.m, in my VPI toolbox.
help minv
help minv
vpi/minv: the inverse of a modulo p, such that mod(a*x,p) == 1
usage: x = minv(a,p)
if a and p are relatively prime (co-prime)
uses the extended Euclidean algorithm to find
a solution to the problem a*x - q*p = 1
minv returns an empty result if a and p are
relatively prime, (also known as coprime.) A
warning will be generated in this event.
Example:
a = 35;
p = vpi(2^31 - 1);
ainv = minv(a,p)
ainv =
1656630242
mod(a*ainv,p)
ans =
1
Example:
a and p must be coprime, or a warning will
be generated. Since no inverse exists, an
empty will be returned.
minv(3,15)
Warning: a and p must be relatively prime, gcd(a,p) == 1
ans =
[]
VPI/minv uses the extended Euclidean algorithm to solve the problem.
You can also find a modular inverse in the Java.BigInteger tools. I'd look at java.math.BigInteger.modInverse. (My replacement for VPI is VPIJ, which is essentially a wrapper for the Java BigInteger tools. vpij/minv uses the Java modInverse.)
Some implemetations of tools where powermod is a defined operator allow a power of -1. That would effectively denote the modular inverse. I recall the Python powermod utility does it that way. Arguably, had I thought of it when I wrote VPI, that is where I should have implemented the modular inverse computation. Oh well, I did not.
Finally, I just checked the symbolic toolbox. Surprisingly, it does not appear a modular inverse computation is provided there at all, under any guise, even though they do provide a symbolic version of powermod.
  2 个评论
aaru sri
aaru sri 2019-1-7
i hv uint8 values in x so hence ....can u make a code and help me
x=mod(a,256);
John D'Errico
John D'Errico 2019-1-7
编辑：John D'Errico 2019-1-7
Not sure why you accepted Star's answer, since it does not actually give you what you wanted. Que sera, sera.
Regardless, what you ask for is trivial. You want to compute the modular inverse of uint8 numbers? Nothing stops you from downloading my vpi toolbox, and using minv.
However, if you are doing MANY computations of this form, minv would not be terribly efficient. So the simple answer is to create a lookup table.
If your modulus is 256, then ALL even numbers have no modular inverse, but all odd integers DO have a modular inverse, and that inverse is unique within the group of integers modulo 256. Now, while I could build the desired lookup table using my minv utility, 256 is such a small number, it is easy to do using brute force.
t = 1:2:255;
[I,J] = find(mod(t'.*t,256) == 1);
minv256 = zeros(1,255);
minv256(t) = t(I);
So the first 10 elements of this table are:
minv256(1:10)
ans =
1 0 171 0 205 0 183 0 57 0
The modular inverse of 3 is minv256(3)==171. We can test that claim as:
mod(3*minv256(3),256)
ans =
1
As you can see, I created minv256 as a regular double vector, because in order do the test multiply as I just did, it creates numbers larger than 255, so 3*171=513 is greater than 255. That would fail for uint8 integers, since it would overflow.
But now you can use use a direct lookup into that vector to return the modular inverse for any odd number x. As you can see, it works:
mod(t.*minv256(t),256)
ans =
Columns 1 through 24
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Columns 25 through 48
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Columns 49 through 72
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Columns 73 through 96
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Columns 97 through 120
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Columns 121 through 128
1 1 1 1 1 1 1 1
You can feel free to convert this vector into uint8 yourself, using the uint8 function.
uint8(minv256)
ans =
1×256 uint8 row vector
Columns 1 through 24
1 0 171 0 205 0 183 0 57 0 163 0 197 0 239 0 241 0 27 0 61 0 167 0
Columns 25 through 48
41 0 19 0 53 0 223 0 225 0 139 0 173 0 151 0 25 0 131 0 165 0 207 0
Columns 49 through 72
209 0 251 0 29 0 135 0 9 0 243 0 21 0 191 0 193 0 107 0 141 0 119 0
Columns 73 through 96
249 0 99 0 133 0 175 0 177 0 219 0 253 0 103 0 233 0 211 0 245 0 159 0
Columns 97 through 120
161 0 75 0 109 0 87 0 217 0 67 0 101 0 143 0 145 0 187 0 221 0 71 0
Columns 121 through 144
201 0 179 0 213 0 127 0 129 0 43 0 77 0 55 0 185 0 35 0 69 0 111 0
Columns 145 through 168
113 0 155 0 189 0 39 0 169 0 147 0 181 0 95 0 97 0 11 0 45 0 23 0
Columns 169 through 192
153 0 3 0 37 0 79 0 81 0 123 0 157 0 7 0 137 0 115 0 149 0 63 0
Columns 193 through 216
65 0 235 0 13 0 247 0 121 0 227 0 5 0 47 0 49 0 91 0 125 0 231 0
Columns 217 through 240
105 0 83 0 117 0 31 0 33 0 203 0 237 0 215 0 89 0 195 0 229 0 15 0
Columns 241 through 256
17 0 59 0 93 0 199 0 73 0 51 0 85 0 255 0
Again, all even numbers have no modular inverse in the field of numbers modulo 256, so my table contains 0 for those inputs.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Number Theory 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by