Construction of Multi-sequences With High Nonlinear Complexity via Narrow Ray Class Fields

I. INTRODUCTION

• High nonlinear complexity matters for simulation and word-based ciphers because high linear complexity can coexist with low nonlinear complexity, while function-field constructions remain comparatively limited.The introduction frames a systematic construction method as both theoretically and practically important.Source: §I · pp. 1–2
• Narrow ray class field constructions yield multi-sequences with high dimensions and large linear and nonlinear complexity, and generalize constructions in,.The paper also outlines explicit constructions and asymptotic results via function field towers.Source: §I · p. 2
• The paper previews preliminaries, main results and techniques, narrow ray class field constructions, illustrative explicit examples, asymptotic results via function field towers, and concluding directions.The construction section reports favorable cryptographic properties for the resulting multi-sequences.Source: §I · p. 2

1) Definition of multi-sequences:

• A periodic multi-sequence is introduced in terms of its dimension and period, followed by two classical function-field constructions as examples.The examples are presented to illustrate the definition.Source: 1) Definition of multi-sequences · p. 3

2) Linear Complexity:

• Linear complexity is the smallest nonnegative recurrence length for which coefficients satisfy the recurrence across every component sequence and index.Source: 2) Linear Complexity · p. 3

3) Nonlinear Complexity:

• The mth nonlinear complexity is the least N permitting a multivariate recurrence polynomial of total degree at most m, and NLm(S) ≤ LC(S).Source: 3) Nonlinear Complexity · pp. 3–4

4) β−error Nonlinear Complexity

• β-error nonlinear complexity minimizes nonlinear complexity over multi-sequences within total Hamming distance β of the original sequence.Source: 4) β−error Nonlinear Complexity · p. 4

B. Extension Theory of Function Fields

• A place has degree [FP : Fq], degree-one places are rational, and their number N(F) satisfies the stated Serre bound.The bound is |N(F) − q − 1| ≤ gF · ⌊2√q⌋.Source: B. Extension Theory of Function Fields · p. 4
• For a nonnegative divisor G, the Riemann–Roch space L(G) has dimension deg(G) + 1 − gF when deg(G) ≥ 2gF − 1.Divisors are finite linear combinations of places.Source: B. Extension Theory of Function Fields · pp. 4–5
• In a finite extension, the different exponent is e(Q|P) − 1 exactly when gcd(e(Q|P), p) = 1; higher ramification groups also enter the different and Hurwitz genus formula.The extension-theory preliminaries define the different exponent, ramification index, and relative degree.Source: B. Extension Theory of Function Fields · p. 5

C. Drinfeld Modules of Rank 1 and Class Field Theory

• For a function field with a rational place ∞, the Hilbert class field of Aq is the maximal abelian extension unramified at finite places in which ∞ splits completely, and its degree is h(F).The setup assumes genus gF ≥ 1 and at least one rational place.Source: C. Drinfeld Modules of Rank 1 and… · pp. 5–6
• A rank-1 Drinfeld module is a homomorphism ψ: Aq → HAq{τ} with degτ(ψa) = −v∞(a), where τu = uqτ.Here τ is the Frobenius endomorphism of HAq.Source: C. Drinfeld Modules of Rank 1 and… · p. 6
• When gcd(M, charAq(ψ)) = 1, the M-torsion module is finite, and its associated field is called the M-division field of ψ.The passage associates the M-division field with HAq(Λψ(M)).Source: C. Drinfeld Modules of Rank 1 and… · p. 6
• For a prime modulus Q, finite places R not dividing Q are unramified, while Q is totally ramified with index Φ(Q).At infinity, the ramification index is q − 1, and the number of places above infinity is Φ(Q)/(q − 1) = (q^d − 1)/(q − 1).Source: C. Drinfeld Modules of Rank 1 and… · pp. 6–7
• For a prime modulus Q, a finite place R not dividing Q splits completely in the division field when its order modulo Q is 1.The decomposition proposition identifies that order as f, with complete splitting when f = 1.Source: C. Drinfeld Modules of Rank 1 and… · p. 6

