Verfasst am: 23.07.2015, 21:50
Titel: erweiterter euklidischer Algorithmus in Z/pZ[x]
Hallo alle zusammen,
ich stelle hier zum ersten Mal eine Frage und hoffe sehr Hilfe zu finden. Ich bin noch ein Einsteiger und habe versucht mit Hilfe von Matlab den erweiterten euklidischen Algorithmus in Z/pZ[x] (p=Primzahl)zu schreiben. Aber es klappt nicht. Ich glaube es liegt an der zweiten while-Schleife, die nicht aufhört. Kann mir jemand helfen, wo der Fehler liegen könnte? Ich hoffe nicht, dass das alles kompleter Blödsinn ist, was ich geschrieben habe. Ich bin wie gesagt Anfänger.
Oder gibt es in Matlab eigentlich irgendeinen Befehl mit dem ich den beschriebenen erweiterten euklidischen Algorithmus in Z/pZ[x] durchführen kann?
P.S.: grad() und Leitkoeffizient() die in meinem Code vorkommen sind übrigens Funktionen, die ich selber geschrieben habe und die wohl auch funktionieren.
Danke schon mal ,
Gruß Bud Spencer
Code:
%%%ereiterter euklidischer Algorithmus in Z/pZ[X] für eine Primzahl p.
%%%EINGABE: Primzahl p und zwei Polynome aus Z/pZ[X](Die eingegebenen Vektoren müssen
%%%beide gleich lang sein: eventuell links mit Nullen auffüllen.)
%%%Ausgabe:Polynome s,t,ggt aus Z/pZ[X] mit ggt(a,b)=(X^N-1)*s+f*t
TPversch=zeros(1,Laenge);
QUOfalsch=zeros(1,Laenge); %%%ergibt nachher den Quotienten in umgekehrter Reihenfolge
DIVI=a
REST=a
TEIL=b
j=1;
A=cell(1,grad(a)) %%%hier sollen für jede Polynomdivision alle vier Polynome
%%%in jeweils einer Zelle abgespeichert werden.
r=a
while(isequal(mod(r,p), zeros(1,Laenge))==0)
%%% POLYNOMDIVISION ANFANG
%%%while Schleife läuft solange grad(r)>=GradB
r=a
while grad(r)>=grad(TEIL) [ggt,s,t]=eEuklid(p,Leitkoeffizient(REST))
Inverse=mod(t,p)
QZahl=mod(Leitkoeffizient(r)*Inverse,p)
QUOfalsch((grad(r)-grad(TEIL))+1)=QZahl %%%QZahl wird an die richtige Position gesetzt; QUOfalsch ergibt nachher umgedreht den richtigen Quotienten
%%%Teilerpolynom verschoben wir jetzt mit for Schleife gebildet
for i= 1:1:(Laenge-(grad(r)-grad(TEIL)))
TPversch(i)=b(i+(grad(r)-grad(TEIL)));
end %%%for
r=mod((r- QZahl*TPversch),p);
TPversch=zeros(1,Laenge);
REST=r
QUOTIENT=mod(fliplr(QUOfalsch),p)
A{1,j}=[DIVI;TEIL;QUOTIENT;REST]; %%%für jede Polynomdivision werden die vier Polynome der daraus resultierenden Gleichung dem j-ten Cell-Array abgelegt
j=j+1 %%%Danach wird j um Eins erhöht, so dass das nächste Cell-Array belegt werden kann
DIVI=TEIL
TEIL=REST
end %%%while
%%%ENDE POLYNOMDIVISION
end
ggt=A{1,i-2}(4,:)
t=zeros(1,Laenge);
t(Laenge)=1; %%%Startwert für t aus ggt=as*bt ist :[0...01]
s=zeros(1,Laenge);%%%Startwert für s aus ggt=as*bt ist ein Vektor nur aus Nullen
for j=(i-2):-1:1
platz=t;
AL=conv(A{1,j}(3,:),t) %%%Abzug Lang, das ist schon das Produkt aus qt
AK=zeros(1,Laenge); %%%Abzug Kurz
for k=0:1:(Laenge-1)
AK(Laenge-k)=AL(2*Laenge-(k+1)) end;
end
t=mod(s-AK,p)
s=mod(platz,p)
Diese isequal()==0-Abfrage finde ich eigenartig.
Soll der solange laufen, wie mod(r,p) überall Null ist, oder nicht?
Sonst Breakpoints setzten und Variablen nachverfolgen.
_________________
Ich hasse es wenn die Leute Fragen stellen, man dann versucht sich Mühe zu geben, und diejenigen ihren Thread nie wieder besuchen...
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS