Modular arithmetic for encryption

12 次查看（过去 30 天）
Fatma Alnabrisi
Fatma Alnabrisi 2019-12-1
评论： Carlos Guerra Yánez 2021-2-11
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 个评论
Fatma Alnabrisi
Fatma Alnabrisi 2019-12-2
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 ??

请先登录，再进行评论。

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

采纳的回答

Bruno Luong
Bruno Luong 2019-12-1
编辑：Bruno Luong 2019-12-1
"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 个评论
显示 2更早的评论
Fatma Alnabrisi
Fatma Alnabrisi 2019-12-1
编辑：Fatma Alnabrisi 2019-12-1
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 2021-2-11
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.

请先登录，再进行评论。

更多回答（0 个）

类别

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

标签

Community Treasure Hunt

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

Start Hunting!

Translated by