D. Ihara’s Constant A(q)

• Ihara’s constant is defined using N_q(g), the maximum number of rational places of a genus-g function field over F_q; the Drinfeld–Vlăduț bound gives an upper bound, with equality when q is a square.The equality is stated to be proved via modular curves.Source: D. Ihara’s Constant A(q) · p. 7

E. Garcia-Stichtenoth Tower

• For square q, the Garcia–Stichtenoth tower starts with T1 = F_q(y1) and is built iteratively as Tm = Tm−1(ym) using a defining equation.The equation itself is not legible in the supplied passage.Source: E. Garcia-Stichtenoth Tower · p. 7
• In the Garcia–Stichtenoth tower, the unique pole of y1 is totally ramified in Tm/T1, and the unique place above it is common to y1, …, ym.These properties are stated in Proposition II.9, Section 7.4.Source: E. Garcia-Stichtenoth Tower · p. 7
• Each Qα, the zero of y1 − α, is totally ramified when α^(√q−1) = −1.This ramification property is stated in Proposition II.9, Section 7.4.Source: E. Garcia-Stichtenoth Tower · p. 7
• The tower’s genus is given by a formula whose stated cases depend on m’s parity.The supplied text includes a fragment for m ≡ 1 (mod 2), but not enough of the formula to report its value.Source: E. Garcia-Stichtenoth Tower · pp. 7–8

III. MAIN RESULTS AND COMPARISON

• Under Theorem III.1’s rational-place and divisor-range hypotheses, the construction gives dimension r+s_r, period μ_H, and a nonlinear-complexity lower bound beginning m+r+s_r.The stated setting has q=r^2, a function field of genus g_F with 1+r+s_r rational places, and a fixed odd-degree place Q.Source: §III · pp. 8–9
• Theorem III.2 gives a casewise β-error nonlinear-complexity bound, displaying r+s_r−α_0+m and μ_H(r+s_r)−ma+m−1.Here α_0=1+⌈(a+1)/μ_H⌉; the theorem’s divisor range extends to (r+s_r−1)μ_H+α_0−3.Source: §III · p. 9
• The comparison notes that prior constructions mostly rely on large automorphism groups, which are limited by the Hurwitz bound, while this construction yields new infinite families with large period and high dimension.For an irreducible curve X/F_q of genus g_X, the cited bound is |Aut(X/F_q)|≤16g_X^4.Source: §III · p. 9

IV. MULTI-SEQUENCES WITH HIGH NONLINEAR COMPLEXITY FROM NARROW RAY CLASS FIELDS

• Rank-1 Drinfeld modules and narrow ray class fields provide tools for generating new multi-sequences with significantly high nonlinear complexity.Source: §IV · p. 9

• For odd-degree Q with d ≥ 3, the cyclic descent field H/L from Lemma IV.1 splits every F_r-rational place and can ramify only at Q.Source: A. Construction of multi-sequences… · pp. 10–11
• The first descent Γ/L need not be cyclic, so its degree cannot generally define a cyclic automorphism or contribute its class-number factor to the period.Source: A. Construction of multi-sequences… · p. 11
• When F/F_r is rational, both class numbers equal 1, the two descents coincide, and H's genus attains equality in the genus estimate.Source: A. Construction of multi-sequences… · p. 11
• The ramification quantity Δ_Q satisfies d ≤ Δ_Q ≤ μ_H d, with Δ_Q = d in the totally ramified case.Source: A. Construction of multi-sequences… · p. 12
• Riemann–Roch ensures an evaluation function z in L(A + P0) \ L(A) when deg A ≥ 2g_H − 1 and P0 is outside Supp(A); z has a simple pole at P0.Its other poles lie in Supp(A), and A is σ-invariant with support disjoint from the rational orbits.Source: A. Construction of multi-sequences… · p. 12
• The construction yields a multi-sequence of dimension r + sr and period μ_H.Source: A. Construction of multi-sequences… · p. 12

B. High Linear Complexity

