Additive index and Carlitz rank

Arne Winterhof; Pierre-Yves Bienvenu

arxiv: 2604.25414 · v1 · submitted 2026-04-28 · 🧮 math.NT · math.AC

Additive index and Carlitz rank

Pierre-Yves Bienvenu , Arne Winterhof This is my paper

Pith reviewed 2026-05-07 15:01 UTC · model grok-4.3

classification 🧮 math.NT math.AC

keywords finite fieldsCarlitz rankadditive indexcomplexity measurescryptographic functionsdiscrete logarithm

0 comments

The pith

Carlitz rank and additive index cannot both be small simultaneously except for trivial cases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that for self-mappings of finite fields, Carlitz rank and additive index cannot be small at the same time except for trivial exceptions. These two measures therefore identify different classes of functions that might have cryptographic weaknesses. The work also examines how additive index relates to the degree and weight of functions, extending earlier findings on Carlitz rank. Finally, it presents a function related to the discrete logarithm where all four measures—degree, weight, additive index, and Carlitz rank—are large.

Core claim

We show that Carlitz rank and additive index cannot be small simultaneously up to trivial exceptions. That is, these two measures detect cryptographic weaknesses of different classes of functions. We also study the relationship between additive index and degree or weight, respectively, complementing earlier results on the relationship between Carlitz rank and degree or weight, respectively. Finally, we show that a function closely related to the discrete logarithm provides an example in which all four complexity measures, degree, weight, additive index and Carlitz rank, are large.

What carries the argument

The demonstration that small Carlitz rank and small additive index are incompatible for self-mappings of finite fields except in trivial cases.

Load-bearing premise

The definitions of Carlitz rank and additive index are well-defined and capture distinct notions of complexity for all self-mappings of finite fields, with only trivial exceptions where both can be small.

What would settle it

Finding a non-trivial self-mapping of a finite field where both Carlitz rank and additive index are small would disprove the central claim.

read the original abstract

We compare several complexity measures for self-mappings of finite fields. In particular, we show that Carlitz rank and additive index cannot be small simultaneously up to trivial exceptions. That is, these two measures detect cryptographic weaknesses of different classes of functions. We also study the relationship between additive index and degree or weight, respectively, complementing earlier results of Aksoy et al. and G\'omez-P\'erez et al. on the relationship between Carlitz rank and degree or weight, respectively. Finally, we show that a function closely related to the discrete logarithm provides an example in which all four complexity measures, degree, weight, additive index and Carlitz rank, are large.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves Carlitz rank and additive index cannot both be small except for affine maps, with clean case analysis and a discrete-log example where all measures are large.

read the letter

The core result is that Carlitz rank and additive index are incompatible for small values on non-affine self-maps of finite fields. The authors define both measures for arbitrary functions F_q to F_q, then show by case analysis on the possible small values that only the affine functions satisfy both bounds at once. This mutual exclusion is the new piece; earlier work handled each measure separately against degree or weight, but not their joint behavior. They also fill in the additive-index relations to degree and weight, and give an explicit function tied to the discrete logarithm where degree, weight, additive index, and Carlitz rank are all large at the same time. That example is useful because it shows the measures can all flag the same function as complex without overlap in the small cases. The proof approach is direct: enumerate the low-rank and low-index possibilities and check the resulting polynomial forms. It avoids circularity and handles the field-size generality without extra restrictions. The only soft spot is that the case analysis grows with the bound size, but since the authors target small values the enumeration stays manageable and the exceptions are stated cleanly as the affine maps. No load-bearing gaps appear in the argument structure. This work is for researchers in algebraic cryptography and permutation polynomials who already track these complexity measures. A reader looking for concrete comparisons between existing notions will find it directly useful. It is worth sending to peer review; the claims are modest, the evidence is explicit, and the contribution is a precise clarification rather than a broad new theory.

Referee Report

0 major / 3 minor

Summary. The manuscript compares several complexity measures for self-mappings of finite fields F_q to itself. Its central claim is that Carlitz rank and additive index cannot both be small simultaneously, except for the trivial affine functions; these measures therefore detect cryptographic weaknesses of different classes. The authors also derive relations between additive index and the degree or weight of the polynomial representation (complementing earlier results on Carlitz rank), and exhibit a function related to the discrete logarithm for which degree, weight, additive index, and Carlitz rank are all large.

