国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

關(guān)于任意零元阿貝爾有限??杉訄D群及其在信息安全中的應用

2022-04-22 07:47趙梅梅
關(guān)鍵詞:標號頂點加密

趙梅梅, 姚 兵

(1. 甘肅農(nóng)業(yè)大學 理學院, 甘肅 蘭州 730070; 2. 西北師范大學 數(shù)學與統(tǒng)計學院, 甘肅 蘭州 730070)

1 研究簡介

眾所周知,密碼保護系統(tǒng)的安全性取決于多個因素,公鑰和私鑰在密碼學中發(fā)揮著重要作用。密碼問題的經(jīng)典研究可以追溯到40多年前,一些學者對現(xiàn)有的圖形密碼做了深入的研究[1-3]。圖形密碼是不同于文本密碼的一種新型密碼,圖形密碼易于用戶記憶,而且很難被攻擊者破解?,F(xiàn)有的圖形密碼缺點是圖片頻繁更改會占用計算機龐大的空間,用戶需要學習更多的相關(guān)知識并具有良好的記憶,不支持更多的個性化創(chuàng)意和個性化的圖形密碼。為了解決圖形密碼的缺點,王宏宇等[4-6]提出了拓撲圖形密碼, 其思想是“拓撲結(jié)構(gòu)+數(shù)論”。 拓撲圖形密碼是由圖論中的拓撲結(jié)構(gòu)和著色(標號)組成的。由于拓撲圖形密碼通過代數(shù)矩陣保存在計算機中[7],這就使得拓撲圖形密碼比現(xiàn)有的圖形密碼占用計算機的空間小,關(guān)于數(shù)矩陣的算法是多形式的,因此,可以快速實現(xiàn)拓撲圖形密碼。更為重要的是,拓撲圖形密碼可以用來對網(wǎng)絡(luò)進行整體加密,加之大量的NP-問題和猜想存在于拓撲圖形密碼中,使得拓撲圖形密碼具有抗量子計算的能力[8]。

云計算引入“同態(tài)加密”技術(shù)提供了一種對加密數(shù)據(jù)進行處理的功能[9],提高了數(shù)據(jù)的安全隱私保護,實現(xiàn)“數(shù)據(jù)不可見”性。同態(tài)加密技術(shù)可以應用在很多領(lǐng)域,例如,在案件調(diào)查過程中,警察可以搜索嫌犯的行程、財務記錄,以及調(diào)查通訊和郵件記錄,且不會暴露嫌犯的數(shù)據(jù)。醫(yī)學研究人員可以根據(jù)數(shù)百萬患者的記錄,來識別基于人口結(jié)構(gòu)和地理位置的疾病趨勢。政府和商業(yè)機構(gòu)能夠很好地對財務數(shù)據(jù)進行分析和處理。值得注意的是,同態(tài)加密技術(shù)也可以在原有基礎(chǔ)上使用區(qū)塊鏈技術(shù),且不會對區(qū)塊鏈屬性造成任何重大的改變。圖群整體加密技術(shù)在公有區(qū)塊鏈上進行加密,隨時加密公用區(qū)塊鏈上的數(shù)據(jù)。

本文介紹的任意零元阿貝爾有限??杉訄D群可以應用于“同態(tài)圖群”,這將產(chǎn)生“同態(tài)圖群加密”技術(shù),在云計算、抗量子計算中具有可應用性。下面給出一個網(wǎng)絡(luò)整體加密的例子, 采用了圖1中的任意零元(7)-模混合優(yōu)美圖群,它是一個任意零元阿貝爾有限??杉訄D群。圖2為給網(wǎng)絡(luò)T進行整體加密。

圖1 一個(7)-模混合優(yōu)美圖G能生成19個(7)-模圖

圖2 給網(wǎng)絡(luò)T進行整體加密Fig.2 Encrypting integrally a network T

圖2給出網(wǎng)絡(luò)T的4個整體加密, 其中,T1和T2的節(jié)點著色相同,但是邊著色不同,這是用于網(wǎng)絡(luò)整體加密的零元不同,T1的零元是(7)-模混合優(yōu)美圖群中的G6,T2的零元是(7)-?;旌蟽?yōu)美圖群中的G10。T3和T4的邊著色有著規(guī)律,T3的邊著色為G1,G2,G3,G4,G5, 不難看到,T4的邊著色為G1,G3,G5,G7,G9。 每個Gk(k∈[1,19])可以產(chǎn)生數(shù)字串, 例如,G1導出數(shù)字串

