Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin





- - - - -

o-wielomiany

Napisane przez Arczi, 07 January 2016 · 693 wyświetleń

Definicja Niech m będzie dowolną dodatnią liczbą całkowitą. Wielomian permutacyjny nad \mathbb{F}_{2^m} nazywamy o-wialomianem, jeśli dla każdego \gamma\in\mathbb{F}_{2^m} funkcja

 

z\in\mathbb{F}_{2^m} \mapsto \{ \frac{G(z+\gamma)+G(\gamma)}{z}, z \neq 0 \\ 0, z = 0

 

jest permutacją ciała \mathbb{F}_{2^m}.

 

Znane o-wielomianów:
1. Automorfizm Frobeniusa G(z)=z^{2^i}, (i,m)=1
2. G(z)=z^6, m - nieparzysta
3. G(z)=z^{3\cdot 2^k +4}, m=2k-1
4. G(z)=z^{2^k+2^{2k}}, m=4k-1
5. G(z)=z^{2^k+2}, m=2k-1
6. G(z)=z^{2^{2k+1}+2^{3k+1}}, m=4k+1
7. G(z)=z^{2^k}+z^{2^k+2}+z^{3\cdot2^k+4}, m=2k-1
8. G(z)=z^{2^{m-1}+2^{m-2}}, m - nieparzysta
9. G(z)=z^{\frac{1}{6}}+z^{\frac{3}{6}}+z^{\frac{5}{6}}, m - nieparzysta
10. G(z)=\frac{\delta^2(z^4+z)+\delta^2(1+\delta+\delta^2)(z^3+z^2)}{z^4+\delta^2z^2+1}+z^{\frac{1}{2}}, Tr_1^m\(\frac{1}{\delta}\)=1, a jeśli m \equiv 2[\text{mod } 4], to \delta \notin \mathbb{F}_4 - o-wielomian Subiaco
11. G(z)=\frac{1}{Tr^n_m(b)}\(Tr_m^n(b^r)(z+1)+Tr^n_m((bz+b^{2^m})^r)(z+Tr^n_m(b)z^{\frac{1}{2}}+1)^{1-r}\)+z^{\frac{1}{2}}, m - parzysta, r=\pm\frac{2^m-1}{3}, b\in\mathbb{F}_{2^{2m}}, b^{2^m+1}=1, b\neq1, gdzie Tr_m^n(x)=x+x^{2^m} jest funkcją śladu z \mathbb{F}_{2^n} do \mathbb{F}_{2^{m}} - o-wielomian Adelaide.

 

DOWÓD 10.

 

1. Zdefiniujmy funkcję śladu: GF(q) \maps GF(2), gdzie q=2^e, poprzez

tr(x)=x+x^2+x^4+\cdots+x^{2^{e-1}}

 

2. Fakt Równanie kwadratowe ax^2+bx+c, a,b,c\in GF(q), a\neq0 jest nierozkładalne nad ciałem GF(q) wtw, gdy b\neq0 oraz tr\(\frac{ac}{b^2}\)=1.

 

3. Niech \mathbb{C}=\{A_t : t\in GF(q)\} będzie rodziną macierzy wymiaru 2\times2 o elementach z GF(q). Zdefiniujmy formę kwadratową Q_{st} jako

Q_{st}(x,y)=(x\;y)(A_s-A_t)\(x \\ y\).

 

Mówimy, że \mathbb{C} jest q-klanem, jeśli forma kwadratowa Q_{st} jest anizotropowa (nieizotropowa) dla wszelkich s\neq t.

 

4. Ponieważ zajmować się będziemy tylko ciałami o charakterystyce 2, to:
Q_{st}=\(a_s+a_t\)x^2+\(b_s+b_t\)xy+\(c_s+c_t\)y^2 jest anizotropowa dla wszelkich s\neq t wtw, gdy:

tr\(\frac{\(a_s+a_t\)\(c_s+c_t\)}{\(b_s+b_t\)^2}\)=1.

 

5. Zdefiniujmy f:GF(q)\maps GF(q) poprzez f(t)=a_t oraz f:GF(q)\maps GF(q) przez g(t)=\frac{c_t}{a}. Wówczas f(0)=g(0)=0 oraz f(1)=g(1)=1. Ponieważ Q_{st} jest anizotropowa dla każdego s\neq t, to mamy,

\mathcal{T}_a(f,g):\;tr\(\frac{a\(f(s)+f(t)\)\(g(s)+g(t)\)}{s+t}\)=1 dla wszelkich s\neq t.

 

6. Twierdzenie Niech q będzie parzysta. Niech f,g:GF(q)\maps GF(q), f(0)=g(0)=0 oraz f(1)=g(1)=1. Wówczas \mathcal{T}_a(f,g) jest prawdziwe wtw, gdy g jest o-wielomianem, f_s jest o-wielomianem dla każdego s\in GF(q), gdzie

f_s(x)=\frac{f(x)+asg(x)+s^{\frac{1}{2}}x^{\frac{1}{2}}}{1+as+s^{\frac{1}{2}}}

oraz tr(a)=1.

 

7. Twierdzenie Niech d \in GF(q), q - parzysta, będzie taki, że d^2+d+1 \neq 0 oraz tr\(\frac{1}{d}\)=1. Niech

a=\frac{d^2+d^5+d^{\frac{1}{2}}}{d\(1+d+d^2\)}, \; f(x)=\frac{d^2\(x^4+x\)+d^2\(1+d+d^2\)\(x^3+x^2\)}{\(x^2+dx+1\)^2}+x^{\frac{1}{2}} oraz g(x)=\frac{d^4x^4+d^3\(1+d^2+d^4\)x^3+d^3\(1+d^2\)x}{\(d^2+d^5+d^{\frac{1}{2}}\)\(x^2+dx+1\)^2}+\frac{d^{\frac{1}{2}}}{d^2+d^5+d^{\frac{1}{2}}}x^{\frac{1}{2}}.

Wtedy

\mathcal{S}=\mathcal{S}_d=\{A_t=\left(\begin{array}{cc}<br />f(t)&t^{\frac{1}{2}}\\<br />0&ag(t)<br />\end{array}\right):\; t\in GF(q)\}

jest q-klanem.

 

Dowód. Zaczniemy od pokazania, że tr(a)=1 dla każdego q parzystego:


tr(a)=tr(a^2)=tr\(\frac{d^9+d^3+1}{d\(d^2+d+1\)^2}\)=tr\(\frac{1}{d}\)+tr\(d+\frac{d^4}{d^2+d+1}\)+tr\(d^2+\frac{d^8}{(d^2+d+1)^2}\)

Zatem tr(a)=tr\(\frac{1}{d}\)=1.
Zapiszmy f i g w nieco innej postaci (co ułatwi nam późniejsze obliczenia):


f(x)=\frac{N_f(x)}{D(x)^2}+x^{\frac{1}{2}} oraz g(x)=\frac{1}{d^2+d^5+d^{\frac{1}{2}}}\frac{N_g(x)}{D(x)^2}+\frac{d^{\frac{1}{2}}}{d^2+d^5+d^{\frac{1}{2}}}x^{\frac{1}{2}}.

Pokażemy teraz, że dla GF(q), q=2^e, że macierze


\left(\begin{array}{cc}<br />f(t)&t^{\frac{1}{2}}\\<br />0&ag(t)<br />\end{array}\right), t \in GF(q)

 

tworzą q-klan. Innymi słowy pokażemy, że \mathcal{T}_a(f,g) jest prawdziwe, a co za tym idzie, że \frac{a(f(x)+f(y))(g(x)+g(y))}{x+y} ma ślad równy 1 dla każdego x\neq y. Od teraz zakładać będziemy, że x\neq y, a więc:

 

\frac{(f(x)+f(y))(ag(x)+ag(y))}{x+y}
=\frac{1}{x+y}\(\frac{N_f(x)}{D(x)^2}+x^{\frac{1}{2}}+\frac{N_f(y)}{D(y)^2}+y^{\frac{1}{2}}\)\(\frac{N_g(x)}{d\(1+d+d^2\)D(x)^2}+\frac{d^{\frac{1}{2}}}{d\(1+d+d^2\)}x^{\frac{1}{2}}+\frac{N_g(y)}{d\(1+d+d^2\)D(y)^2}+\frac{d^{\frac{1}{2}}}{d\(1+d+d^2\)}y^{\frac{1}{2}}\)
=\frac{1}{x+y}\(\frac{N_f(x)N_g(x)}{d\(1+d+d^2\)D(x)^4}+\frac{N_f(x)N_g(y)}{d\(1+d+d^2\)D(x)^2D(y)^2}+\frac{(x+y)^{\frac{1}{2}}}{d^{\frac{1}{2}}\(1+d+d^2\)}\frac{N_f(x)}{D(x)^2}+\frac{N_f(y)N_g(y)}{d\(1+d+d^2\)D(y)^4}+\frac{N_f(y)N_g(x)}{d\(1+d+d^2\)D(x)^2D(y)^2}+\frac{(x+y)^{\frac{1}{2}}}{d^{\frac{1}{2}}\(1+d+d^2\)}\frac{N_f(y)}{D(y)^2}+ \frac{(x+y)^{\frac{1}{2}}}{d^{\frac{1}{2}}\(1+d+d^2\)}\frac{N_g(x)}{D(x)^2}+\frac{(x+y)^{\frac{1}{2}}}{d^{\frac{1}{2}}\(1+d+d^2\)}\frac{N_g(y)}{D(y)^2}+\frac{x+y}{d^{\frac{1}{2}}\(1+d+d^2\)}\)

 

Jeśli teraz E_1,\ldots,E_8 odpowiadać będą pierwszym ośmiu elementom w nawiasie powyższego wyrażenia, to możemy je zapisać jako:


\frac{1}{x+y}\(E_1+E_2+E_3+E_4+E_5+E_6+E_7+E_8+\frac{x+y}{d^{\frac{1}{2}}\(1+d+d^2\)}\)

Dokonamy dalszego podstawienia w lini powyżej, w celu uzyskanina:


A+B+\frac{1}{d^{\frac{1}{2}}\(1+d+d^2\)},

gdzie


A=\frac{1}{x+y}\(E_1+E_2+E_4+E_5\) oraz B=\frac{1}{x+y}\(E_3+E_6+E_7+E_8\).

Teraz


tr\(\frac{1}{d^{\frac{1}{2}}\(1+d+d^2\)}\)=tr\(\frac{1}{d\(1+d+d^2\)}\)=tr\(\frac{1}{d}\)+tr\(\frac{d+d^3}{1+d^2+d^4}\)=tr\(\frac{1}{d}\)+tr\(\frac{d}{1+d+d^2}\)+tr\(\frac{d^2}{1+d^2+d^4}\)=tr\(\frac{1}{d}\)=1.

 

Pozostaje pokazać, że A+B ma ślad zero. Ponieważ tr(A+B)=tr\(A+B^2\), jest to równoważne wykazaniu, iż A+B^2 ma ślad zero.

 

A+B^2
=\frac{1}{x+y}\(E_1+E_2+E_4+E_5+\frac{N_f(x)^2}{d\(1+d^2+d^4\)D(x)^4}+\frac{N_f(y)^2}{d\(1+d^2+d^4\)D(y)^4}+\frac{N_g(x)^2}{d^2\(1+d^2+d^4\)D(x)^4}+\frac{N_g(y)^2}{d^2\(1+d^2+d^4\)D(y)^4}+\)
=\frac{1}{x+y}\(E_2+E_5+\frac{d\(1+d^2+d^4\)N_f(x)N_g(x)+dN_f(x)^2+N_g(x)^2}{d^2\(1+d^2+d^4\)D(x)^4}+\frac{d\(1+d^2+d^4\)N_f(y)N_g(y)+dN_f(y)^2+N_g(y)^2}{d^2\(1+d^2+d^4\)D(y)^4}\).

 

Po uproszczeniu otrzymamy:

 

\frac{1}{x+y}\(E_2+E_5+\frac{d^5\(1+d^2+d^4\)x^8+d^6\(1+d^6\)x^7+d^5\(1+d^6\)x^6+d^8\(1+d^6\)x^5}{d^2\(1+d^2+d^4\)D(x)^4}+\frac{d^5\(1+d^6\)x^4+d^6\(1+d^6\)x^3+d^5\(1+d^2+d^4\)^2x^2}{d^2\(1+d^2+d^4\)D(x)^4}+\frac{d^5\(1+d^2+d^4\)y^8+d^6\(1+d^6\)y^7+d^5\(1+d^6\)y^6+d^8\(1+d^6\)y^5}{d^2\(1+d^2+d^4\)D(y)^4}+\frac{d^5\(1+d^6\)y^4+d^6\(1+d^6\)y^3+d^5\(1+d^2+d^4\)^2y^2}{d^2\(1+d^2+d^4\)D(y)^4}\).

 

Używając 1+d^6=\(1+d^2+d^4\)\(1+d^2\) i dokononując kolejnych uproszczeń, dzieląc przez D(x)^2 (lub przez D(y)^2) i sprowadzając do wspólnego mianownika, otrzymujemy:

 

\frac{1}{x+y}\(E_2+E_5+\frac{d^3x^8+d^4\(1+d^2\)x^7+d^3\(1+d^2\)x^6+d^6\(1+d^2\)x^5+d^3\(1+d^2\)x^4+d^4\(1+d^2\)x^3+d^3x^2}{D(x)^4}+\frac{d^3y^8+d^4\(1+d^2\)y^7+d^3\(1+d^2\)y^6+d^6\(1+d^2\)y^5+d^3\(1+d^2\)y^4+d^4\(1+d^2\)y^3+d^3y^2}{D(y)^4}\)
=\frac{1}{x+y}\(E_2+E_5+\frac{d^3\(x^4+d\(1+d^2\)x^3+x^2\)D(x)^2}{D(x)^4}+\frac{d^3\(y^4+d\(1+d^2\)y^3+y^2\)D(y)^2}{D(x)^4}\)
=\frac{1}{x+y}\(\frac{N_f(x)N_g(y)}{d\(1+d+d^2\)D(x)^2D(y)^2}+\frac{N_f(y)N_g(x)}{d\(1+d+d^2\)D(x)^2D(y)^2}+\frac{d^3\(x^4+d\(1+d^2\)x^3+x^2\)}{D(x)^2}+\frac{d^3\(y^4+d\(1+d^2\)y^3+y^2\)}{D(y)^2}\)
=\frac{1}{x+y}\(\frac{d^5\(1+d^3\)\(1+d\)x^4y^3+d^6\(1+d+d^2\)x^4y^2+d^5\(1+d+d^2\)x^4y+d^5\(1+d^3\)\(1+d\)x^3y^4+d^6\(1+d+d^2\)x^2y^4+d^5\(1+d+d^2\)xy^2+d^5\(1+d+d^2\)^3x^3y^2+d^6\(1+d+d^2\)x^3y+d^5\(1+d^3\)\(1+d\)xy^2+d^5\(1+d+d^2\)^3x^2y^3+d^6\(1+d+d^2\)xy^3+d^5\(1+d^3\)\(1+d\)x^2y}{d\(1+d+d^2\)D(x)^2D(y)^2}+\frac{d^3\(x^4+d\(1+d^2\)x^3+x^2\)D(y)^2}{D(x)^2D(y)^2}+\frac{d^3\(y^4+d\(1+d^2\)y^3+y^2\)D(x)^2}{D(x)^2D(y)^2}\).

 

Dokonując uproszczeń i dzieląc, gdzie to tylko jest możliwe przez d\(1+d+d^2\) oraz grupując, otrzymujemy:

 

\frac{1}{x+y}\(\frac{d^3x^2y^2\(x^2+y^2\)+d^4x^2y^2\(x+y\)+d^4xy\(x^3+y^3\)+d^5xy\(x^2+y^2\)}{D(x)^2D(y)^2}+\frac{d^4\(1+d^2\)xy\(x+y\)+d^3\(x^4+y^4\)+d^3\(x^2+y^2\)+d^4\(1+d^2\)\(x^3+y^3\)}{D(x)^2D(y)^2}\).

 

Dzielimy przez x+y i po prostym uproszczeniu otrzymujemy:

 

\frac{d^4x^3y+d^4xy^3+\(d^5+d^3\)x^2y+\(d^5+d^3\)xy^2+d^3x^3y^2+d^3x^2y^3}{D(x)^2D(y)^2}+\frac{d^3x^3+d^3y^3+d^4\(1+d^2\)x^2+d^4\(1+d^2\)y^2+d^3x+d^3y}{D(x)^2D(y)^2}
=\frac{\(d^3x+d^3y\)\(x^2+dx+1\)\(y^2+dy+1\)+d^6x^2+d^6y^2}{\(x^2+dx+1\)^2\(y^2+dy+1\)^2}=\frac{d^3x+d^3y}{\(x^2+dx+1\)\(y^2+dy+1\)}+\frac{d^6x^2+d^6y^2}{\(x^2+dx+1\)^2\(y^2+dy+1\)^2},

 

co jest postaci X+X^2. Tym samym kończymy dowód naszego twierdzenia.

 

Jak widać dowód nie jest skomplikowany tylko wymaga sporo obliczeń!



  • 0



Maj 2017

P W Ś C P S N
1234567
891011121314
15161718192021
2223242526 27 28
293031    

Kategorie

Ostatnie wpisy

Ostatni odwiedzający