residue number system in MATLAB

Hi,

I wanted to ask if it is possible to use rns in MATLAB?

If it is possible to use the residue number system in MATLAB, please guide me.

Answer 1

[Walter Roberson]

MATLAB can be used to program any deterministic calculation that can fit into your computer memory. MATLAB is Turing-complete: you could use it to write a Turing Machine to perform any deterministic calculation that you can fit. It might take a long time, but it can be done.

Residue Number System is deterministic, so YES you can program it in MATLAB.

MATLAB does not supply any functions for rns so you will need to write them yourself.

[Hana]

Thank you for Answer.

[Walter Roberson]

P = primes(19);
rns_fromdec = @(A) mod(A,P);
rns_addconst = @(A,const) mod(A + const,P);
rns_multiplyconst = @(A,const) mod(A .* const, P);
rns_multiply = @(A,B) mod(A.*B, P);

A = rns_fromdec(314159)

A = 1×8

1 2 4 6 10 1 16 13

A1 = rns_addconst(A, 1)

A1 = 1×8

0 0 0 0 0 2 0 14

A2 = rns_fromdec(314159+1)

A2 = 1×8

0 0 0 0 0 2 0 14

A1 == A2

ans = 1×8 logical array
   1   1   1   1   1   1   1   1

A3 = rns_multiplyconst(A, 15)

A3 = 1×8

1 0 0 6 7 2 2 5

A4 = rns_fromdec(314159*15)

A4 = 1×8

1 0 0 6 7 2 2 5

A3 == A4

ans = 1×8 logical array
   1   1   1   1   1   1   1   1

B = rns_fromdec(15)

B = 1×8

1 0 0 1 4 2 15 15

A5 = rns_multiply(A, B)

A5 = 1×8

1 0 0 6 7 2 2 5

A3 == A5

ans = 1×8 logical array
   1   1   1   1   1   1   1   1

[Hana]

It was a big help, I'm writing my masters thesis and part of my implementation is related to rns and I had no idea about rns codes.

Thank you for your guidance.

[Walter Roberson]

Subtraction can be done by adding negative.

For storage efficiency you could use an integer data type such as int16 provided that none of the primes exceed sqrt() of the maximum integer value.

[Walter Roberson]

Working out division could be a challenge. For powers see powermod()

[Hana]

In the first part of the implementation, which is related to hiding the text in the image, I used unit8 because each number needs 1byte to be placed in the pixel. Do you think that if I use int16, there will be no storage problem? int16 requires 2bytes. Because in encryption, first the character is converted into a number and then it is placed in each pixel.

[Walter Roberson]

Values up to 255 can easily be handled by using the primes up to 11. The maximum residue is then 10 and the maximum intermediate multiple is then 10*10 = 100 which is less than 128. So using 8 bits should work well. But I suggest int8 instead of uint8 if you want to be able to subtract

[Hana]

Thank you, absolutely correct I will definitely try your suggestion and pay attention to the points you said. If I have any questions, I will ask you.

[Walter Roberson]

P = int8(primes(11));
rns_fromdec = @(A) int8(mod(A(:),double(P)));
rns_add = @(A,B) mod(A + B,P);

Araw = randi([-255 255], 1, 5)

Araw = 1×5

57 -166 183 -113 -200

Arns = rns_fromdec(Araw)

Arns = 5×5

1 0 2 1 2 0 2 4 2 10 1 0 3 1 7 1 1 2 6 8 0 1 0 3 9

Braw = randi([-255 255], 1, 5)

Braw = 1×5

-222 45 -17 -228 -4

Brns = rns_fromdec(Braw)

Brns = 5×5

0 0 3 2 9 1 0 0 3 1 1 1 3 4 5 0 0 2 3 3 0 2 1 3 7

Crns = rns_add(Arns, Brns)

Crns = 5×5

1 0 0 3 0 1 2 4 5 0 0 1 1 5 1 1 1 4 2 0 0 0 1 6 5

Craw = Araw + Braw;
Crns == rns_fromdec(Craw)

ans = 5×5 logical array
   1   1   1   1   1
   1   1   1   1   1
   1   1   1   1   1
   1   1   1   1   1
   1   1   1   1   1

[Hana]

Hi,

I want to draw a flowchart with a numerical example of RNS to better understand how it works, but I don't know how to do it. I have a picture of the RNS architecture, but it's fuzzy.

In your opinion, how should I do this? because all three mathematical operations are included in the architecture.

image reference: https://doi.org/10.1007/s13389-020-00231-w

[Walter Roberson]

All three of the operations listed, are implimented in RNS by doing that same element-by-element operation on the RNS vectors (mod the appropriate prime), so basically that is the flow chart.

Note: at the moment I do not know any efficient method to convert an RNS vector to decimal.

[Hana]

Thank you for your answer.