S1,i=314 123 134 145 055 566

(1)

它由18個數(shù)字組成。圖2中的T1的節(jié)點G1和節(jié)點G7被標有G2的邊連接在一起, 節(jié)點G1導出的數(shù)字串S1,i與節(jié)點G7導出的數(shù)字串S7,i通過標有G2的邊導出的數(shù)字串S2,i進行連接認證, 使得節(jié)點G1和節(jié)點G7之間有通訊聯(lián)通,認證是由54個數(shù)字組成。當網(wǎng)絡(luò)整體的零元發(fā)生變化后,連接2個節(jié)點邊著色也發(fā)生變化,邊著色導出的數(shù)字串也發(fā)生變化,使得2個節(jié)點的通訊認證必須采用新的數(shù)字認證。

一般情形下,一個任意零元阿貝爾有限??杉訄D群中的圖Gk導出mk個數(shù)字構(gòu)成的數(shù)字串,k為整數(shù)。任意2個節(jié)點Gi,Gj,通過Gk通訊認證需由mi+mj+mk個數(shù)字構(gòu)成。 因為涉及到圖的同構(gòu),加之已經(jīng)有數(shù)百種著色運用于實際[10,11], 所以由式(1)中的數(shù)字串S1,i找到圖1中的著色圖G1是及其困難的。這說明用任意零元阿貝爾有限??杉訄D群進行網(wǎng)絡(luò)整體加密的優(yōu)勢。

2 基本術(shù)語、定義

文中所考慮的圖均為有限、無向、簡單圖。文中沒有定義的術(shù)語和符號參考文獻[12]。為敘述簡便起見, 用記號[m,n]表示集合{m,m+1,m+2,…,n}, 其中,m和n均為整數(shù), 且滿足m

對于(q+1)-模混合優(yōu)美圖, 其最小的頂點標號是負數(shù), 最大的頂點標號是正數(shù)。設(shè)圖G有(q+1)-?;旌蟽?yōu)美標號f:V(G)→[-q,q], 使得

f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)}

({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q]。

如果G中最小的頂點標號為s, 最大的頂點標號為t, 記G的標號f=fm, 其中,m=t+q+1,G=Gm, 那么對于G的每個拷貝Gk, 定義其(q+1)-?;旌蟽?yōu)美標號為:fk(x)=fm(x)-(m-k)(modq+1), 其中x∈V(G),k∈[1,3q+1]。

定義1[10,12]對于給定的 (p,q)-圖G, 如果存在一個單射f:V(G)→[0,q], 使得邊標號集合f(E(G))={f(uv)=|f(u)-f(v)|:uv∈E(G)}=[1,q], 則稱f是G的一個優(yōu)美標號(graceful labelling), 也稱G為優(yōu)美圖 (graceful graph)。此外, 若圖G是具有頂點二部劃分(X,Y)的二部圖, 且f滿足max{f(x)|x∈X}

定義2 對于給定的 (p,q)-圖G, 如果存在一個單射f:V(G)→[-q,q], 使得G的任何不同的2個頂點u,v滿足f(u)≠f(v), 且邊標號集合

f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)}

({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q],

則稱f是圖G的一個(q+1)-?;旌蟽?yōu)美標號((q+1)-modular mixed graceful labelling), 也稱G為(q+1)-模混合優(yōu)美圖((q+1)-modular mixed graceful graph)。特別地, 若f:V(G)→[0,q], 則稱f是圖G的一個(q+1)-模優(yōu)美標號((q+1)-modular graceful labelling);若f:V(G)→[-q,0], 則稱f是圖G的一個(q+1)-模負優(yōu)美標號((q+1)-modular negative graceful labelling)。

3 主要結(jié)果及證明

假設(shè)F是群,F′是它的非空子集且對于F中的加法運算封閉, 如果F′本身對于F中這個加法運算是群, 則稱F′是F的子群, 并且表示成F′

已知, 一個 (q+1)-模混合優(yōu)美圖G拷貝可以得到3q+1個圖。 事實上, (q+1)-?;旌蟽?yōu)美圖的頂點標號是在[-q,q]中取得, (q+1)-模優(yōu)美圖的頂點標號是在[0,q]中取得, (q+1)-模負優(yōu)美圖的頂點標號在[-q, 0]中的取得。 這些圖做成一個集合, 稱此集合是由(q+1)-?;旌蟽?yōu)美圖G生成的, 記作Mixg(G)。

