Erweiterter euklidischer Algorithmus

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

numerix hat geschrieben:Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ...
Kalira wird es schon schaffen, die Ausgabe nach ihren Vorgaben zu verändern. Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend :lol: :

Code: Alles auswählen

(a0, b0) = (481, 253)
(amult_a0, amult_b0) = (0, 1)  #alte Multiplikatoren von a0 und b0
#
(aa,bb) = (a0, b0)
(qq,rr) = divmod(aa,bb)  #aa == qq*bb + rr
(mult_a0, mult_b0) = (1, -qq)  #Multiplikatoren von a0 und b0
#
while rr>0:
  print "%3i = %3i * %3i + %3i   ==>  " %(aa,qq,bb,rr),
  print "%3i = (%4i) * %3i + (%4i) * %3i" %(rr, mult_a0,a0, mult_b0,b0)
  #
  (aa,bb) = (bb,rr)
  (qq,rr) = divmod(aa,bb)
  (nmult_a0, nmult_b0) = (amult_a0-qq*mult_a0, amult_b0-qq*mult_b0)
  #
  (amult_a0, amult_b0) = (mult_a0, mult_b0)
  (mult_a0, mult_b0) = (nmult_a0, nmult_b0)
:mrgreen: Übrigens, was hast du gegen Klammern? Mir wurde gesagt, Python sei eine so kuhle Sprache, weil man fast überall Klammern setzen kann :mrgreen:
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Wer hat dir das denn erzählt? Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Goswin hat geschrieben:
numerix hat geschrieben:Nur dass die Ausgabe nicht so ist, wie gewünscht und dass dein Code nur bei ausgewählten Werten funktioniert ...
Kalira wird es schon schaffen, die Ausgabe nach ihren Vorgaben zu verändern.
Da bin ich ziemlich sicher, dass sie das nicht schaffen wird. :? (Versuch du es doch mal ... ). Wenn ich es richtig aufgenommen habe, dann sollte die Darstellung wohl so aussehen, wie man es z.B. in der Wikipedia findet. Das sähe dann z.B. so aus:

Code: Alles auswählen

1 = 1·25-8·3
  = 1·25-8·(228-9·25) = 73·25-8·228
  = 73·(253-1·228)-8·228 = 73·253-81·228
  = 73·253-81·(481-1·253) = 154·253-81·481
Mit ein bisschen Verändern ist das aber nicht getan. Der Algorithmus muss anders angelegt werden, um das zu erreichen.
Goswin hat geschrieben:Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend :lol: :
Diese Art von Spannung erschließt sich mir jedenfalls nicht.
Im übrigen funktioniert dein Code für a==b immer noch nicht ... :)
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

derdon hat geschrieben:Und warum benutzt du keine Klammern in Zeile 8, das wäre doch sowas von cool.
OK, ich versuche einmal ernstlich, meinen Klammernstil zu erklären, falls euch so etwas wirklich interessieren sollte:
(1) Für MICH hat das Komma (natursprachlich bedingt) eine gaaanz niedrige Bindepräzedenz; wenn also eng zusammengehörende Ausdrücke in Python durch Kommas getrennt werden (müssen), dann setze ich sie immer in Klammern; in Deutschaufsätzen würde ich das Gleiche tun. Also (a,b)=(c,d) statt a,b=c,d.
(2) Außerdem setze ich Klammern, wo sie in einem normalen Mathematikbuch auch stehen würden, also x=a*(-b) anstelle von x=a*-b, und x=(a/b)/c anstelle von x=a/b/c.
Leonidas hat geschrieben:Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.
Das hat wohl eher mit Python_3.x zu tun, und ich gebe zu dass ich das noch nicht installiert habe. Könnte man im Code-Tag dieses Forums nicht vielleicht zwischen code=py2 und code=py3 unterscheiden?
Python nervt. (Nicht immer, und natürlich nur mich, niemals andere)
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

Goswin hat geschrieben:Und Flüchtichkeitsfehler im Code werden doch noch erlaubt sein, das macht die Sache so richtig spannend :lol: :
numerix hat geschrieben:Diese Art von Spannung erschließt sich mir jedenfalls nicht.
Kalira hat geschrieben:Ich schreibe grade eine Facharbeit in Mathe.
Der Fehler war von mathematischer Art und nicht von programmiertechnischer Art.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Goswin hat geschrieben:
Leonidas hat geschrieben:Und in 9 und 10 könnte man sicher noch das eine oder andere Klammerpaar reinsetzen.
Das hat wohl eher mit Python_3.x zu tun, und ich gebe zu dass ich das noch nicht installiert habe.
Nein, ``print("abc")`` funktionier auch in Python 2.x und hat immerhin schon ein weiteres Klammerpaar.

