幾類基于0-線性轉(zhuǎn)換的置換多項式*

謝 茜, 王麗莎, 李 念

湖北大學 數(shù)學與統(tǒng)計學學院 應用數(shù)學湖北省重點實驗室, 武漢430062

1 引言

設(shè)p 是素數(shù), n 為正整數(shù), Fpn 表示含有pn個元素的有限域. 若有限域Fpn 上的多項式F(x) 是從Fpn 到自身的一個一一映射, 則稱F(x) 是Fpn 上的置換多項式. 平衡性是密碼函數(shù)一項重要的安全性指標, 而有限域上的置換多項式能夠有效地保證平衡性. 在密碼算法設(shè)計中, 密碼函數(shù)常由有限域上具有優(yōu)良密碼性質(zhì)(如低差分均勻度、高非線性度、高代數(shù)次數(shù)等) 的置換構(gòu)成. 基于置換多項式在密碼學、編碼理論和序列設(shè)計等領(lǐng)域的廣泛應用, 構(gòu)造新的置換多項式是一個值得深入研究的問題.

人們對置換多項式的研究已有150 多年的歷史. 1863 年, Hermite[1]首先開創(chuàng)了對模素數(shù)p 的置換多項式的研究, 并提出了有限域Fp上置換多項式的一經(jīng)典判別方法: Hermite 準則. 之后, Dickson[2]于1896–1897 年將置換多項式的概念推廣到任意有限域Fpn上, 并對置換多項式作了深入探討. 隨后,越來越多的學者對置換多項式進行了研究. 目前, 已有利用跡函數(shù)和線性化多項式[3]、分段函數(shù)[4,5]、AGW 準則[6]等多種不同方法構(gòu)造置換多項式. 2009 年, Coulter, Henderson 和Matthews[3]利用跡函數(shù)和線性化多項式構(gòu)造有限域Fpn上的置換多項式. 同年, Charpin 和Kyureghyan[7]構(gòu)造有限域Fpn上形式為G(x)+γ Tr(H(x)) 的置換多項式, 其中G(x) ∈Fpn[x], H(x) ∈Fpn[x], γ ∈Fpn, Tr(·) 表示Fpn上的絕對跡函數(shù). 隨后, Marcos 在文獻[8] 中討論形式為L(x)+γh(Tr(x)) 的置換多項式, L 為定義在Fpn上的Fp-線性置換, h(x) ∈Fp[x], γ ∈Fpn. 基于對以上形如G(x)+γh(f(x)) 的置換多項式的研究, Kyureghyan[9]提出由線性轉(zhuǎn)換構(gòu)造形式為L(x)+L(γ)h(f(x)) 的置換多項式F(x), 其中L 為定義在Fpn上的Fpm-線性置換, f(x) 為定義在Fpn到Fpm的函數(shù), h(x) 為定義在Fpm到Fpm的函數(shù), γ ∈F?pn為f 的一個b-線性轉(zhuǎn)換, m, n 為正整數(shù), 且m|n. 同時, Kyureghyan 在文獻[9] 中給出函數(shù)F(x) 為Fpn上置換的充要條件, 即對于某些適當?shù)腷 ∈Fpm, x+bh(x) 為Fpm上的置換. 繼而, Akbary,Ghioca 和Wang[6]將Kyureghyan 的構(gòu)造推廣到Fpn的任意子集上, 而不僅限于其子域上.

通過選擇適當?shù)暮瘮?shù)f(x) 使F(x) 為Fpn 上的置換. 根據(jù)Kyureghyan[9]給出的結(jié)論, F(x) 在Fpn 上與g :u →u+bh(u) 在Fpm 上有相同的置換性質(zhì), 當b=0 時, g :u →u 為Fpm 上的置換, 此時F(x)為Fpn 上的置換. 因此, 通過找到存在0-線性轉(zhuǎn)換的f 即可得到置換多項式F. 定義在Fpn 到其子域Fpm 上的函數(shù)能表示成如下跡函數(shù)的形式

其中P(x) ∈Fpn[x] 且其不唯一[11]. 2017 年, Cepak, Charpin 及Pasalic[11]討論了f(x) 為某些特殊稀疏多項式的情形及其存在線性轉(zhuǎn)換所需條件. 本文主要考慮一類線性化多項式和一類二次齊次多項式f(x), 給出其存在線性轉(zhuǎn)換所需滿足的條件, 并進一步探討其0-線性轉(zhuǎn)換的存在性, 進而利用f 得到形式為(1)的置換多項式.

