\(p(x)\)-circulants over finite fields and probability methods of their construction. (English. Russian original) Zbl 1321.15050

Gritsenko, V. V.; Maevskiy, A. É.

Math. Notes 96, No. 5, 928-942 (2014); translation from Mat. Zametki 96, No. 6, 864-879 (2014).

Let \(\mathbb F\) be a finite field of characteristic \(p\), with \(p^s\) elements, and let \(p(x)=x^n-p_{n-1}x^{n-1}-\dots-p_1x-p_0\), with \(n\) an integer \(>1\) and coefficients \(p_i\) in \(\mathbb F\). The authors define the \(p(x)\)-circulant of a vector \(c=(c_0,\dots,c_{n-1})\) in \(\mathbb F^n\) to be the \(n\times n\) matrix whose elements \(c_{i,j}\) are defined as follows for \(1 < i , j < n\): \[ \begin{aligned} c_{i,1}&=c_{i-1},\\ c_{i,2}&=c_{n,1}p_{i-1}+c_{i-1,1},\\ &\dots,\\ c_{i,n}&=c_{n,n-1}p_{i-1}+c_{i-1,n-1},\end{aligned} \] with \(c_{0,j}=0\) for \(j = 1, 2, \dots, n-1\).
In this paper, the algebraic structure of the set of all \(p(x)\)-circulants over \(\mathbb F\) is studied, a computationally effective criterion for the invertibility of its elements is established, together with a method for constructing inverse elements, and a formula for evaluating the determinant of a \(p(x)\)-circulant is presented. The authors also solve the converse problem of constructing computationally effective algorithms of random equiprobable choice in the set of invertible \(p(x)\)-circulants or in the set of all \(p(x)\)-circulants with a given determinant. Here, computational effectiveness means minimization of computational complexity and of the number of random elements used.

Reviewer: Rabe von Randow (Bonn)

MSC:

15B33	Matrices over special rings (quaternions, finite fields, etc.)
65F30	Other matrix algorithms (MSC2010)
65Y20	Complexity and performance of numerical algorithms
15A15	Determinants, permanents, traces, other special matrix functions
15A09	Theory of matrix inversion and generalized inverses

Keywords:

\(p(x)\)-circulant; finite field; algorithm of random choice; random equiprobable choice; time complexity; algebra of \(p(x)\)-circulants; invertibility; determinant; computational complexity

Software:

McEliece

References:

[1]	V. V. Voevodin and E. E. Tyrtyshnikov, Numerical Processes with Toeplitz Matrices (Nauka, Moscow, 1987) [in Russian]. · Zbl 0636.65018
[2]	Zhao-Lin Jiang and Zong-Ben Xu, “Efficient algorithm for finding the inverse and the group inverse of FLS <Emphasis Type=”Italic“>r-circulant matrix,” J. Appl. Math. Comput. 18(1-2), 45-57 (2005). · Zbl 1087.65024 · doi:10.1007/BF02936555
[3]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977; Svyaz’, Moscow, 1979). · Zbl 0369.94008
[4]	D. Chillag, “Regular representations of semisimple algebras, separable field extensions, group characters, generalized circulants, and generalized cyclic codes,” Linear Algebra Appl. 218, 147-183 (1995). · Zbl 0839.20015 · doi:10.1016/0024-3795(93)00167-X
[5]	A. Mahalanobis, “The discrete logarithm problem in the group of non-singular circulant matrices,” Groups Complex. Cryptol. 2(1), 83-89 (2010). · Zbl 1193.94059 · doi:10.1515/gcc.2010.006
[6]	R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, Deep Space Network Progress Report, DSN PR 42-44 (1978), 114-116.
[7]	A. D. Wyner, “The Wire-Tap Channel,” Bell System Tech. J. 54(8), 1355-1387 (1975). · Zbl 0316.94017 · doi:10.1002/j.1538-7305.1975.tb02040.x
[8]	Ozarow, L. H.; Wyner, A. D., Wire-tap channel. II, 33-50 (1985), Berlin · Zbl 0596.94007
[9]	R. Lidl and G. Niederreiter, Finite Fields (Addison-Wesley Publishing Co., Reading, Mass., 1983; Mir, Moscow, 1988). · Zbl 0554.12010
[10]	F. R. Gantmakher, The Theory of Matrices (Nauka, Moscow, 1988; [Gantmacher] AMS Chelsea Publishing, Providence, RI, 1998). · Zbl 0666.15002
[11]	V. Shoup, A Computational Introduction to Number Theory and Algebra (Cambridge Univ. Press, Cambridge, 2009). · Zbl 1196.11002
[12]	D. E. Knuth, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms (Addison-Wesley Publishing Co., Reading, Mass.-London-DonMills, Ont, 1969; Mir, Moscow, 2000). · Zbl 0191.18001
[13]	V. V. Gritsenko and Yu. V. Kosolapov, “Algorithm for constructing of all invertible circulants over Galois fields,” Izv. Vuzov. Sev.-Kavkazsk. Region. Ser. Estestv. Nauki 2, 8-12 (2012) [in Russian].