Generell geht das öfter dass man hinter Keywords Klammern setzen kann. Insbesondere wenn die Leute von Curly-Brace Sprachen kommen sieht man oft ``if (...)`` oder ``while (...)`` etc. was zwar nicht die bevorzugte Art ist, aber gültige Python-Syntax ist.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Python ist aber weder natürliche Sprache, noch ein Mathematikbuch ;-) Ich finde die überflüssigen Klammern zwar nur wenig störend, aber sie tragen auch nicht unbedingt etwas zur Verständlichkeit bei. Da es üblich ist keine Klammern zu setzen, wo diese nicht notwendig sind, muss man sich auch nicht dagegen stellen.
Das Leben ist wie ein Tennisball.
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi :wink:

Da bin ich wieder!
Also ich habs jetzt mal ein bisschen.. naja "schöner" geschrieben und mir auch grade noch ein weiteres Handbook zu Python runtergeladen..
...also ich frag auch mal grade bei meiner Lehrerin nach ob die wirklich eine lesbare Darstellung des Rechenweges haben will.. wenn nicht, wie kann ich das dann einfügen?? Also wie schreibt man überhaupt die Erweiterung des euklidischen Algorithmus?? Kann mir da bitte jemand ein Beispiel schicken?

So sieht jetzt das neuste aus:

Code: Alles auswählen

