Bestimmung von (X+a)^n != X^{n mod r} + a

Status des Themas:
Es sind keine weiteren Antworten möglich.

Diskutiere Bestimmung von (X+a)^n != X^{n mod r} + a im Mathematik Forum; Hallo, nachdem ich mit viel hilfe in diesem Thread[1] den ersten Teil vom AKS Algorithmus implementiert habe, stehe ich nun vor einem neuen...

  1. hawkeye78
    hawkeye78 Neues Mitglied
    Hallo,

    nachdem ich mit viel hilfe in diesem Thread[1] den ersten Teil vom AKS Algorithmus implementiert habe, stehe ich nun vor einem neuen Problem und zwar das ich für eine Schleife die von 1 bis 2*sqrt(r) + log n (mit gegebenen r und n als natürliche Zahlen, sowie a als Laufvariable) bestimmen ob (X+a)^n != X^{n mod r} + a ist und falls ja die Methode mit einem entsprechenden Rückgabewert verlassen.
    Nun wäre meine persönlich erste Idee ich multipliziere das ganze aus und überprüfe dann ob das Binom dem Polynom entspricht, blöderweise soll das ganze aber in logarithmischer Zeit gehen was mich vor das Problem stellt das ich keine Ahnung habe wie man das ordentlich implementieren könnte....
    Ich habe nun die Hoffnung das vielleicht hier jemand mitliest der besser in Mathe ist als ich das bin oder vielleicht sogar schon den AKS Algorithmus implementiert hat, ich wäre über einen entsprechenden HInweis auf jeden Fall sehr dankbar. Den auch wenn der Algorithmus wenig praktischen Nährwert hat fühle ich mich doch jetzt an meiner Ehre gepackt und möchte das ganze vollständig zum laufen bringen.
    Viele Grüsse
    Dan


    [1] http://www.java-forum.org/mathematik/82193-berechnung-von-n-b-c.html
     
  2. Vielleicht hilft dir diese Seite hier weiter (Klick!)
  3. 0x7F800000
    0x7F800000 Neues Mitglied
    Da du nur sehr schwammig formuliert hast was du willst, und nirgends gesagt hast, was die ganzen buchstaben heißen sollen, kann ich dir nichts konkretes empfehlen...

    Irgendwas mit einem natürlichen exponent potenzieren geht jedenfalls so in logarithmischer zeit:
    Exponentiation by squaring - Wikipedia, the free encyclopedia
    ...ist sehr üblich, wird dauernd überall verwendet.
     
  4. hawkeye78
    hawkeye78 Neues Mitglied
    Hallo,

    vielleicht hast Du recht und ich sollte wirklich mal aus einander ziehen was die einzelnen Variabeln bedeuten, Der AKS Algorithmus bekommt eine Variable n die darauf geprüft werden soll ob sie eine Primzahl ist.
    Danach wird in einer while Schleife getestet ob es eine Primzahl gibt (mit r < n) für die gilt n^i mod r != 1 für alle Zahlen zwischen 1 und 4*log n², wenn so eine Zahl gefunden wird wird die Schleife verlassen.
    Und nun kommt die for-Schleife die mir soviel sorgen macht...Dort wird nun eine Laufvariable a definiert die von 1 bis 2*sqrt(r) * log n läuft und halt obige Äquivalenz testen soll. Da ich aber leider das X nicht gegeben habe, bin ich nun etwas Ratlos wie man diese Äquivalenz in adäquater Zeit testen könnte.
    Für den Fall das meine Erklärungen immer noch etwas wirr sind (ich habe schließlich heute morgen noch keinen kaffee getrunken ;) ) habe ich einfach mal die entsprechende Folie aus meiner Vorlage ausgeschnitten und als Anhang bei gefügt.
    viele Grüsse
    Dan
     

    Anhänge:

    • aks.png
      aks.png
      Dateigröße:
      81,1 KB
      Aufrufe:
      23
  5. 0x7F800000
    0x7F800000 Neues Mitglied
    "X" ist keine Unbekannte, das ist einfach eine Variable aus einem Polynom aus diesem etwas abschreckenden Polynomring (Z/nZ[x])/(X^r-1).
    Du musst also:
    1) Mit dem Restklassenring Z/nZ = Zn = Fn (oder wie auch immer man die notiert) für richtig abratig große n rechnen können (brauchst wohl big Integer)
    2) Mit den Polynomringen in mindestens einer Variable über solchen Körpern rumrechnen können, dann bekommst du insbesondere den Z/nZ[x]
    3) dort musst du polynomdivision implementieren, und bei jeder polynom addition/multiplikation im Z/nZ[x] alles modulo (X^r-1) rechnen. Dann verhält sich das alles so wie (Z/nZ[X])/(X^r-1)
    4) zu guter letzt* musst du noch square und multiply im (Z/nZ[X])/(X^r-1) reinbauen.

    (*oder je nach flexibilität deiner implementierung gleich zu anfang, das square und multiply geht bereits bei wesentlich einfacheren strukturen, etwa halbgruppen, wenn ich mich nicht irre)

    Das ist alles recht spaßig... good luck have fun.
     
  6. hawkeye78
    hawkeye78 Neues Mitglied
    Hallo,

    erst einmal vielen Dank für deine Erklärung, was wohl für mich bedeutet ich muss mir die entsprechenden Literatur schnappen und mich erst einmal in das Thema: "was ist ein Polynmomring und wie rechnet man damit" einlesen den bis jetzt ist mir das (zumindestens nicht unter diesen Namen) begegnet.
    Nichsdestotrotz danke ich dir für deine Ausführliche erklärung.
    viele Grüsse
    Dan
     
  7. 0x7F800000
    0x7F800000 Neues Mitglied
    Ist alles halb so wild, allerdings sind die in der mathematik üblichen begriffe der breiten öffentlichkeit irgendwie weitestgehend unbekannt, weil man in der schule dauernd versucht, den armen planlosen schülern jegliche strukturierung und systematik vorzuenthalten, und matheunterricht im totalen chaos untergehen zu lassen^^ (was den meisten auch perfekt gelingt, wenn ich mir manche schüler so anschaue, den ich mal nachhilfe in mathe gegeben hab^^) (-.-)

    Ein "Ring" ist einfach eine Struktur in der du mit "normalen" assoziativ- und distributivgesetzen addieren und multiplizieren kannst, zum beispiel sind ganze zahlen mit der normalen addition und multiplikation ein Ring:

    (2+3)*5=2*5+3*5=10+15=15+10=25

    Oder die rationalen Zahlen, oder reellen... Oder quadratische matrizen (dann wird der ring allerdings nicht kommutativ d.h bei der multiplikation darfst du nicht einfach so die reihenfolge vertauschen). In einem Ring darfst du aber i.Allg. nicht teilen, d.h. es existieren nicht immer "Kehrwerte" (wie bei Z zum beispiel: 1/2 ist der Kehrwert von 2 in Q, aber keine ganze Zahl).

    Oder eben die Mengen der Polynome über irgendwelche dieser Ringe. Die nennt man dann eben "Polynomringe". Mit den kannst du ja auch "ganz normal" rumrechnen, sieht dann in Z[X] etwa so aus:

    (x+2)*(x+5)+3x=x^2+10x+10

    Z/nZ ist der Restklassenring modulo n. Da kannst du auch ganz normal rumrechnen, aber alles was du ausrechnest musst du am ende einfach modulo n nehmen, in Z/7Z etwa:
    2+3=5
    3+3=6
    3+4=0
    2*2=4
    2*5=3
    -1=6
    und so weiter... einfach rest modulo 7 aus dem bereich [0..6] nehmen, und fertig (kannst auch andere representanten nehmen, das ist eigentlich auch egal).

    In so einem Polynomring Z/nZ[X] rumzurechnen geht genauso wie in allen anderen Polynomringen auch: wenn du alles korrekt gekapselt hast, sollte die implementierung vom Polynomring sich gar nicht dafür interessieren, über welchem Ring sie eigentlich rechnet: dem Polynomring reicht es zu wissen, dass er in seinem ring addieren und multiplizieren kann, fertig.

    Polynomdivision ist in einem Polynomring über einem Ring der kein Körper ist, ist schon eher problematisch. Dieses Gebilde was auf deiner folie steht:
    (Z/nZ[x])/(X^r-1)
    ...ergibt meiner meinung nach für n nicht prim nicht unbedingt viel Sinn, weil man in einem Ring (im unterschied zu einem Körper) i.Allg. nicht einfach so teilen kann. In diesem Konkreten Fall macht es aber nichts, weil der Leitkoeffizient bei (X^r-1) gleich 1 ist, und 1 teilt ja alles in einem Ring, daher müsste hier eigentlich nichts schief gehen, bei der Implementierung muss man aber schauen, wie man das vorsichtig umsetzt, ohne das interface der Ringe kaputt zu machen.
     
    Zuletzt bearbeitet: 3. Mai 2009
  8. hawkeye78
    hawkeye78 Neues Mitglied
    Hallo Andrey,

    damit ich das richtig verstehe und morgen bei der Sprechstunde von meiner Professorin nicht allzuviel Blödsinn erzähle ein Ring ist eigentlich so etwas wie ein Körper (mit ein paar einschränkungen...) auf dem ähnliche Rechengesetze definiert sind.
    Was auf meinem Fall bezogen bedeutet ich müßte für den Ausdruck (X+a)^n alle Polynome betrachten? Aber ich befürchte ich habe noch nicht so ganz verstanden was ein Restklassenring ist und wie das in mein Problem hereinspielt. Also angenommen ich habe das jetzt richtig verstanden und ich muss tatsächlich die entsprechenden Polynome betrachten wie was muss ich jetzt durch was in meinem Fall dividieren?
    Viele Grüsse
    Dan
     
  9. 0x7F800000
    0x7F800000 Neues Mitglied
    Ring und Körper unterscheiden sich bei der definition in einem einzigen Punkt: bei Körpern kannst du immer zu jedem element a!=0 ein multiplikatives inverses 1/a finden, bei einem Ring muss es sowas aber nicht geben, man kann da im allgemeinen nicht dividieren. Ein Körper ist einfach nur ein Ring, wo man zu jedem element !=0 einen "Kehrwert" findet, und da darfst du im prinzip so rumrechnen, als ob du mit reellen Zahlen R rumrechnen würdest. (zwar können die Rechner mit R nicht umgehen, und außer den Mathematikern kann kaum ein Mensch kurz und klar sagen, was dieses R eigentlich sein soll, aber irgendwie ist es am beliebtesten)
    Viel mehr steckt da nicht dahinter.

    Welche "alle" Polynome? Du hast doch hier ein ganz konkretes gegeben.

    Wie man das gut definiert ist wieder eine andere geschichte. Aber zum rumrechnen muss man das nicht wirklich wissen. Man rechnet einfach ganz normal mit ganzen zahlen herum, und nimmt alle ergebnisse immer modulo n, das wars. Wenn Heute Dienstag ist=2, welcher Wochentag ist in 1000 Tagen? Montag, weil 1000=-1 mod 7 also 2+1000=2-1=1=Montag mod 7. Für sowas sind halt restklassenringe wie Z/7Z gut...
    das weiß ich auch nicht... Da stand irgendwo "Zp" auf deiner Folie, wozu es da genau gut ist: keine Ahnung, da müsste man sich den Beweis reinziehen.
    welche "entsprechenden polynome" schon wieder, wieso redest du von dem einem Ding in Plural? ???:L
    Was du wo dividieren willst weiß ich grad auch nicht. Meinst du POlynomdivision oder wie?
     
    Zuletzt bearbeitet: 5. Mai 2009
  10. hawkeye78
    hawkeye78 Neues Mitglied
    Hallo,

    vielen Dank für die erneute ausführliche und vor allem auch geduldige Erklärung ich finde es immer wieder toll wenn sich jemand wirklich die Zeit nimmt und die auch noch so (blöden) nervigisten Fragen geduldig beantwortet. :)

    Aber was ich noch sagen wollte, ich spreche von Polynomen (im Plural) weil "a" eine Laufvariable von einer Schleife ist, und ich damit mehrere Polynome bekomme. Aber du hast wohl recht in diesem Punkt von einem Polynom zu sprechen da man das ja Iterationsweise betrachten muss.

    Was Zn und alles weitere betrifft sowie die Frage wie man in logarithmischer Zeit berechnet ergibt sich hoffentlich heute bei der Sprechestunde vom Prof wo ich hin wollte....

    Auf jeden Fall noch einmal vielen Dank für deine Hilfe.
    viele Grüsse
    Dan
     
  11. Hinweis: Du möchtest Java lernen? Vielleicht hilft dir dieses Training hier weiter. Sichere dir hier den Zugriff auf umfangreiches Java-Know How und starte richtig durch!
Die Seite wird geladen...

Bestimmung von (X+a)^n != X^{n mod r} + a - Ähnliche Themen

Bestimmung an welche Methode eine andere Methode ihren Wert weitergeben soll
Bestimmung an welche Methode eine andere Methode ihren Wert weitergeben soll im Forum Java Basics - Anfänger-Themen
Bestimmung der Sleeptime
Bestimmung der Sleeptime im Forum Spiele- und Multimedia-Programmierung
Scala „funktionale Funktion“ zur Bestimmung der Anzahl möglicher „Münzstückelungen“
Scala „funktionale Funktion“ zur Bestimmung der Anzahl möglicher „Münzstückelungen“ im Forum Scriptsprachen
Festplatten-Bestimmung
Festplatten-Bestimmung im Forum Java Basics - Anfänger-Themen
Räumlicher Bogenschnitt zur Positionsbestimmung
Räumlicher Bogenschnitt zur Positionsbestimmung im Forum Mathematik
Status des Themas:
Es sind keine weiteren Antworten möglich.
Thema: Bestimmung von (X+a)^n != X^{n mod r} + a