Significance. If the results hold, the work shows that Carlitz rank and additive index capture distinct notions of complexity, which is useful for assessing permutation polynomials in cryptography. Strengths include the explicit definitions that apply to arbitrary self-maps, the case-analysis proof of the main theorem (showing only affine functions satisfy both small bounds), the supporting degree/weight relations derived directly from polynomial representations, and the concrete discrete-logarithm example. These elements provide falsifiable, non-circular contributions that extend prior literature without unstated field-size restrictions.

minor comments (3)

[§2] §2: the definition of additive index is given explicitly, but a short numerical example for q=5 or q=7 would help readers verify the measure before the main theorem.
[Theorem 3.1] Theorem 3.1: the statement lists the affine exceptions, but it would be clearer to restate the precise bounds (e.g., rank ≤ 2 and index ≤ 1) inside the theorem rather than only in the surrounding text.
[§4] §4: the discrete-logarithm construction is derived from the same polynomial representation used earlier; adding a small table of computed values for a concrete prime power would make the claim that all four measures are large immediately checkable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. The referee summary correctly identifies the central result on the incompatibility of small Carlitz rank and small additive index (except for affine maps), the complementary relations to degree and weight, and the discrete-logarithm example where all four measures are large. No major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central result—that Carlitz rank and additive index cannot both be small except for affine functions—is established by explicit definitions of both measures for arbitrary self-maps of finite fields, followed by direct case analysis on the possible small values of each. Supporting relations to degree and weight are derived from the same polynomial representations used in the definitions, without fitting parameters or renaming. The discrete-logarithm example is constructed explicitly and shown to make all four measures large. Prior results cited (Aksoy et al., Gómez-Pérez et al.) are external and non-overlapping with the present authors; no self-citation is load-bearing for the main theorem. The derivation chain is therefore self-contained against the stated assumptions and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard algebraic definitions of finite fields and the four complexity measures; no free parameters or invented entities are visible from the abstract.

axioms (1)

standard math Finite fields exist and support polynomial representations of functions.
Background assumption for all self-mappings discussed.

pith-pipeline@v0.9.0 · 5400 in / 1170 out tokens · 62696 ms · 2026-05-07T15:01:52.490967+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

Aksoy, A

E. Aksoy, A. C ¸ e¸ smelio˘ glu, W. Meidl, A. Topuzo˘ glu, On the Carlitz rank of permutation polynomials. Finite Fields Appl. 15 (2009), no. 4, 428–440

work page 2009
[2]

Bienvenu, A

P.-Y. Bienvenu, A. Winterhof, On the additive index of the Diffie-Hellman mapping and the discrete logarithm.https://arxiv.org/abs/2601.13034

work page arXiv
[3]

Carlitz, Permutations in a finite field

L. Carlitz, Permutations in a finite field. Proc. Amer. Math. Soc. 4 (1953), 538

work page 1953
[4]

G´ omez-P´ erez, A

D. G´ omez-P´ erez, A. Ostafe, A. Topuzo˘ glu, On the Carlitz rank of permutations ofFq and pseudoran- dom sequences. J. Complexity 30 (2014), no. 3, 279–289

work page 2014
[5]

I¸ sık, A

L. I¸ sık, A. Winterhof, Carlitz rank and index of permutation polynomials. Finite Fields Appl. 49 (2018), 156–165

work page 2018
[6]

Niederreiter, A

H. Niederreiter, A. Winterhof, CyclotomicR-orthomorphisms of finite fields. Discrete Math. 295 (2005), 161–171

work page 2005
[7]

L. Reis, Q. Wang, The additive index of polynomials over finite fields. Finite Fields Appl. 79 (2022), Paper No. 102002, 16 pp

work page 2022
[8]

Shparlinski, Cryptographic applications of analytic number theory

I. Shparlinski, Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness. Progr. Comput. Sci. Appl. Logic, 22 Birkh¨ auser Verlag, Basel, 2003

work page 2003
[9]

