Algebraisch unabhängig

Neue Frage »

Metti Auf diesen Beitrag antworten »
Algebraisch unabhängig
Hallo!
Ich finde in den Quellen für meine Diplomarbeit immer wieder den Begriff "algebraically independent" also algebraisch unabhängig.

Ich weiß auch grob, was es bedeutet:
Ich habe eine Menge von Polynomen und wenn diese die o.g. Eingenschaft besitzen, dann haben sie möglicherweise gemeinsame Nullstellen.

Aber ich weiß nicht genau, was es bedeutet und ich bin auch nicht so bewandert in diesen Sachen. Daher fänd ich es gut, wenn mir jemand die Sache kurz erklären könnte...

Danke schon mal und liebe Grüße aus Australien,
Matthias
Ben Sisko Auf diesen Beitrag antworten »
RE: Algebraisch unabhängig
Hallo Metti,

hilft dir folgende Definition? Klick

Um was geht es in deiner Diplomarbeit?

Ich nehm das Thema mal mit in die HöMa.

Gruß vom Ben
Metti Auf diesen Beitrag antworten »

Hallo Ben,
danke für den Link, den versteh' ich nur nicht ganz.
Ich bin nämlich kein Mathematiker, sondern nur ein einfacher Wirtschaftsinformatiker. :P

Alsowenn ich es richtig verstehe sagt der Link, den Du gepostet hast etw das:

Bei mir geht es um Polynome (h_1 und h_2) in R[x,y], das ist dann die Körpererweiterung nehme ich an?!

Wenn es ein (nicht triviales) Polynom f(a,b) aus (R[x,y])[a,b] gibt, für das gilt:
f(h_1,h_2)=0
dann sind h_1 und h_2 algebraisch abhängig.

Also z.B.:
h_1 = x²+3xy
h_2 = x + 3y
und f(a,b)=42a - 42xb
=> f(h_1,h_2)=0 also abhängig?

Kann man (R[x,y])[a,b] schrieben? Oder wie sagt man, dass es sich um ein Polynom aus R[x,y] handelt?

===========

In der Diplomarbeit geht es um RSA und speziell um die Angriffe, die auf Gitterbasenreduktion basieren. Dabei werden bei bestimmten Verfahren mehrere Polynome gefunden, deren gemeinsame Nullstellen interessant sind. Und die sind garantiert linear unabhängig (also die koeff. vektoren) aber eben nicht garantiert alg. unabhängig.

Danke schon mal so weit.

Ben: "Ich nehm das Thema mal mit in die HöMa"

Ich bin stolz, dass ich es so weit gebracht habe!

Gruß,
Matthias
Tobias Auf diesen Beitrag antworten »

Hallo,

mal abgesehen von deinem eigentlichen Problem: Ist R[X, Y] überhaupt ein Körper? Meines Wissens ist dies ein Polynom-Ring aus endlichen Polynomen. Kann es sein, dass manche Elemente aus R[X, Y] kein Inverses haben? Laurentreihen R((X)) wären in dem Zusammenhang Körper.

Ansonsten finde ich die Notation (R[X, Y])[A, B] schon gut gelungen. :]


MfG

P.S.: Ich bin auch nur ein blöder Informatik-Student (und noch blöder, weil ohne Vordiplom) aber das Thema deiner Diplomarbeit finde ich hoch interessant. Glaubst du, du wirst sie im Netz publizieren?
Ben Sisko Auf diesen Beitrag antworten »

Hallo Metti,

das mit der Körpererweiterung brauchst du erstmal nicht (nehm ich an). Polynome lassen sich ohne weiteres über Ringen bilden.

(R[x,y])[a,b] heisst dann hier:"Polynom mit Variablen a und b und Koeffizienten aus R[x,y]", also wiederum Polynome als Koeffizienten.

Jetzt müssten wir nur noch rauskriegen, was genau du damit machen musst bzw. wo du sie brauchst. Augenzwinkern

Gruß vom Ben
Metti Auf diesen Beitrag antworten »

@Tobias: Denke schon, dass ich sie ins Inet stelle. Kann ja wenns so weit ist, hier den Link posten. (ende nächster woche schätze ich).

@Ben:
Die Verfahren, die ich beschreibe liefern mir linear unabhängige Polynome. Meistens aus R[x].
Aber an einigen Stellen werden Polynome aus R[x,y] gefunden. Da brauche ich ja zwei, damit ich die gem. Nullstellen finden kann. Allerdings sind die gefundenen Polynome eben i.A. nicht algebraisch unabhängig (steht so in den Quellen). Daher sind diese Verfahren heuristisch (man nimmt an, sie seien alg. unabh.)
Ich verstehe und verwende den Begriff "algebraisch unabhängig" so:
n Polynome in n Unbekannten, die algebraisch unabhängig sind, liefern die gemeinsamen Nullstellen, die anderen nicht. Kann man das so sagen?

