Modular arithmetic for encryption

I'm trying to implement an encryption technique using Matlab for a college project.

However I'm facing some difficulties in modular calculation.

For example I have matrix A = [ 1 , 0 ; 1/2 , 1 ] , and I need to calculate A mod 29.

what I'm getting in matlab is [ 1 , 0 ; 1/2 ,1 ],

while what I'm supposed to get is [ 1 , 0 ; 15 , 1 ] as in https://planetcalc.com/8326/

Actually I don't understand the math behined the fact that (1/2 mod 29) = 15 .

So, if any one can help me in getting this result in Matlab, I would be grateful.

[Fatma Alnabrisi]

Can someone please help me in finding modular of fractions.

My input is real number matrix A and I need to get (A mod 29)

The output should be integer matrix.

How to code this function in Matlab ??

Answer 1

[Bruno Luong]

"1/2" is integer (let us call it "a") so that

a*2 = 1 mod 29

This can be obtained by GCD function

>>  [~,a]=gcd(2,29)

a =

   -14

>> a = mod(a,29)

a =

    15

[Fatma Alnabrisi]

Thank you very much for your answer.

But actually I didn't get it 100% ..

what if I need to calculate 3/2 mod 29 .. I'm getting wrong answer !

>> b = 3/2

b =

    1.5000

>> [~,b]=gcd(2,29)

b =

   -14

>> b = mod (b,29)

b =

    15

[Bruno Luong]

You should wonder where 3 is used in your code (no where).

Here is the result

b = 3/2 = 3*(1/2) = 3*a = 3*15 = 45 = 16 mod 29

[Fatma Alnabrisi]

well, based on what you've mentioned can you please help me in writing a code which takes any matrix A as an input, and finds A mod 29 (considering that the elements of A are real numbers and the outputs have to be integers.)

Thank you

[Carlos Guerra Yánez]

I might be late, but I'll try to answer you just in case it could help anyone else...

I understood that we have the ℚ-coefficient matrix given as

And we want to calculate an associated -coefficient matrix...

First of all, if we apply the mod(n,m) function in MATLAB with floating point values (which is the case of this matrix, the value is a floating point value), the function will return the result of applying the rational modulo operation... i.e. just forcing the values to be in the interval by removing or adding m as much times as it is needed.

However, what we want to obtain is the ℤ modulo operation. This operation will return the remainder of the division of n and m as integers. But is not an integer, so what we are looking for is the inverse element of 2 in the field. This element is defined as the number (between 0 and ) that will give an element of the residue class of 1. For the number two, it would be , because, as we can see

So how can we find the modular inverse of a given number (if it exists at all)? The Extended Euclidean Algorithm is what we are looking for...

In this case, a single iteration would give us the modular inverse

Which we can rearrange as

And reducing this expression modulo it would become

Which is just what we are looking for... Summarizing, the function that you have to implement, must obtain the modular inverse by applying the Extended Euclidean Algorithm.

Cheers,

Carlos.