Topuzo˘ glu, The Carlitz rank of permutations of finite fields: a survey

A. Topuzo˘ glu, The Carlitz rank of permutations of finite fields: a survey. J. Symbolic Comput. 64 (2014), 53–66

work page 2014
[10]

Wang, Cyclotomic mapping permutation polynomials over finite fields

Q. Wang, Cyclotomic mapping permutation polynomials over finite fields. Sequences, Subsequences, and Consequences (International Workshop, SSC 2007, Los Angeles, CA, USA, May 31 - June 2, 2007), Lecture Notes in Comput. Sci. 4893, 119–128, Springer, Berlin, 2007

work page 2007
[11]

Winterhof, Polynomial interpolation of the discrete logarithm

A. Winterhof, Polynomial interpolation of the discrete logarithm. Des. Codes Cryptogr. 25 (2002), no. 1, 63–72. ADDITIVE INDEX AND CARLITZ RANK 17 Email address:{pierre.bienvenu,arne.winterhof}@oeaw.ac.at Johann Radon Institute for Computational and Applied Mathematics, Austrian Acad- emy of Sciences, Linz, Austria

work page 2002

[1] [1]

Aksoy, A

E. Aksoy, A. C ¸ e¸ smelio˘ glu, W. Meidl, A. Topuzo˘ glu, On the Carlitz rank of permutation polynomials. Finite Fields Appl. 15 (2009), no. 4, 428–440

work page 2009

[2] [2]

Bienvenu, A

P.-Y. Bienvenu, A. Winterhof, On the additive index of the Diffie-Hellman mapping and the discrete logarithm.https://arxiv.org/abs/2601.13034

work page arXiv

[3] [3]

Carlitz, Permutations in a finite field

L. Carlitz, Permutations in a finite field. Proc. Amer. Math. Soc. 4 (1953), 538

work page 1953

[4] [4]

G´ omez-P´ erez, A

D. G´ omez-P´ erez, A. Ostafe, A. Topuzo˘ glu, On the Carlitz rank of permutations ofFq and pseudoran- dom sequences. J. Complexity 30 (2014), no. 3, 279–289

work page 2014

[5] [5]

I¸ sık, A

L. I¸ sık, A. Winterhof, Carlitz rank and index of permutation polynomials. Finite Fields Appl. 49 (2018), 156–165

work page 2018

[6] [6]

Niederreiter, A

H. Niederreiter, A. Winterhof, CyclotomicR-orthomorphisms of finite fields. Discrete Math. 295 (2005), 161–171

work page 2005

[7] [7]

L. Reis, Q. Wang, The additive index of polynomials over finite fields. Finite Fields Appl. 79 (2022), Paper No. 102002, 16 pp

work page 2022

[8] [8]

Shparlinski, Cryptographic applications of analytic number theory

I. Shparlinski, Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness. Progr. Comput. Sci. Appl. Logic, 22 Birkh¨ auser Verlag, Basel, 2003

work page 2003

[9] [9]

Topuzo˘ glu, The Carlitz rank of permutations of finite fields: a survey

A. Topuzo˘ glu, The Carlitz rank of permutations of finite fields: a survey. J. Symbolic Comput. 64 (2014), 53–66

work page 2014

[10] [10]

Wang, Cyclotomic mapping permutation polynomials over finite fields

Q. Wang, Cyclotomic mapping permutation polynomials over finite fields. Sequences, Subsequences, and Consequences (International Workshop, SSC 2007, Los Angeles, CA, USA, May 31 - June 2, 2007), Lecture Notes in Comput. Sci. 4893, 119–128, Springer, Berlin, 2007

work page 2007

[11] [11]

Winterhof, Polynomial interpolation of the discrete logarithm

A. Winterhof, Polynomial interpolation of the discrete logarithm. Des. Codes Cryptogr. 25 (2002), no. 1, 63–72. ADDITIVE INDEX AND CARLITZ RANK 17 Email address:{pierre.bienvenu,arne.winterhof}@oeaw.ac.at Johann Radon Institute for Computational and Applied Mathematics, Austrian Acad- emy of Sciences, Linz, Austria

work page 2002