Quadratische Gleichungen in F2n

4.5 Quadratische Gleichungen in $F2n$

4.5.1 Problemstellung

Quadratische Gleichungen (mit $a⁄= 0$ ) der Form

ay2 +by + c= 0, a,b,c∈ F2n

kann man bezüglich $y$ in $F2n$ nicht so einfach lösen wie in $ℝ$ . Wie noch zu sehen sein wird, hat diese Gleichung in $F n 2$ :

möglicherweise keine Lösung;
genau eine Lösung für den Fall $b= 0$ ;
oder sogar zwei Lösungen.

Zuersteinmal kann man sie unter der Voraussetzung $a,b⁄= 0$ mit Hilfe der Substitution $z= ay∕b$ und der naheliegenden Abkürzung $2 β = ac∕b$ in eine allgemeine Form überführen:

Davon ausgehend können wir uns den mathematischen Grundlagen einer Lösung zuwenden [Ber84, Sho05].

4.5.2 Trace

Zuallererst soll eine Hilfsformel eingeführt werden, welche in der einen oder anderen Form immer wieder benötigt wird.⁶⁵ Dazu sei die folgende Summe $λ i$ für ein Element $α ∈ F n p$ definiert und mit $i∈ ℕ$ indiziert (vorerst soll $i⁄= 0$ gelten):

i−1 k λi = ∑ αp k=0

Dann berechnen wir unter Zuhilfenahme des „Anfänger-Traums“ nach Formel 3.13 bzw. 3.14 die $p$ -te Potenz:

[i−1 ]p i−1( ) i−1 i i−1 λp= αpk = αpk p = αpk+1 = αpk = αpi− α + αpk i ∑k=0 k∑=0 k∑=0 k∑=1 ∑k=0

und stellen fest:

p pi i−1 pk λi − λi = α − α, mit λi = ∑ α . k=0

(4.29)

Definition Der Trace ist die Summe der Konjugierten eines Elements im Körper $F n p$ .

n−1 i 2 3 n−1 tr(α )= ∑ αp = α + αp + αp + αp + ⋅⋅⋅+ αp i=0

Mit Formel 4.29 ist der Trace auch darstellbar als:

tr(α) = λn.

(4.30)

Eigenschaften Mit Hilfe der Polynomdarstellung für ein Element $n α ∈Fp$

n−1 α = ∑ αjxj (αj ∈ Fp) j=0

kann man einige interessante Eigenschaften und Beziehungen für den Trace ableiten:

Aus den Formeln 4.29 und 4.30 ergeben sich mit dem kleinen Satz von FERMAT ( $n αp − α = 0$ ) die Beziehungen:

d. h. der Trace ist eine lineare Abbildung $Fpn → Fp$ . Der Grund liegt ganz einfach darin, daß Gleichung 4.31 nur im Körper $Fp$ Gültigkeit hat (nicht in $Fpn$ ) – und deshalb: $tr(α) ∈Fp$ .
Der Trace eines Elements wird nicht verändert, wenn man das Element vorher (mehrfach) zur Potenz $p$ potenziert:

Warum dies so ist, erkennt man durch Anwendung der im Punkt 1 hergeleiteten Formel 4.31 sowie (wieder) des „Anfänger-Traums“ nach Formel 3.14:
$[ ] n−1 ip n−1( i)p n− 1 pi tr(α )= trp(α )= ∑ αp = ∑ αp = ∑ (αp ) = tr(αp). i=0 i=0 i=0$
Der Trace ist linear:
1. $tr(α + β) = tr(α)+ tr(β )$ , mit $α,β ∈ Fpn$
  In ausführlicher Schreibweise des Trace und (wieder) mit Formel 3.14 kann man auch dies schnell beweisen.
  $n−1 i n−1 i i n−1 i n−1 i tr(α+ β )= ∑ (α+ β )p = ∑ (αp + βp )= ∑ αp + ∑ βp = tr(α)+ tr(β) i=0 i=0 i=0 i=0$
2. $tr(cα )= ctr(α )$ , mit $c∈ Fp$ , $n α ∈Fp$
  Ausklammern von $i c= cp = cp$ aus der Summendarstellung des Trace führt zu:
  $n−1 n−1( ) n−1( ) tr(cα)= ∑ (cα)pi = ∑ cpiαpi = ∑ cαpi = ctr(α ). i=0 i=0 i=0$

Im Körper $F2n$ Speziell im Binärkörper $F2n$ entsteht aus Formel 4.29:

λ2i + λi = α2i+ α

(4.33)

und mit der Rekursion $2i−1 λi = λi−1+ α$ die (insbesondere für einen Berechnungsalgorithmus) interessante Beziehung:⁶⁶

