Generic Ring Algorithmus < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:32 Di 15.05.2007 | | Autor: | MrPink |
Moin!
Ich muss wegen einem Paper mit einem "Generic Ring Algorithmus" arbeiten. Ich weiss nur leider nicht genau, was ein "Generic Ring" ist. Vermute es ist ein einfacher Körper. Ich müsste allerdings genau wissen was für ein Körper.
Und der Algorithmus wird dann vermutlich auf den diesem Körper arbeiten ?!
Über ein wenig aufklärung wäre ich erfreut 
Danke im Voraus!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:59 Di 15.05.2007 | | Autor: | piet.t |
Hallo,
nur mal ein Schuss ins Blaue, aber könnte es vielleicht anders geklammert sein? Also ein generic (ring algorithm), sprich ein generischer Algorithmus, der auf einem Ring arbeitet?
Was ein Generic Ring sein sollte wüsste ich nicht (was noch nichts heissen soll), ein Körper hieße meines Wissens ja auch "field".
Gruß
piet
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:20 Di 15.05.2007 | | Autor: | felixf |
Moin MrPink!
> Ich muss wegen einem Paper mit einem "Generic Ring
> Algorithmus" arbeiten. Ich weiss nur leider nicht genau,
> was ein "Generic Ring" ist. Vermute es ist ein einfacher
> Körper. Ich müsste allerdings genau wissen was für ein
> Körper.
> Und der Algorithmus wird dann vermutlich auf den diesem
> Körper arbeiten ?!
Ein Koerper ist das sicher (im Allgemeinen) nicht.
Ein `generic ring' ist einfach irgendein (abstraktes) Modell eines Ringes, von dem man nichts weiss (bzw. annehmen kann) ausser das es ein Ring ist. Also man kann nur davon ausgehen, dass man Objekte addieren, subtrahieren, multiplizieren kann, und dass man vergleichen kann und auf 0 und 1 zugreifen kann. Und evtl. noch testen kann, ob ein Element invertierbar ist und ggf. Inverse berechnen. (Je nachdem wie man das nun genau definiert.)
Ein `generic ring algorithm' ist ein Algorithmus, der mit einem `generic ring' arbeitet: Man kann ihn also jeden beliebigen Ring vorwerfen, und er muss immer funktionieren, da er nichts besonderes ueber den Ring voraussetzen kann. Also weder das er von der Form [mm] $\IZ/n\IZ$ [/mm] ist noch das es ein Koerper ist oder das er lokal ist oder sonst etwas.
(In der Berechnenden Gruppentheorie gibt es uebrigens analog das Konzept der `generic group' und dem `generic group algorithm'. Wenn du dich etwas mit Kryptographie auskennst, es gibt da ein Paper von Shoup (glaube ich) in dem gezeigt wird, dass das Diskrete-Logarithmus-Problem bei generischen Gruppen der Ordnung $p$ (Primzahl) [mm] $\Theta(\sqrt{p})$ [/mm] ist, es also keine subexponentiellen oder gar polynomiellen Algorithmen gibt. Das ist ein ziemlich starkes Resultat, da es einige (konkrete) Gruppen von Primzahlordnung gibt, fuer die es sehr wohl Algorithmen zum Loesen des DLPs gibt (z.B. in [mm] $(\IZ/p\IZ, [/mm] +)$ in polynomieller Zeit und in [mm] $\IF_q^*$ [/mm] in subexponentieller Zeit). Aber fuer eine Gruppe uber die man sonst nix weiss (also eine `generic group') geht es halt nur exponentiell.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:01 Di 15.05.2007 | | Autor: | MrPink |
Ok, gut das ich nach gefragt habe Sonst hätte wohl doch daneben gelegen. Du scheinst dich damit aus zu kennen, mit einem Generic Group Algortihmus habe ich auch zu tun. Hast du noch nen paar Links dazu ? Bevor ich die Frage hier gestellt habe, habe ich natürlich selber versucht mir was zu ergoogeln, habe aber leider nix gefunden.
Ich habe es aber richtg verstandeb, dass in einem Generic Ring die normalen Definitionen für eine Ring gelten. Also zwei verknüpfungen, Assoziativtät, Distribut. ... etc. Oder liege ich da falsch ? Und der Algoritmus kann dann diese Verknüpfungen nutzen ? Und eine Generic Group hat dann eine Verknüpfung, die der Algo. nutzen kann ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:50 Di 15.05.2007 | | Autor: | felixf |
Hallo!
> Ok, gut das ich nach gefragt habe Sonst hätte wohl doch
> daneben gelegen. Du scheinst dich damit aus zu kennen, mit
> einem Generic Group Algortihmus habe ich auch zu tun.
Auskennen ist etwas uebertrieben ;)
> Hast
> du noch nen paar Links dazu ? Bevor ich die Frage hier
> gestellt habe, habe ich natürlich selber versucht mir was
> zu ergoogeln, habe aber leider nix gefunden.
Nicht wirklich... Lies dir vielleicht mal den Anfang von Shoups Paper durch: http://www.shoup.net/papers/dlbounds1.pdf
Vielleicht findest du Im Abschnitt `related work' Referenzen wo du mehr Infos finden kannst.
Ansonsten such auch mal nach `black box group' bzw. `black box ring'.
Eventuell kannst du auch in Kryptographie-Buechern/Skripten/... fuendig werden, insbesondere wenn dort das Paper von Shoup bzw. das Resultat daraus diskutiert wird.
> Ich habe es aber richtg verstandeb, dass in einem Generic
> Ring die normalen Definitionen für eine Ring gelten. Also
> zwei verknüpfungen, Assoziativtät, Distribut. ... etc. Oder
> liege ich da falsch ?
Genau.
> Und der Algoritmus kann dann diese
> Verknüpfungen nutzen ? Und eine Generic Group hat dann eine
> Verknüpfung, die der Algo. nutzen kann ?
Ja, wuerd ich so sagen.
Ich hab leider nie eine richtige formale Definition von dem ganzen gesehen, daher kann ich das nur soweit beantworten wie ich glaube das richtig verstanden zu haben.
Falls du eine gute Einfuehrung/Definition/sonstwas findest, waer schoen wenn du das hier hinschreiben koenntest. Wuerd mich auch interessieren :)
LG Felix
|
|
|
|
