Verschoben! singuläre matrix über GF(q)

23.01.2011, 02:01	orangebird	Auf diesen Beitrag antworten »
singuläre matrix über GF(q) Hallo, wer kann mir bei folgendem Problem helfen: Finde eine singuläre kxk Matrix M über GF(q) die 2 Bedingungen erfüllt: 1. Die Einträge der Matrix sollen von der Form $\begin{eqnarray} M_{i,k } \end{eqnarray}$ = $\begin{eqnarray} F(M_{i,1},M_{i,2 }....M_{ i,k-1} \end{eqnarray}$ ) für i=1,...,k F ist eine Hashfunktion 2. Es soll eine Vektor im Kern der Matrix M geben dessen letzte Komponente ungleich 0 ist. Anders ausgedrückt: $\begin{eqnarray} v=(v_{1},...,v_{ k})^T element GF(q)^k \end{eqnarray}$ mit Mv=0 und $\begin{eqnarray} v_{ k}=-1 \end{eqnarray}$ wie verdammt noch mal berechne ich das denn Edit (Gualtiero): Vorerst einmal hierher - Hochschulalgebra - verschoben.
23.01.2011, 14:26	Elvis	Auf diesen Beitrag antworten »
Das berechnest du gar nicht, denn das ist nicht Schulmathematik. Bevor wir uns damit beschäftigen, musst du das Buch vollständig abtippen, in dem diese Aufgabe steht.
23.01.2011, 15:42	orangebird	Auf diesen Beitrag antworten »
http://www.cs.berkeley.edu/~daw/papers/genbday.html Kapitel 4....da steht alles
25.01.2011, 19:02	Elvis	Auf diesen Beitrag antworten »
Siehst du, habe ich doch geahnt, dass das sogar in subexponentieller Zeit gelöst werden kann.

Verwandte Themen