任取一個固定的元Gk∈Mixg(G), 對任意的2個元Gi,Gj∈Mixg(G)={Gk:k∈[1,3q+1]}, 定義加法運算“Gi⊕kGj”如下:

[fi(x)+fj(x)-fk(x)](modq+1)=fλ(x)

(2)

其中,λ=i+j-k(modq+1),x∈V(G)=V(Gi)=V(Gj)=V(Gk)。

(1)若[fi(x)+fj(x)-fk(x)]<-q, 則

[fi(x)+fj(x)-fk(x)](modq+1)=q+1+fi(x)+

fj(x)-fk(x);

(2)若[fi(x)+fj(x)-fk(x)]>q, 則

[fi(x)+fj(x)-fk(x)](modq+1)=fi(x)+fj(x)-

fk(x)-(q+1);

(3)若不是上面(1)和(2)的情形,[fi(x)+fj(x)-fk(x)](modq+1)=fi(x)+fj(x)-fk(x)。

集合Mixg(G)和加法運算構(gòu)成一個任意零元阿貝爾有限??杉訄D群(見定理1的證明), 特記作{Mixg(G),f;⊕}。

定理1 設(shè) (p,q)-圖G有 (q+1)-模混合優(yōu)美標號f。 以下結(jié)論成立:

(1)G生成了3q+1個圖, 構(gòu)成一個任意零元阿貝爾有限??杉訄D群{Mixg(G),f;⊕}。

(2)任意連續(xù)的q+1+i個圖構(gòu)成一個任意零元阿貝爾有限??杉訄D子群, 且階為3q+1-i的子群有i+1 個, 其中,i∈[0,2q]。

(3)G可以生成2個特殊的任意零元阿貝爾有限??杉訄D子群, 其中,一個子群中的圖都是(q+1)-模優(yōu)美的, 另一個子群中的圖都是(q+1)-模負優(yōu)美的。

證明任取一個圖Gk0∈Mixg(G)作為零元, 對任意2個元Gi,Gj∈Mixg(G), 定義加法運算Gi⊕k0Gj=Gλ(λ=i+j-k0(modq+1)∈[1,3q+1]) 如下:

[fi(x)+fj(x)-fk0(x)](modq+1)=fm(x)-

[m-(i+j-k0)](modq+1)=fλ(x)

(3)

其中,λ=i+j-k0(modq+1),x∈V(G)=V(Gi)=V(Gj)=V(Gk0)。

(1)首先證明Mixg(G)是任意零元阿貝爾有限??杉訄D群。Gi⊕k0Gj∈Mixg(G), 假設(shè)Gi⊕k0Gj=Gλ,Gi⊕k0Gj=Gμ, 則有λ=i+j-k0(modq+1)=μ。

1)零元 因為Gi⊕k0Gk0=Gi, 所以Gk0是Mixg(G)的零元。

2)逆元 因為Gi⊕k0G2k0-i=Gk0, 所以Gi∈Mixg(G)的逆元是G2k0-i∈Mixg(G)。

3)結(jié)合律 因為[Gi⊕k0Gj]⊕k0Gl=Gi+j-k0⊕k0Gl=Gi+j+l-2k0以及Gi⊕k0[Gj⊕k0Gl]=Gi⊕k0Gj+l-k0=Gi+j+l-2k0,所以[Gi⊕k0Gj]⊕k0Gl=Gi⊕k0[Gj⊕k0Gl]。

綜上,Mixg(G)是一個任意零元阿貝爾有限??杉訄D群{Mixg(G),f;⊕}。 而Gi⊕k0Gj=Gj⊕k0Gi, 可知它又是交換群。

(2)Mixg(G)中任取連續(xù)的q+1+i個圖, 構(gòu)成集合H, 可得H是Mixg(G)的一個任意零元阿貝爾有限??杉訄D子群, 且階為3q+1-i的子群有i+1 個, 其中,i∈[0,2q]。

(3)顯然,Mixg(G)中的前q+1個圖都是(q+1)-模負優(yōu)美的, 后q+1個圖都是(q+1)-模優(yōu)美的。 它們構(gòu)成的圖群都是Mixg(G)的任意零元阿貝爾有限??杉訄D子群。

