Estamos realizando la búsqueda. Por favor, espere...
1579
37
170
28929
4401
2598
347
381
Abstract: L. Carlitz proved that any permutation polynomial f over a finite field Fq is a composition of linear polynomials and inversions. Accordingly, the minimum number of inversions needed to obtain f is defined to be the Carlitz rank of f by Aksoy et al. The relation of the Carlitz rank of f to other invariants of the polynomial is of interest. Here we give a new lower bound for the Carlitz rank of f in terms of the number of nonzero coefficients of f which holds over any finite field. We also show that this complexity measure can be used to study classes of permutations with uniformly distributed orbits, which, for simplicity, we consider only over prime fields. This new approach enables us to analyze the properties of sequences generated by a large class of permutations of Fp, with the advantage that our bounds for the discrepancy and linear complexity depend on the Carlitz rank, not on the degree. Hence, the problem of the degree growth under iterations, which is the main drawback in all previous approaches, can be avoided.
Fuente: Journal of Complexity, Volume 30, Issue 3, Pages 279–289
Fecha de publicación: 01/06/2014
Nº de páginas: 11
Tipo de publicación: Artículo de Revista
DOI: 10.1016/j.jco.2013.11.001
ISSN: 0885-064X,1090-2708
Proyecto español: MTM2011-24678 ; TIN2011-27479-C04-04
Url de la publicación: http://dx.doi.org/10.1016/j.jco.2013.11.001
Consultar en UCrea Leer publicación
DOMINGO GOMEZ PEREZ
OSTAFE, ALINA
TOPUZOGLU, ALEV
Volver