2i−1 2 λi = λi−1+ α = λi−1+ α.

(4.34)

Insbesondere aus den Punkten 1 und 2 auf Seite 147 ergeben sich weitere spezialisierte Eigenschaften:

Quadrieren des Arguments $α$ in $tr(α )$ ändert nach Formel 4.32 nichts am Wert des Trace.

$tr(α)= tr(α2)= tr(α2k), k ∈ℕ$ (4.35)
Das Potenzieren eines Trace ändert ebenfalls nichts an seinem Wert.⁶⁷

$i tr(α) = tr(α), i∈ ℕ$ (4.36)

Grundlage des Beweises bilden die folgenden beiden Reduktionsfälle:
${ i∕2 tri(α )= tr (α ) (i gerade) tr(i+1)∕2(α ) (i ungerade).$

Sie erlauben es, den Exponenten iterativ bis auf $1$ zu reduzieren, was letztlich zu $tri(α )= tr(α )$ führt.
In einer kurzen Fallbetrachtung für $i$ gerade:
$i i∕2 2 i∕2 tr(α) = [tr (α)] = tr (α)$

bzw. $i$ ungerade (und so $i− 1$ gerade):
$tri(α )= tr(α )tri− 1(α )= tr(α )[tr(i− 1)∕2(α )]2 = tr(α)tr(i−1)∕2(α)= tr(i+1)∕2(α)$

kann man die Begründung finden.
Aus der Linearität des Trace und aus Formel 4.32 ergibt sich direkt: $2 2 tr(α + α + β)= tr◟(α-)+◝◜-tr(α◞)+tr(β)= tr(β ). 0$
Eine bemerkenswerte Formel, insbesondere im Zusammenhang mit der Lösung quadratischer Gleichungen in $F2n$ , ist die folgende:
$2 n−1 2i i−1 2k αtr(β)+ β tr(α)= γ + γ, mit γ = ∑i=1 β λi und λi = k∑=0α .$ (4.37)

Ihr Beweis startet, indem man auf die äußere Summe den „Anfänger-Traum“ anwendet und danach mit $i:= i− 1$ umindiziert. Mittels Formel 4.34 wird im Anschluß $λ2i−1$ substituiert.
$n−1 i+1 n i n i γ2 = ∑ β 2 λi2= ∑ β2λ 2i−1 = ∑ β 2(λi+ α) i=1 i=2 i=2$

Läßt man die Summe bei $i= 1$ starten, dann ist zwar eine Korrektur um $β2(λ1+ α)$ vonnöten, letztlich ändert sich wegen $λ1 = α$ aber überhaupt nichts ( $λ1+ α = 0$ ). Jetzt noch den Summanden für $i= n$ herausziehen, ausmultiplizieren und $β2n = β$ sowie $λ = tr(α ) n$ entsprechend Formel 4.30 berücksichtigen:

Im letzten Schritt wird noch der Summand für $i= 0$ hinzugenommen: $n−1 2i n−1 2i ∑i=1 β = β + ∑ i=0 β = β + tr(β )$ und man erkennt, daß der ganz rechte Term genau $γ$ darstellt.

Algorithmus Die Idee für einen Algorithmus steckt in der Darstellung 4.30 für den Trace bzw. hinter Rekursionsformel 4.34.

Algorithmus 8: Trace eines Elements $α ∈ F2n$

Ensure: $λ = tr(α )$ $λ ⇐ α$
for $i= 1$ to $n− 1$ do
$2 λ ⇐ λ + α$ { $2 λi = λi−1+ α$ }
end for

4.5.3 Halb-Trace

Der Halb-Trace ist eine wichtige Funktion für den Fall, daß $n$ für den Binärkörper $F2n$ ungerade ist.

Definition

(n−1)∕2 22i (n−1)∕2 4i (n−1)∕2( 2i)2i htr(α )= ∑ α = ∑ α = ∑ α i=0 i=0 i=0

Eigenschaften

Der Halb-Trace ist genauso linear wie der Trace. $htr(α+ β )= htr(α )+ htr(β)$
$htr(α2)= htr2(α)$ , es gilt jedoch hier: $htr(α2) ⁄= htr(α)$ , wehalb $htr(α )$ kein Element aus $F2$ (im Gegensatz zum Trace), sondern aus $F2n$ ist.
Einsetzen der Polynomdarstellung von $α$ führt in ähnlicher Art und Weise wie beim Trace zu:
$[ ]2 2 (n− 1)∕2( 2)22i (n−1)∕2( 22i)2 (n−1)∕2 22i 2 htr(α )= ∑ α = ∑ α = ∑ α = htr(α ) i=0 i=0 i=0$
$htr(α2)+ htr(α )= α + tr(α)$
Etwas ausführlicher

Umindizierung der beiden Summen mit $l := 2i+ 1$ bzw. $l := 2i$ führt unter zusätzlicher Berücksichtigung von $2n α = α$ zum Ergebnis:
Aus den beiden vorangegangenen Punkten ergibt sich:
$α +tr(α )= htr2(α )+ htr(α) = γ2+ γ$ (4.38)

Algorithmus Der Algorithmus arbeitet ähnlich wie beim Trace (vgl. Algorithmus 8), außer daß der zusätzlichen Potenzierung Rechnung getragen wird.

Algorithmus 9: Halb-Trace eines Elements $α ∈ F2n$

Ensure: $h = htr(α )$ $h ⇐ 0$
for $i= 0$ to $(n− 1)∕2$ do
$2 h ⇐ h$
$h ⇐ h2 + α$
end for

4.5.4 Lösung

Ist $β = 0$ dann sind die Lösungen $0$ und $1$ .

Im allgemeinen gilt:

d. h. eine Voraussetzung für die Existenz der zwei Lösungen ist $tr(β)= 0$ .

Für den Spezialfall, daß $n$ ungerade ist, kann man mit der Grundvoraussetzung $tr(β)= 0$ aus Formel 4.38 direkt eine Lösung der quadratischen Gleichung ablesen:⁶⁸

htr2(β)+ htr(β )= β

(4.39)

Mit $htr2(β)+ htr(β)= [htr(β)+ 1]htr(β )$ sind die zwei Lösungen demzufolge $z1 = htr(β )$ und $z2 = htr(β)+ 1$ .

Ist $n$ jedoch gerade (bzw. im allgemeinen Fall), dann besteht eine Berechnungsmöglichkeit durch Anwendung von Formel 4.37. Setzt man nämlich als Grundvoraussetzung $tr(β)= 0$ , dann gilt:

β tr(α) = z2+ z, mit z= n−1β 2iλ und λ = i−1α2k ∑i=1 i i ∑k=0

d. h. findet man ein Element $α$ mit $tr(α) = 1$ , wodurch

β = z2+ z

dann kann man die Lösung $z$ aus diesem Element $α$ berechnen. Glücklicherweise besitzt im Mittel die Hälfte aller Elemente $α ∈ F2n$ einen Trace von $1$ , so daß man $α$ durchaus zufällig wählen kann (mit 50% Wahrscheinlichkeit für $tr(α )= 1$ ).

Algorithmus Für den allgemeinen Fall (bzw. wenn $n$ gerade ist) kann man auf Algorithmus 10 zurückgreifen, um die quadratische Gleichung in $F2n$ zu lösen [ANS05, IEE00].

Beide Summen können vereint werden, wenn man $λi$ iterativ in der äußeren Summe mitberechnet (nach derselben Methodik wie in Algorithmus 8), was dann im letzten Durchlauf $λn = tr(α )$ ergibt.

Und es gilt ja nach Formel 4.37, unter der Voraussetzung $tr(β) = 0$ und $tr(α = 1 )$ , immer:

n−1 i−1 γ = β + γ2, mit γ = β 2iλi und λi = α2k ∑i=1 ∑k=0

Algorithmus 10: Lösung der quadratischen Gleichung in $F2n$

Ensure: $n−1 2i z = ∑i=1 β λi$ , mit $i−1 2k λi = ∑ k=0 α$ repeat
$α ⇐$ zufälliges Element aus $F2n$
$z ⇐ 0$
$λ ⇐ α$ { $λ1 = α$ }
for $i= 1$ to $n− 1$ do
$z ⇐ z2+ λ 2β$ { $z = z2 +β$ für $i= n− 1$ (bzw. $λn = tr(α )= 1$ )}
$λ ⇐ λ2+ α$ { $λ = λ2 + α i i−1$ }
end for
until $λ = 1$ { $tr(α) = 1$ }

Optimierung Schreibt man dazu unter Zuhilfenahme der Polynomdarstellung für das Element $α$ und noch unter Berücksichtigung von Formel 3.13:

n−1(n −1 )2i n−1n−1( ) i n− 1n−1 ( )j tr(α)= ∑ ∑ αjxj = ∑ ∑ αjxj 2 = ∑ ∑ α2ij x2i . i=0 j=0 i=0j=0 i=0 j=0

Umsortieren der Summen und mit $αl = αj j$ in $F2$ und dann wieder mit Formel 3.13

n−1 n−1( 2i)j n−1 n− 1( j)2i n−1 j tr(α )= ∑ αj ∑ x = ∑ αj ∑ x = ∑ αjtr(x ) j=0 i=0 j=0 i=0 j=0

Den Wert für $j tr(x )$ kann man vorausberechnen.