Representing the inverse map as a composition of quadratics in a finite field of characteristic 2
Tóm tắt
In 1953, Carlitz showed that all permutation polynomials over
$${\mathbb F}_q$$
, where
$$q>2$$
is a power of a prime, are generated by the special permutation polynomials
$$x^{q-2}$$
(the inversion) and
$$ ax+b$$
(affine functions, where
$$0\ne a, b\in {\mathbb F}_q$$
). Recently, Nikova, Nikov and Rijmen (2019) proposed an algorithm (NNR) to find a decomposition of the inverse function in quadratics, and computationally covered all dimensions
$$n\le 16$$
. Petrides (2023) theoretically found a class of integers for which it is easy to decompose the inverse into quadratics, and improved the NNR algorithm, thereby extending the computation up to
$$n\le 32$$
. In this paper, we extend Petrides’ result, as well as we propose a new number theoretical approach, which allows us to easily cover all (surely, odd) exponents up to 250, at least.
Từ khóa
Tài liệu tham khảo
Bilgin, B., Nikova, S., Nikov, V., Rijmen, V., Stütz, G.: Threshold Implementations of All \(3 \times 3\) and \(4\times 4\) S-Boxes. In: Prouff, E., Schaumont, P. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2012, LNCS 7428. Springer, Berlin, Heidelberg (2012)
Carlitz, L.: Permutations in a finite field’. Proc. Amer. Math. Soc. 4, 538 (1953)
Hall, R.T., Tenenbaum, G.: Divisors, Cambridge Tracts in Mathematics, 90. Cambridge University Press, Cambridge (1988)
Kontorovich, A., Lagarias, J.: On toric orbits in the affine sieve. Exp. Math. 30, 575–587 (2021)
Luca, F., Stănică, P.: Asymptotics on a class of \(\cal S\it \)-unit integers. Periodica Math. Hungarica, https://doi.org/10.1007/s10998-023-00551-4
Luca, F.: Stănică, P.: Prime divisors of Lucas sequences and a conjecture of Skałba. Int. J. Number Theory 1(4), 583–591 (2005)
Moree, P.: On the divisors of \(a^k+b^k\). Acta Arith. LXXX.3, 197–212 (1997)
Murata, L., Pomerance, C.: On the largest prime factor of a Mersenne number. In: Number Theory, 209–218, CRM Proc. Lecture Notes 36, Amer. Math. Soc., Providence, RI, (2004)
Nikova, S., Nikov, V., Rijmen, V.: Decomposition of permutations in a finite field. Cryptogr. Commun. 11, 379–384 (2019)
Nikova, S., Rechberger, C., Rijmen, V.: Threshold Implementations Against Side-Channel Attacks and Glitches. In: Ning, P., Qing, S., Li, N. (eds.) Information and Communications Security - ICICS, LNCS 4307. Springer, Berlin, Heidelberg (2006)
Petrides, G.: On decompositions of permutation polynomials into quadratic and cubic power permutations. Cryptogr. Commun. 15, 199–207 (2023)
Rotkiewicz, A.: Applications of Jacobi’s symbol to Lehmer’s numbers. Acta Arith. 42, 163–187 (1983)