inverse of mod function

x=amod(256);

now i hv to find a where x is given

[madhan ravi]

not clear , mod requires two inputs

[aaru sri]

here i hv x as an matrix form

x=mod(a,256);

now going reverse i hv to find a in my program ..how cn i do it

[KALYAN ACHARJYA]

amod -Analog passband modulator??

Are you looking for this one?

[aaru sri]

yup

[Jan]

@aaru sri: "have" and "can" is easier to read for non-native speakers than "hv" and "cn". Thanks.

Answer 1

[Star Strider]

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

[aaru sri]

here u hv taken 8 elements but i hv x as an 3d matrix so what range i will give

to hv a !!!!

[John D'Errico]

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]

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.

Answer 2

[John D'Errico]

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.

[aaru sri]

i hv uint8 values in x so hence ....can u make a code and help me

x=mod(a,256);

[John D'Errico]

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.