Magma

70 Reputation

4 Badges

4 years, 330 days

MaplePrimes Activity


These are replies submitted by Magma

@Carl Love I would like to kindly request you to see my new post. I really need your help. Thanks in advance for your consideration of this request.

@Carl Love 

When I changed datatype= integer[8] to datatype= integer[4] then it made the following error 

Error, (in Paar) unable to store 'HFloat(1.0)' when datatype=integer[4]

I installed the 64 bit version of Maple 15 on a computer with windows 7 (64 bit). My results was the same as you but in 242 seconds. Therefore I want to install the 64 bit version of Windows 7 and then install the 64-bit Maple 15.

With the best regards and wishes for you

@Carl Love Excuse me, did you test the code for a 128x128 binary matrix.

When I run the code for a 128x128 binary matrix, then it makes an error as follows 

Error, (in Paar) Maple was unable to allocate enough memory to complete this computation.  Please see ?alloc

I used 32 bit version of Windows 7 with 4GIG RAM.

@Carl Love The time complexity of your code in comparison with the original published Paar's algorithm is valuable and as you said this might be worth publishing. In continue I want to suggest an improvement for reduction of number of required XOR.

Consider the following 8x8 binary matrix 

A:=

You can check that the number of required XOR for the  implementation of the matrix A is 10 XOR when you run the Paar algorithm.

Set X:=[x_1,x_2,.,.x_8]. Then the cost of implementation X.A is equal to the cost of the equation (1) in my question.

Based on my question the cost of f[i] with i=1..7 is equal to 9 XOR. Now the question is that why the Paar algorithm computed one XOR more than the required XOR.

One answer is that in the question I selected columns with the minimum number of 1's and the Paar algorithm starts with  columns with the maximum number of 1's.

I suggest you if you edit your code until that the output your edited code for the matrix A be 9 XOR, then your solution is a new improved heuristics for Short Linear Programs.

Although this types of improvement is recently done (you can see the following two papers), the time complexity of your code is amazing

https://eprint.iacr.org/2019/847.pdf

https://link.springer.com/chapter/10.1007/978-3-030-26834-3_7

 Thanks for everything.

@Carl Love Please let me that I delete some my  unnecessary comments. Because I want to suggest an improvement for your nice code that is valuable in cryptography.Also I tested your excellent code with the binary matrices in the following link

https://github.com/rub-hgi/shorter_linear_slps_for_mds_matrices/tree/master/matrices_bp_format

and I checked the results with Table 3 in the following paper

https://eprint.iacr.org/2017/1151.pdf

All results were correct. Thanks for your effort Prof Car.Love. You are man of Maple. 

@Carl Love 

I want to have a request about your code. Consider the C++ code of Parr algorithm that has been given in the following link (which is called "int paar_algorithm1(uint64_t *input_matrix)")

https://github.com/rub-hgi/shorter_linear_slps_for_mds_matrices/blob/master/paar.cpp

In the mentioned algorithm, first receives an nxn binary matrix A and then the algorithm computes the following integer number

xor_count=Occurrences(1, convert(A, list))-n

Also in each step, the algorithm obtains an integer number hw_max and then computes

xor_count -= (hw_max-1);

I wrote the Maple code of this algorithm as follows

``

restart

``

with(LinearAlgebra); with(ListTools)

``

xo := proc (M::list, N::list, r::integer, a::integer) local E, i; E := Matrix(r, 1, 0); if a = 1 then for i to r do if M[i]+N[i] = 2 then E[i, 1] := 1 end if end do else for i to r do if M[i]+N[i] = 1 then E[i, 1] := 1 end if end do end if; return E end proc

``

Parr := proc (R::Matrix) local n, m, cont, u, hmax, i, j, hw, imax, jmax, B, E, F, k, A; A := copy(R); n := RowDimension(A); m := copy(n); cont := Occurrences(1, convert(A, list))-n; u := 1; while 0 < u do hmax := 0; for i to m-1 do for j from i+1 to m do hw := Occurrences(1, convert(xo(convert(Column(A, i), list), convert(Column(A, j), list), n, 1), list)); if hmax < hw then hmax := hw; imax := i; jmax := j end if end do end do; if 1 < hmax then B := xo(convert(Column(A, imax), list), convert(Column(A, jmax), list), n, 1); A := copy(`<|>`(A, B)); E := xo(convert(Column(A, imax), list), convert(xo(convert(B, list), [seq(1, i = 1 .. n)], n, 0), list), n, 1); F := xo(convert(Column(A, jmax), list), convert(xo(convert(B, list), [seq(1, i = 1 .. n)], n, 0), list), n, 1); for k to n do A[k, imax] := E[k, 1]; A[k, jmax] := F[k, 1] end do; cont := cont-hmax+1; m := m+1 end if; if hmax < 2 then u := 0 end if; unassign('B, E, F, hmax, hw, i, imax, jmax, j, k') end do; unassign('u, m, n'); return cont end proc

