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

謝 茜, 王麗莎, 李 念

湖北大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室, 武漢430062

1 引言

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

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

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

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

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

2 預(yù)備知識(shí)

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

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

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

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

當(dāng)m=1 時(shí), 稱其為Fpn 上的絕對(duì)跡函數(shù).

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

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

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

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

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

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

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

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

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

且對(duì)任意的u ∈Fpm 有

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

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

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

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

與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. 此時(shí), 上式(4)可化為

進(jìn)而由引理3 和定理1 可推導(dǎo)出如下結(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上的兩類多項(xiàng)式(即線性化多項(xiàng)式和二次齊次多項(xiàng)式) 線性轉(zhuǎn)換的存在性, 并通過深入研究其0-線性轉(zhuǎn)換構(gòu)造出了兩類形式為式(1)的無限類置換多項(xiàng)式. 本文推廣了Cepak 等人[11]的部分結(jié)論. 在本文的討論中, 設(shè)計(jì)出形式為式(1)的置換多項(xiàng)式的關(guān)鍵在于確定存在線性轉(zhuǎn)換的多項(xiàng)式f(x). 對(duì)于多項(xiàng)式f(x) 代數(shù)次數(shù)大于2 的情形, 討論其線性轉(zhuǎn)換的存在性可留做一個(gè)有趣的研究課題, 供讀者思考.