A Primary Study And A Conjecture Of The Computation Theory In Two New Problems Of Magic Square

How to complete an unfinished magic square and how to separate the modulus sum of magic squares are new problems with cryptographical significance in magic square. Some practical applications of them can be widely found in the fields such as network identification, electronic tag, access control, key management and assignment, micro-payment, digital anti-fake technique and etc.. Researching on these new problems in theory will be an important assistant to the applications of them. Aimed at this need, we develop our work on the study of the two crucial problems of separating the modulus sum of magic squares and completing an unfinished magic square using methods of linear algebra in the finite field and computational complexity. The main contributions of this thesis are summarized as follows.(1) This paper focuses on some basic properties of the problem of how to separate the modulus sum of magic squares associated with n 2 +1 being a prime number. A proof is given that all matrices of the modulus sum of magic squares of order n make up of a linear space with ( n 2 ? 2n?1) dimensions if n =4,6,10,14,16,20. Then a pretty theory is proved to determine whether a matrix is a modulus sum of some magic squares of order n ( n =4,6,10,14,16,20), and a primary solution is proposed to separate the modulus sum of magic squares. On the basis of this, a conjecture is presented that the dimension of the linear space which is made of by all matrices of the modulus sum of magic squares of order n is ( n 2 ? 2n?1) if n 2 +1 is a prime number.(2) This paper researches on two algorithms to solve the unfinished magic square with low rank, and analyses the defects of them. A primary solution is given to prove the conjecture that completing an unfinished magic square is NP-complete.(3) To prove that completing an unfinished magic square is NP-complete, this paper defines perfect Latin square and discusses its properties. The relation between perfect Latin squares and magic squares, especially the mapping between perfect Latin squares of order 5 and perfect magic squares of order 5 which is proved in this paper may possibly provide a new method to study magic square.