``

R := Matrix(8, 8, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 1, (1, 4) = 1, (1, 5) = 1, (1, 6) = 1, (1, 7) = 1, (1, 8) = 1, (2, 1) = 1, (2, 2) = 0, (2, 3) = 1, (2, 4) = 1, (2, 5) = 1, (2, 6) = 1, (2, 7) = 0, (2, 8) = 1, (3, 1) = 0, (3, 2) = 1, (3, 3) = 0, (3, 4) = 1, (3, 5) = 1, (3, 6) = 1, (3, 7) = 1, (3, 8) = 1, (4, 1) = 0, (4, 2) = 0, (4, 3) = 1, (4, 4) = 0, (4, 5) = 1, (4, 6) = 1, (4, 7) = 1, (4, 8) = 1, (5, 1) = 0, (5, 2) = 0, (5, 3) = 0, (5, 4) = 1, (5, 5) = 0, (5, 6) = 1, (5, 7) = 1, (5, 8) = 1, (6, 1) = 0, (6, 2) = 0, (6, 3) = 0, (6, 4) = 0, (6, 5) = 1, (6, 6) = 0, (6, 7) = 1, (6, 8) = 1, (7, 1) = 0, (7, 2) = 0, (7, 3) = 0, (7, 4) = 0, (7, 5) = 0, (7, 6) = 1, (7, 7) = 0, (7, 8) = 1, (8, 1) = 1, (8, 2) = 1, (8, 3) = 1, (8, 4) = 1, (8, 5) = 1, (8, 6) = 1, (8, 7) = 0, (8, 8) = 1})

``

Parr(R)

14

(1)

``

 

 But it takes long times when n>=64.

I want to request you, please edit your code until that the edited code compute the parameter xor_count.

Thanks for your favor. 

@Carl Love Perfect. It works without error. Thanks for everything.

@Carl Love Unfortunately because of some limitations I could not installed the new version of Maple and hence I should use Maple 15 again. When I run the new code retrofitted  in Maple 15, it made this error

Sorry due to my limitations and thanks for all your effort and codes.

 

 

 

@Carl Love First of all I want to appreciate you taking the time to write this procedure. I used Maple 15 and when I run the  procedure it made an error that I attached its maple file. Error.mw

Really thanks for your favor.

 

@Carl Love You right. I made a mistake. Thank you. 

@vv I appreciate you taking the time to respond to my comment. Your solution is nice and perfect and not only is useful for this question, but also can be used for other commands of generic package.

I would like to ask you to help me in the next question which is the my last question. I attached a new maple file. In the new Maple file, there is an 8x16 matrix over GF(2,4)  which is denoted with  H. I used the matrix H as a parity-check matrix of a code and observe that H produces the [16,8,7] code which means the minimum number of linearly dependent columns of H over G is 7. But when I test the matrix H with your given solution I got 8 for the rank of matrix. Where is my mistake. In other words, how to obtain the minimum number of linearly dependent columns of H with your given solution.

Excuse me that I ask too questions. I am a TA of coding and I would like to implement the concept of coding with Maple.

test.mw

@vv Thanks for your answer.I tested your suggestion, but the ReducedRowEchelon  command makes an error when the matrix is not a square matrix.I attached the Maple file to see the example. As you know, my question is equivalent to obtain the minimum distance of a code when the matrix H is used as a parity-check matrix in the code. Thanks again.Maple-Error-Generic.mw

@vv Yes the use of floats should be enough. A million thanks to you.

@vv First of all, I want to thank you because of two useful notes that you mentioned. I have two questions.


First: what did you mean by "provided that the entries of C are < 2^53". Do you mean C[i,j]<2^53 for all i and j? 


Second: Consider we defined the finite field G:=GF(2,n) for some n and we considered the matrix A over G by A:=G:-input~(A). Now the computation are done over  GF(2) and hence when by generic package we obtain C=A^k, then all even numbers in C are changed to zero and this is not acceptable. In fact we want to find the primitive order of matrix A over field of real numbers. 

Thanks in advance


 

@mmcdara Thanks  for your cooperation in the question. 

1 2 3 4 5 Page 3 of 5
´╗┐