a = 493
b = 403
c = a%b
modul = []
vielfach = []
rest = []
multi = [] 
while c > 0:
    print (a, "=", a//b, "*", b, "+", c)
    modul.append(a)
    vielfach.append(b)
    multi.append(a//b)
    rest.append(c)
    a = b
    b = c
    c = a%b
    if a%b == 0:
        break
    
print ("--------------------------------------------------------------------")

rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()

i = 0
while len(rest) > i:
        print (rest[i], "=", modul[i], "-", multi[i], "*", vielfach[i])
        i = i + 1

print ("--------------------------------------------------------------------")
ich weiß einfach nicht wie ich dem jetzt sage, dass er wiederholt Terme für den Rest einsetzen soll.... :?:


Liebe Grüße
Kalira
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Hallo Kalira,
das einzige, was ich Dir im Moment anbieten kann,
ist das hier:
http://paste.pocoo.org/show/115129/
Es hat zwar, soweit ich das verstanden habe,
nicht ganz die von Dir gewünschte Darstellungsform,
aber vielleicht hilft's trotzdem.
(Ist nach dem 1. Algorithmus aus Wikipedia)

:wink:
yipyip
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Kalira hat geschrieben:...also ich frag auch mal grade bei meiner Lehrerin nach ob die wirklich eine lesbare Darstellung des Rechenweges haben will.. wenn nicht, wie kann ich das dann einfügen?? Also wie schreibt man überhaupt die Erweiterung des euklidischen Algorithmus?? Kann mir da bitte jemand ein Beispiel schicken?
Es ist ja nicht so, dass das nicht ginge, aber so, dass es für jemanden, der - nach eigener Aussage - sich mal eben ohne vorherige Erfahrung mit Programmierung im Allgemeinen das Programmieren in Python selbst beigebracht hat - eigentlich eine unlösbare Aufgabe ist.

Was ich nicht verstehe: Wer ist denn auf die Idee gekommen, dass du so etwas machen sollst? War das eine Vorgabe der Lehrerin oder deine eigene Idee? Wenn es die Vorgabe der Lehrerin war, kann das IMHO nur heißen, dass sie von Programmierung nichts versteht, denn sonst hätte sie erkennen müssen, das dieser Teil der Facharbeit für jemanden, der keine Programmierkenntnisse hat, aus eigener Kraft nicht mal eben zu schaffen ist.

Mögliche "Lösungen" wären: Ganz auf diesen Teil der Facharbeit zu verzichten oder aber eine fertige Lösung eines Drittanbieters zu verwenden und das dann aber auch entsprechend auszuweisen. Ob das sinnvoll ist, hängt natürlich vom Thema der Facharbeit ab. Wenn das eigene Erstellen eines Programms integraler Bestandteil des Themas ist, geht es natürlich nicht; geht es im Wesentlichen um den mathematischen Anteil und dient nur der Veranschaulichung, wäre das etwas anderes. Das sollte man ggf. mit der Lehrerin besprechen.

Deine konkrete Frage
ich weiß einfach nicht wie ich dem jetzt sage, dass er wiederholt Terme für den Rest einsetzen soll..
kratzt eigentlich nur an der Oberfläche. Da steckt noch einiges mehr dahinter ...

[Falls die "Drittanbieter"-Lösung in Frage käme, würde ich dir meinen Code evtl. zur Verfügung stellen. Den würdest du zwar ganz überwiegend nicht verstehen, aber du könntest die gewünschte Ausgabe damit erzeugen. Für dein Beispiel:]

Code: Alles auswählen

e = Euclid(481,253)
print e.steps
print e.extended
Liefert als Ausgabe:

Code: Alles auswählen

481 = 1·253+228
253 = 1·228+25
228 = 9·25+3
 25 = 8·3+1
  3 = 3·1+0

1 = 1·25-8·3
  = 1·25-8·(228-9·25) = 73·25-8·228
  = 73·(253-1·228)-8·228 = 73·253-81·228
  = 73·253-81·(481-1·253) = 154·253-81·481
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

yipyip hat geschrieben:Hallo Kalira,
das einzige, was ich Dir im Moment anbieten kann,
ist das hier:
http://paste.pocoo.org/show/115129/
Es hat zwar, soweit ich das verstanden habe,
nicht ganz die von Dir gewünschte Darstellungsform,
aber vielleicht hilft's trotzdem.
(Ist nach dem 1. Algorithmus aus Wikipedia)
Die produzierte Ausgabe ist bei deinem Programm für ggt(a,b) eine andere als für ggt(b,a) ... :wink:
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi!

Also ich hab mir das zum größten Teil selbst eingebrockt :cry:
Ich wollte halt gerne als Thema die RSA-Verschlüsselung machen und dann haben meine Lehrerin und ich erst einmal darüber diskutiert, was ich als eigenen Anteil in die Arbeit einbringen könnte... und dann kam sie auf die tolle Idee Statistiken über die Sicherheit des Verfahrens zu entwerfen.... naja Statistik ist nicht wirklich mein Ding...

Also hab ich einfach mal vorgeschlagen es mit einem Programm zu versuchen... ich hatte ja auch keine Ahnung, dass das so schwierig sein würde... daher heißt mein Thema erst mal "Das RSA-Verschlüsselungsverfahren mit der Anwendung eines selbstentwickelten Computerprogramms"
aber ich hab es geschafft den Sieb des Eratosthenes zu programmieren und einen Zufallsgenerator zu programmieren der auf dieses Sieb zugreift um halt den Verschlüsselungsexponenten e zu bestimmen... nur jetzt ist ja der Entschlüsselungsexponent d das multiplikative inverse Element zu e... und dafür brauch ich halt diesen blöden erweiterten Algorithmus
aber ich warte noch auf eine Antwort meiner Lehrerin und ein bekannter von mir hat mir grade folgendes geschrieben:

Code: Alles auswählen

def extended_gcd(a, b):
    if a%b == 0:
        return 0, 1
    else:
        x, y = extended_gcd(b, a%b)
        return y, x - y * (a // b)

p = 1913
q = 953
e = 1384289
n = (p - 1) * (q - 1)

x, y = extended_gcd(e, n)
d = x % n

print ("n = ", n)
print ("x = ", x)
print ("y = ", y)
print ("d = ", d)
Ich muss das jetzt erst einmal nur verstehen :wink:
und dann noch ein bisschen umändern damit ich es überhaupt in der Arbeit verwenden kann... ich guck dann mal wie ich da mit meiner Lehrerin einen Kompromiss finden kann :wink:

Wenn ich dein Programm bei Python mal ausprobiere krieg ich folgende Fehlermeldung :

Code: Alles auswählen

Traceback (most recent call last):
  File "C:/Python30/von nummerix.py", line 1, in <module>
    e = Euclid(481,253)
NameError: name 'Euclid' is not defined
muss ich davor irgendetwas importieren???

Danke schonmal^^
Liebe Grüße
Kalira
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Die produzierte Ausgabe ist bei deinem Programm für ggt(a,b) eine andere als für ggt(b,a) ... :wink:
Stimmt, das liegt in der Natur meiner Implementation
und habe ich als Problem eigentlich gar nicht beachtet.

:wink:
yipyip
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

yipyip hat geschrieben:
Die produzierte Ausgabe ist bei deinem Programm für ggt(a,b) eine andere als für ggt(b,a) ... :wink:
Stimmt, das liegt in der Natur meiner Implementation
und habe ich als Problem eigentlich gar nicht beachtet.
Naja, ein wirkliches Problem ist da ja auch nicht. Es war mir halt bei meiner eigenen Implementation aufgefallen, die das gleiche Verhalten gezeigt hat (bis ich es abgestellt habe), weil die Darstellung im Falle von a < b (bei ggT(a,b)) sonst etwas verunglückt aussieht.
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Ok, ich hatte nur Wert darauf gelegt, dass die Operanden immer an
der gleichen Stelle stehen, damit man sieht, wie die Gleichungen
auf die Lösung
ggt(a, b) = s*a + t*b
"zuwandern".

:wink:
yipyip
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Kalira hat geschrieben: Wenn ich dein Programm bei Python mal ausprobiere krieg ich folgende Fehlermeldung :

Code: Alles auswählen

Traceback (most recent call last):
  File "C:/Python30/von nummerix.py", line 1, in <module>
    e = Euclid(481,253)
NameError: name 'Euclid' is not defined
muss ich davor irgendetwas importieren???
Naja, du brauchst halt meine Klasse Euclid ... aber den Code dazu habe ich ja absichtlich nicht gepostet, weil ich noch nicht weiß, wie es mit der Geschichte weitergeht ...
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

ich finde die aufgabe deutlich zu anspruchsvoll für eine facharbeit.

kläre mit deiner lehrerin, dass du den aufwand für die version mit ausgabe des rechenweges unterschätzt hast und liefere ihr eine gut dokumentierte (standard-)implementierung des algorithmus.
http://www.kinderpornos.info
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

ok^^

ich hab ihr auch schon geschrieben aber noch keine Antwort daher bin ich mal gespannt :wink:
Froher Maifeiertag an alle :wink:

Bis dann
Kalira
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

Der folgende Code "setzt wiederholt Terme für den Rest ein" ; wie man die Ergebnisse dann ausdruckt, ist wohl Geschmackssache. Die Namensgebung der Variablen ist wahrscheinlich nicht optimal, aber das ist ja leicht zu ändern. Natürlich ist das Ganze auch ohne Klassen und Methoden zu machen, aber dann ist es halt weniger elegant...

Code: Alles auswählen

class Link(object):
  #affin-LINearer AusdrucK :-)
  #
  def __init__(link,fvar,linfun):
    #fvar == sum(mult*key for (key,mult) in linfun.items())
    link.fvar = fvar #int
    link.linfun = linfun #dict
  #
  def __str__(link):
    _linkrep = "%3i =" %link.fvar
    (var,mult) =  link.linfun.items()[0]
    _linkrep += " (%4i) * %3i " %(mult,var)
    for (var,mult) in link.linfun.items()[1:]:
      _linkrep += "+ (%4i) * %3i " %(mult,var)
    return _linkrep
  #
  def frei_von(link,unterlink):
    mult = link.linfun.pop(unterlink.fvar)
    _nlinfun = link.linfun.copy()
    for var in unterlink.linfun:
      _nlinfun.setdefault(var,0)
      _nlinfun[var] += mult * unterlink.linfun[var]
    return Link(link.fvar,_nlinfun)


print
(a0, b0) = (962, 506)
#(a0, b0) = ( 66,  18)
#
(aa,bb) = (int(a0),int(b0))
assert a0>b0>0  #BESSER: assert (a0%b0)>0
rrlinks = []
while True:
  (qq,rr) = divmod(aa,bb)
  if rr==0: break
  print "%3i = %3i * %3i + %3i" %(aa,qq,bb,rr)
  rrlinks.append(Link(rr,{aa:1,bb:-qq}))
  (aa,bb) = (bb,rr)
#
print
rrlinks.reverse()
_rrkum = rrlinks.pop(0)
print "GGN(%i,%i) ="%(a0,b0), _rrkum
#
for rrlink in rrlinks:
  print rrlink, "==>",
  _rrkum = _rrkum.frei_von(rrlink)
  print _rrkum
Zuletzt geändert von Goswin am Dienstag 5. Mai 2009, 09:07, insgesamt 2-mal geändert.
Python nervt. (Nicht immer, und natürlich nur mich, niemals andere)
Antworten