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:

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)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

@Goswin:
ggT(60,12) funktioniert z.B. nicht.
Und: Warum ein assert? ggT(253, 481) ist doch ebenso definiert.
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

numerix hat geschrieben:ggT(60,12) funktioniert z.B. nicht.
Danke für den Hinweis. Ja, testen will eben gelernt sein! Ich wüsste freilich nicht, was für eine Ausgabe beim ERWEITERTEN euklidschen Algorithmus in so einem Sonderfall erwünscht ist.
numerix hat geschrieben:Und: Warum ein assert? ggT(253, 481) ist doch ebenso definiert.
Am besten erlegen wir zwei Fliegen auf einen Schlag und ersetzen das obige assert durch:

Code: Alles auswählen

assert (a0%b0)>0
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Goswin hat geschrieben:Ich wüsste freilich nicht, was für eine Ausgabe beim ERWEITERTEN euklidschen Algorithmus in so einem Sonderfall erwünscht ist.
Ich habe mich dafür entschieden:

Code: Alles auswählen

e = Euclid(60, 12)
print e.extended
Liefert

Code: Alles auswählen

12 = 1·60-4·12
Goswin hat geschrieben:Am besten erlegen wir zwei Fliegen auf einen Schlag und ersetzen das obige assert durch:

Code: Alles auswählen

assert (a0%b0)>0
Das verstehe ich jetzt nicht. Zum einen kannst du damit nicht zusichern, dass a > b ist (so habe ich dich jedenfalls verstanden; oder ging es um eine andere 2. Fliege?) und zum anderen gibt es dafür keinen Grund.
Warum sollte z.B. ggT(321, 172) erlaubt sein, ggT(172, 321) aber nicht? Vielmehr sollte man in beiden Fällen das gleiche Ergebnis erwarten.
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi Leute:)

Wow, sag ich dazu erstmal, also da brauch ich ein bisschen zum durchlesen.
Merci beaucoup!

also vielen Dank für die Mühe aber kannst du mir vielleicht auch erklären wie du das geschrieben hast??? Also eigentlich möchte ich gar keinen vollständig geschriebenen Algorithmus ich würde gerne meinen weiter schreiben nur ich hab keine Ahnung wie...
also kann mir jemand erklären wie man so etwas anfängt, also halt schritt für schritt das mit mir durchgeht??
Also zuerst wäre da mal meine Frage wie ich da die Schleife begrenze... ich weiß ja nicht wie viele Zeilen mein Gleichungssystem von zwei beliebigen Zahlen im Endeffekt haben wird... und dann weiß ich auch nicht wie man dem Programm sagt, dass es die ehemaligen Restwerte nicht einfach verwerfen soll, sondern bis zum Schluss mitziehen soll... und dann weiß ich auch nicht wie man es verhindert, dass er nicht einfach die ganze Gleichung ausrechnet.. dann würden mir ja die Rest-Werte verloren gehen und ich könnte sie nicht mehr ersetzen lassen....
Kann bitte jemand das einfach mit mir schritt für schritt durchgehen wie man so eine Erweiterung schreibt??

Liebe Grüße
Kalira
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

@numerix:
Ich schließe mit (a0%b0)>0 alle Fälle aus, für welche (1) mein Algorthmus abstürzt, und das sind alles Fälle, für welche (2) ich nicht wusste, welche Ausgabe gewünscht war. Für Ausreißer wie (12,60) funktioniert der Algorithmus; das war nicht geplant, tut aber auch nicht weh. Es geht mir hier nur um Denkanstöße für Kalira; dein Euclid-Modul ist sicher viel ausgefeilter.
Python nervt. (Nicht immer, und natürlich nur mich, niemals andere)
Antworten