Modular arithmetic for encryption

5 views (last 30 days)
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.
  1 Comment
Fatma Alnabrisi
Fatma Alnabrisi on 2 Dec 2019
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 ??

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 1 Dec 2019
Edited: Bruno Luong on 1 Dec 2019
"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
  4 Comments
Fatma Alnabrisi
Fatma Alnabrisi on 1 Dec 2019
Edited: Fatma Alnabrisi on 1 Dec 2019
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
Carlos Guerra Yánez on 11 Feb 2021
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.

Sign in to comment.

More Answers (0)

Community Treasure Hunt

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

Start Hunting!