• Under the stated place-count, divisor-degree, and field-extension conditions, the construction gives dimension r + s_r, period μ_H, and linear complexity μ_H.The proof rules out linear complexity below μ_H; since the sequence has period μ_H, its linear complexity is μ_H.Source: B. High Linear Complexity · p. 13
• For a rational-function-field specialization, Corollary IV.5 constructs a √q-sequence multisequence and gives its linear complexity.The supplied passage cuts off the displayed linear-complexity formula.Source: B. High Linear Complexity · p. 14
• When d = 3, the fixed field H is Hermitian, and the modified multisequence has linear complexity q − √q + 1.The passage identifies the Hermitian-field case by reference to.Source: B. High Linear Complexity · p. 14
• Any α periodic sequences selected from the multisequence form a new multisequence with linear complexity μ_H.This property is stated after the Hermitian specialization.Source: B. High Linear Complexity · p. 14

C. High Nonlinear Complexity

• Theorem IV.7 constructs a multi-sequence of dimension r + s_r and period μ_H whose nonlinear complexity is at least ((r + s_r)μ_H − am − 1)/(m + r + s_r).The bound applies when 1 + r + s_r rational places satisfy |s_r| ≤ g_F⌊2√r⌋, Q has odd degree d ≥ 3, and 2g_H − 1 ≤ a ≤ (r + s_r − 1)μ_H − 1.Source: C. High Nonlinear Complexity · pp. 14–15
• Corollary IV.8 asserts a multi-sequence with dimension α, period μ_H, linear complexity μ_H, and a lower bound on nonlinear complexity.Its stated parameter range is 2g_H − 1 ≤ a ≤ (α − 1)μ_H − 1, under the same rational-place and place-degree conditions.Source: C. High Nonlinear Complexity · p. 15

D. High β−error Nonlinear Complexity

• Theorem IV.9 constructs multi-sequences of dimension r + s_r and period μ_H with β-error nonlinear-complexity lower bounds for β ≤ r + s_r − α_0 + 2.The construction assumes q = r^2, a function field F/ F_r, an odd-degree place Q of degree d ≥ 3, and the stated range for a.Source: D. High β−error Nonlinear Complexity · pp. 16, 18
• The cyclotomic function-field example gives a lower bound on the nonlinear complexity of S, with a = γd.It uses a Carlitz cyclotomic function field and its descent field H.Source: D. High β−error Nonlinear Complexity · p. 18
• The cited passages state lower bounds for NL_m(S) and NL_{m,β}(S); the first displayed bound involves q and m, while the second also involves μ_H, a, and α_0.Source: D. High β−error Nonlinear Complexity · p. 19
• For a maximal hyperelliptic function field with t dividing √q + 1, the construction gives lower bounds for NL_m(S) and NL_{m,β}(S).The genus is g_F = t − 1, and the displayed bounds depend on q, t, μ_H, a, m, and α_0.Source: D. High β−error Nonlinear Complexity · p. 19

V. ASYMPTOTIC FAMILIES VIA FUNCTION FIELD TOWERS

• For sufficiently large i, Theorem V.2 constructs a multisequence of dimension N_i−1 and linear complexity µ_i using a place Q_i of odd degree d_i=O(√g_i).For every fixed m≥1, its nonlinear complexity has a lower bound and is bounded away from zero whenever λ(F)>2m.Source: §V · pp. 20–21
• For a fourth-power q, a Garcia-Stichtenoth tower reaching the Drinfeld–Vladut bound has positive normalized nonlinear-complexity lower bound when 4√q−1>2m.For fixed m, the bound tends to 1 as q→∞ through fourth powers.Source: §V · p. 21

• The constructed multi-sequences arise from descent narrow ray class fields using rank-1 Drinfeld modules and have period µH = rd+1.Source: §VI · p. 22
• For dimension r + sr, the paper gives lower bounds for nonlinear complexities, including the stated expression m + r + sr.Source: §VI · p. 22
• The paper also divides β-error nonlinear-complexity results into cases, with expressions involving r + sr − α0 + m and µH(r + sr) − ma + m − 1.Source: §VI · p. 22