本文的結(jié)構(gòu)如下: 第2 節(jié)給出一些預備知識; 第3 節(jié)主要討論兩類函數(shù)線性轉(zhuǎn)換的存在性; 第4 節(jié)則討論第3 節(jié)中兩類函數(shù)存在0-線性轉(zhuǎn)換的情況, 并構(gòu)造兩類形式為(1)的置換多項式; 第5 節(jié)總結(jié)全文.

2 預備知識

本節(jié)我們首先給出一些基本概念和相關(guān)已知結(jié)論.

定義1 設(shè)k, m, n 為正整數(shù)且滿足n=km, f 為定義在Fpn到Fpm的函數(shù). 令γ ∈F?pn, 對于給定的b ∈Fpm, 若對任意的x ∈Fpn, u ∈Fpm均滿足

則稱γ 為f 的一個b-線性轉(zhuǎn)換. 特別地,當m=1 時,若對于任意的x ∈Fpn均滿足f(x+γ)?f(x)=b,則稱γ 為f 的一個b-線性結(jié)構(gòu).

定義2 設(shè)m, n 為正整數(shù), m|n, 從有限域Fpn到Fpm的跡函數(shù)定義如下:

當m=1 時, 稱其為Fpn 上的絕對跡函數(shù).

定義3 設(shè)k, m, n 為正整數(shù)且滿足n=km, 定義Fpn 上的Fpm-線性函數(shù)為

當L(x) 為Fpn 上的置換時, 則稱其為Fpn 上的Fpm-線性置換.

關(guān)于形式如式(1)的多項式的置換性, 已有如下結(jié)論.

又因f(x)∈Fp, 則f(γ) 為Fp上的一個固定元, 故而, γ 為f(x) 的f(γ)-線性結(jié)構(gòu).

3 兩類函數(shù)線性轉(zhuǎn)換的存在性

4 置換多項式的構(gòu)造

在第3 節(jié)的討論中, 我們給出了一類線性化多項式和一類二次齊次多項式f(x) 存在線性轉(zhuǎn)換的必要條件. 在本節(jié)中, 我們分別對下面線性多項式和二次齊次多項式f(x) 進行討論:

我們考慮f(x) 存在0-線性轉(zhuǎn)換這一特殊情形, 此時g :u →u 為Fpm上的置換, 利用定理1, 我們可以得到形式為(1)的F(x) 為Fpn上的置換多項式.

首先, 我們討論f(x) 是線性化多項式的情形.

且對任意的u ∈Fpm 有

從而由題設(shè)條件可知, 滿足條件的γ 為函數(shù)f(x) 的0-線性轉(zhuǎn)換.

將等式兩邊分別同時pmlt?it次冪, 即可得γp2mlt?1=?1. 另一方面, 我們有

其中b1=a1+ml2, b2=a2+ml1, ?k

證明: 由引理2 可知, f(x+uγ)?f(x) 與x 無關(guān)當且僅當

與x 無關(guān). 由于pi1+pj1和pi2+pj2不屬于關(guān)于pm模pn?1 的同一分圓陪集,即不存在整數(shù)?k

我們分以下三種情況討論:

(i) 若pi1, pj1屬于同一分圓陪集且pi2, pj2屬于同一分圓陪集, 則

由引理2 即可得證.

(ii) 若pi1, pi2屬于同一分圓陪集且pj1, pj2屬于同一分圓陪集, 則存在整數(shù)?k

由等式(5)可得l1=l2. 此時, 上式(4)可化為

進而由引理3 和定理1 可推導出如下結(jié)論.

定理7 設(shè)k, m, n 為正整數(shù)滿足n=km, L 為Fpn 上的Fpm-線性置換, h:Fpm →Fpm, 函數(shù)

且it, jt滿足jt=it+mlt, ?k

并且

5 結(jié)論

本文討論了從有限域Fpn到Fpm上的兩類多項式(即線性化多項式和二次齊次多項式) 線性轉(zhuǎn)換的存在性, 并通過深入研究其0-線性轉(zhuǎn)換構(gòu)造出了兩類形式為式(1)的無限類置換多項式. 本文推廣了Cepak 等人[11]的部分結(jié)論. 在本文的討論中, 設(shè)計出形式為式(1)的置換多項式的關(guān)鍵在于確定存在線性轉(zhuǎn)換的多項式f(x). 對于多項式f(x) 代數(shù)次數(shù)大于2 的情形, 討論其線性轉(zhuǎn)換的存在性可留做一個有趣的研究課題, 供讀者思考.