Jeden falls meint ein Betreuer zu mir, ich sollte das noch erläutern, was algebraisch unabhängig bedeutet. Aber ich fänd es jetzt zu weit ausgeholt mit Körpern und Ringen usw. zu argumentieren. Am liebsten wär mir eine Definition die sagt:

"Algebraisch unabhängig in diesem Zusammenhang bedeutet, dass die Polynome nicht <leicht verständliche Eigenschaft> erfüllen. [Quelle, S.42]"

Wenn ich diese Eigenschaft mit der Definition aus dem Link wiederlegen möchte, dann bilde ich demnach tatsächlich eine Fuktion aus (R[x,y])[a,b]. Krass! (für mich jedenfalls)

Danke schonmal vielmals für alles bisher Geschriebene und sende viele Grüße aus Maryborough/Australien,
Matthias

P.S.:Meint ihr, diese Diskussion müsste dann auch in die Quellenangabe? Naja, ist auch nur ein nebensächlicherer Teil der Arbeit...
 
 
Poff Auf diesen Beitrag antworten »

@Metti,

hab mal eine Frage.

Nun wo du eine Arbeit über Angriffe auf das RSA-Verfahren
verfasst, müsstest du doch auch über die aktuelle Sicherheits-
lage dieses Verfahrens bezüglich etwas 'Bescheid' wissen.

Schon immer wird gemunkelt, dass es schnelle Faktorisierungs-
möglichkeiten und was auch sonst noch immer geben könnte ...
ist an dem und 'ähnlichen' Unterstellungen deiner Meinung was
dran, oder reicht das mehr in die Gerüchteküche.

Ich kann mich noch erinnern dass ein 512Bit-Schlüssel für mehr
als ausreichend sicher beschrieben wurde und wenn ich nicht irre
sollen derweil sogar 1024Bit schon eher kritisch gesehen werden
.... wie siehts wirklich aus. Weißt du da näheres.

Ist damit zu rechnen, dass in den frei zugänglichen Varianten
Backdoors versteckt sind ...
was ist deine persönliche Meinung dazu ??

Schonmal danke für deine Antwort.

smile
Ben Sisko Auf diesen Beitrag antworten »

Poff, vielleicht ist es Metti ganz recht, wenn wir diese Diskussion auf die Zeit nach der Abgabe verschieben?!? Ist ja nicht mehr so lang.

Metti, die Definition könntest du natürlich schon genauso übernehmen, wie sie hier im Lexikon steht (oder ist in deinen Quellen irgendwo eine andere? Gibt´s da überhaupt eine?).
Was dann imho zur Erklärung noch fehlt ist der Zusammenhang zwischen dieser Definition und den gemeinsamen Nullstellen (die sind ja genau das, was du davon benutzt, oder? Als Anwendung der algebr. Unabhängigkeit). Leider sehe ich eben diesen Zusammenhang nicht. unglücklich Mag daran liegen, dass der Begriff der algebr. Unabhängigkeit mir auch nicht vertraut ist. Sieht das vielleicht sonst jemand?

Gruß vom Ben
Poff Auf diesen Beitrag antworten »

Zitat:
Poff, vielleicht ist es Metti ganz recht, wenn wir diese Diskussion auf
die Zeit nach der Abgabe verschieben?!? Ist ja nicht mehr so lang.


... kein Thema 'Ben' bzw 'Metti', ist schon ok

.
Metti Auf diesen Beitrag antworten »

@Poff:
Ist nicht mein Kernthema, ich hab aber auch mal den aktuellen Stand der Faktorisierungsangriffe geprüft. Also 1024 ist (offiziell) noch von niemandem geknackt worden. Wenn man einfach den Trend aus der Vergangenheit fortsetzt, dauert es auch noch ca. 15-20 Jahre. Aber es gibt einige Unwägbarkeiten. Zum Beispiel wird der Algorithmus in letzter Zeit nicht mehr wirklich verbessert.

Eine neue Gefahr stellt aber Spezialhardware dar, die bisher (offiziell) nur theoretisch machbar ist. Wenn man eine Chipfabrik besitzt würde sie nur ca. 50 Millionen Dollar kosten. (über den Betrag wird auch gestritten) Die soll aber einen RSA Schlüssel von 1024-Bit in einem Jahr faktorisieren können. Mitentwickelt wurde das TWIRL genannte Gerät übrigens von Shamir. Aber hier ist halt nicht klar, ob so ein Gerät überhaupt gebaut werden kann. Außerdem "lohnt" es sich ja auch nur, wenn der Schlüssel einen Wert von mehreren Millionen Krachern (ob Euro oder Dollar ist hier oBdA freigestellt) hat.

RegTP, NIST und RSA-Security empfehlen den Umstieg auf 2048 Bit.