事實上, 圖1中的19個圖就是按照圖3中Gk的生成方式由G生成的, 其中,前7個圖是(7)-模負優(yōu)美的, 后7個圖是(7)-模優(yōu)美的, 中間的圖都是(7)-?;旌蟽?yōu)美的。

圖3 圖G是(7)-?;旌蟽?yōu)美圖, G能生成19個(7)-模圖Gk, 其中k∈[1,19]

定理2設(shè)H是Mixg(G)的一個非空子集, 則H是Mixg(G)的任意零元阿貝爾有限??杉訄D子群的充分必要條件是對于任意Hi,Hj∈H, 給定Hk0, 有Hi⊕k0H2k0-j∈H。

證明充分性。 由于Hi∈H, 給定Hk0, 則有Hk0=Hi⊕k0H2k0-i∈H, 因此,對于任意的Hj∈H,H2k0-j=Hk0⊕k0H2k0-j∈H。 如果Hi,Hj∈H, 那么H2k0-j∈H, 所以Hi⊕k0Hj=Hi⊕k0H2k0-(2k0-j)∈H。因為Mixg(G)是任意零元阿貝爾有限??杉訄D群, 從而H中的加法運算滿足結(jié)合律, 所以H是Mixg(G)的任意零元阿貝爾有限模可加圖子群。

必要性。 顯然。

設(shè)連通圖G有 (q+1)-模優(yōu)美標號f:V(G)→[0,q], 使得

f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)}({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q]。

記圖G的(q+1)-模優(yōu)美標號f=f1,G=G1。 則對于G的每個拷貝Gk定義(q+1)-模優(yōu)美標號fk如下:

fk(x)=f1(x)+(k-1)(modq+1),

其中,x∈V(G),k∈[1,q+1]。

如果G有 (q+1)-模負優(yōu)美標號號f:V(G)→[-q,0], 使得

f(E(G))={f(uv)=|f(u)-f(v)|:uv(E(G)}({q+1-|f(u)-f(v)|:uv(E(G)}=[1,q]。

記圖G的(q+1)-模負優(yōu)美標號f=f1,G=G1。 則對于G的每個拷貝Gk定義(q+1)-模負優(yōu)美標號fk如下:

fk(x)=f1(x)-(k-1)(modq+1),

其中,x∈V(G),k∈[1,q+1]??傻靡韵陆Y(jié)論:

推論1設(shè)圖G有(q+1)-模(負)優(yōu)美標號f, 則G能生成q+1個(q+1)-模(負)優(yōu)美圖, 這些圖構(gòu)成一個階為q+1的任意零元阿貝爾有限??杉訄D群。

推論3 (q+1)-模(負)優(yōu)美圖的對偶圖能生成q+1個 (q+1)-模(負)優(yōu)美圖, 這些圖構(gòu)成一個階為q+1的任意零元阿貝爾有限??杉訄D群。

設(shè)(p,q)-圖G有 (q+1)-模優(yōu)美標號f:V(G)→[0,q], 如果G按照fl(uv)=f1(uv)+(l-1)(modq+1)能生成q+1個圖, 其中,uv∈E(G)=E(Gl),G1=G,Gk+q+1=Gk(modq+1), 那么, 邊標號f:E(Gl)→[0,q], 稱這q+1個圖是邊模圖, 它們有著相同的頂點標號。 這些圖組成的集合記作Gg(G)={Gl:l∈[1,q+1]}。下面在Gg(G) 上定義加法運算“Gi⊕kGj”, 任意給定Gk∈Gg(G), 則

[fi(uv)+fj(uv)-fk(uv)](modq+1)=fλ(uv),

其中,λ=i+j-k(modq+1),uv∈E(G)=E(Gi)=E(Gj)=E(Gk),

(1)若[fi(uv)+fj(uv)-fk(uv)]<-q, 則[fi(uv)+fj(uv)-fk(uv)](modq+1)=q+1+fi(uv)+fj(uv)-fk(uv);

(2)若[fi(uv)+fj(uv)-fk(uv)]>q, 則[fi(uv)+fj(uv)-fk(uv)](modq+1)=fi(uv)+fj(uv)-fk(uv)-(q+1);

(3)其他情況時, [fi(uv)+fj(uv)-fk(uv)](modq+1)=fi(uv)+fj(uv)-fk(uv)。

那么Gg(G)是任意零元阿貝爾有限??杉訄D群, 記作{Gg(G),f;⊕}。

設(shè)(p,q)-圖G有(q+1)-模優(yōu)美標號f, 根據(jù)運算fk(x)=f1(x)+(k-1)(modq+1)能生成q+1個圖, 其中,x∈V(G)=V(Gk),G1=G,k∈[1,q+1], 這些圖稱為頂點模圖。每個圖Gk保持頂點不變, 根據(jù)運算fk,l(uv)=fk,1(uv)+(l-1)(modq+1)又可以生成q+1個邊模圖, 其中,uv∈E(Gk,l)(Gk,l?Gk),l∈[1,q+1],k∈[1,q+1]。Gk,l的標號fk,l定義如下:

fk,1(x)=f1,1(x)+(k-1)(modq+1),

fk,l(uv)=fk,1(uv)+(l-1)(modq+1),

其中,x∈V(G)=V(Gk,l),uv∈E(G)=E(Gk,l),G1,1=G,f1,1=f,l,k∈[1,q+1]。

事實上, 邊模圖Gk,1,Gk,2,…,Gk,q+1構(gòu)成了一個任意零元阿貝爾有限模可加圖群, 又k∈[1,q+1], 因此,有q+1個由邊模圖構(gòu)成的任意零元阿貝爾有限模可加圖群。 頂點模圖G1,l,G2,l,…,Gq+1,l構(gòu)成了一個任意零元阿貝爾有限??杉訄D群, 又l∈[1,q+1], 因此,有q+1個由頂點模圖構(gòu)成的任意零元阿貝爾有限??杉訄D群。 故每個(q+1)-模優(yōu)美圖G可以生成 (q+1)2個圖, 記作Gk,l(k,l∈[1,q+1]), 這些圖構(gòu)成了2(q+1)個任意零元阿貝爾有限??杉訄D群。

類似可得, 每個(q+1)-模負優(yōu)美圖可以生成q+1個頂點模圖, 每個頂點模圖又可以生成q+1個邊模圖, 這些圖構(gòu)成了2(q+1)個任意零元阿貝爾有限模可加圖群(圖4)。 每個(q+1)-?;旌蟽?yōu)美圖可以生成3q+1個頂點模圖, 每個頂點模圖又可以生成q+1個邊模圖, 從而得到4q+2個任意零元阿貝爾有限??杉訄D群。

圖4 (6,6)-圖G是(7)-模優(yōu)美圖, G可生成頂點模圖和邊模圖,其中k,l∈[0,6]Fig.4 The (6,6)-graph G is a (7)-modular graceful graph, G can generate vertex-modular graphs and edge-modular graphs, k,l∈[0,6]

4 結(jié) 語

給出了(q+1)-?;旌蟽?yōu)美標號, 子群, 有限群, 邊模圖和頂點模圖等概念。 定理 1 給出了(p,q)-圖G是(q+1)-?;旌蟽?yōu)美圖時可以生成的任意零元阿貝爾有限??杉訄D群和圖子群及它們的階。 定理 2 證明了H是Mixg(G)的一個非空子集, 則H是Mixg(G)的任意零元阿貝爾有限??杉訄D子群的充分必要條件是對于任意Hi,Hj∈H, 給定Hk0, 有Hi⊕k0H2k0-j∈H。 最后提出了每個(q+1)-模優(yōu)美圖G可以生成q+1個頂點模圖, 每個頂點模圖又可以生成q+1個邊模圖, 這些圖構(gòu)成了2(q+1)個任意零元阿貝爾有限??杉訄D群。 對于(q+1)-模負優(yōu)美圖和(q+1)-?;旌蟽?yōu)美圖也可以得到類似的結(jié)果。 在同態(tài)圖群加密技術(shù)中, 若圖的頂點或者邊數(shù)較多, 并結(jié)合已有的數(shù)百種著色就可以大大提高信息的安全性。 這里討論的都是有限圖, 對于無限群是否會有類似的結(jié)論?這是今后需要繼續(xù)研究的課題。

猜你喜歡
標號頂點加密
基于廣義logistic混沌系統(tǒng)的快速圖像加密方法
保護數(shù)據(jù)按需創(chuàng)建多種加密磁盤
3≤m≤8,n≥6時射影平面網(wǎng)格圖G璵,n的L(2,1)-標號
幾類圖的字典式乘積圖的(d,1)-全標號
加強學習補差距
加密與解密
一致仙人掌樹的Felicitous性質(zhì)
刪繁就簡三秋樹
數(shù)學問答
一個人在頂點