Modular arithmetic for encryption

Question

Fatma Alnabrisi 2019-12-1

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/494128-modular-arithmetic-for-encryption

评论： Carlos Guerra Yánez 2021-2-11

采纳的回答： Bruno Luong

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

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 ??

请先登录，再进行评论。

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

Answer 1

Bruno Luong 2019-12-1

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/494128-modular-arithmetic-for-encryption#answer_404097

编辑：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更早的评论隐藏 2更早的评论

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 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.

请先登录，再进行评论。