@Ben:
Ich denke es mir (als mathematischer Freischwimmer) so:
Wenn die Polynome nicht algebraisch abhängig sind, dann gibt es keine Möglichkeit, durch Multiplikation mit anderen Polynomen, ein Polynom in das andere überzuführen. Kann jetzt leider nicht genau ausdrücken, was ich meine, aber ich denke, wenn ich endlich viele gemeinsame Nullstellen finden möchte, brauch ich zwei alg. unabhängige Polynome, sonst bekomme ich unendlich viele...
Keine Ahnung, ehrlich gesagt geht diese Betrachtug schon über meinen Horizont. (Und auch den der Arbeit)
Danke jedenfalls schonmal für Eure Hilfe, ich denke ich muss in der Arbeit etwas zusammenfuddeln.

Gruß,
Metti
Eddi Kett Auf diesen Beitrag antworten »

Hallo Metti,

ich verstehe das jetzt so: Du hast zwei Polynome in zwei Unbestimmten und suchst die Menge ihrer gemeinsame Nullstellen. Du sagst, wenn die Polynome (in einem noch bestimmten Sinne) "unabhängig" sind, dann ist diese Menge endlich. Und nun wüsstest du gern, was genau diese "Unabhängigkeit" bedeutet.
Man kann den Begriff der algebraischen Unabhängigkeit auf Ringerweiterungen fortsetzen, so wie du es in einem früheren Beitrag getan hast. Es ist jedoch fraglich, ob dieser Begriff zu denselben Folgerungen führt wie im Fall einer Körpererweiterung, falls du bestimmte Folgerungen aus der algebaischen Unabhängigkeit brauchen solltest.
Falls du also sicher sein musst, dass die Nullstellenmenge endlich ist, solltest du einen Beweis haben (oder zitieren können), der auch den hier benötigten Fall der Ringerweiterung umfasst.

Ich denke, diese Diskussion brauchst du in deiner Arbeit nicht nennen, da sie (noch) nicht zu wirklichen Resultaten geführt hat, den Hinweis auf die Definition hätte dir auch dein Betreuer geben können. Vielleicht hilft es uns aber dabei, dir weiterzuhelfen, wenn du uns einige deiner Quellen gibst, in denen dieser Unabhängigkeitsbegriff verwendet wird.
Metti Auf diesen Beitrag antworten »

Hallo!
Also vorweg erstmal: Ich bin echt überrascht von dieser Community. Ich finde die hilfsbereitschaft echt bemerkenswert. (Soll heißen: Danke)

Hier ist eine Quelle, die den Begriff benutzt. (S.6 vorletzter Absatz)

Wenn ich ehrlich bin, weiß ich nicht, was ein Ring und ein Körper ist (im mathematischen Sinne). Ist zwar ein Armutszeugniss für einen Wirtschaftsinformatiker, aber die entsprechende Matheklausur konnte man auch ohne dieses Wissen "gut" bestehen :-)

So, ich mach mir jetzt mal nen Kaffee.

Gruß,
Metti
Ed Ding Auf diesen Beitrag antworten »

Interessant, dieselbe Quelle hatte ich auch schon gefunden *g* Verwendest du sie in deiner Arbeit?

In einem meiner Bücher (Lorenz, Algebra I) wird die algebraische Unabhängigkeit von Polynomen über einem Körper K definiert, indem man zum Quotientenkörper des Polynomrings K[x,y] übergeht, man hat damit eine Körpererweiterung K(x,y) / K. Der Unabhängigkeitsbegriff ist dann genau der, den du beschrieben hast: Die Polynome h_1 und h_2 aus K[x,y] sind algebraisch abhängig, wenn es ein Polynom f aus (K(x,y))[a,b] gibt mit f(h_1, h_2) = 0. Das Polynom muss dann noch mit dem Hauptnenner seiner Koeffizienten (die ja rationale Funktionen sind) multipliziert werden, um ein Polynom f' aus (K[x,y])[a,b] zu liefern.

Allerdings lese ich da nichts von Polynomen über einem Ring. Aber vielleicht kann man da ebenfalls zum Quotientenkörper übergehen. Im Falle von Z ist das Q, und das Polynom f' aus (Q[x,y])[a,b] ergibt mit einer geeigneten ganzen Zahl multipliziert ein Polynom f'' aus (Z[x,y])[a,b].

Die Unterscheidung zwischen Ring und Körper ist sehr wichtig in der Mathematik, die beiden Konzepte solltest du unbedingt verstehen.
Metti Auf diesen Beitrag antworten »

Hallo nochmal!

Ich werde das in der Arbeit glaub ich nur kurz erwähnen. Das bringt an der Stelle nichts das auszuwalzen.

Zitat:
Die Unterscheidung zwischen Ring und Körper ist sehr wichtig in der Mathematik, die beiden Konzepte solltest du unbedingt verstehen.


Ne, ich bin jetzt fertig mit meinem Studium. Ich lern nix mehr!
:-)

Gruß, Metti
Poff Auf diesen Beitrag antworten »

Zitat:
Original von Metti
...
Ne, ich bin jetzt fertig mit meinem Studium. Ich lern nix mehr!
:-)



Ich befürchte das wirst du nochmal überdenken müssen . Augenzwinkern
.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »