kostenloser Webspace werbefrei: lima-city

Euklidischer Algorithmus, RSA

lima-city → Forum → Sonstiges → Schule, Uni und Ausbildung

algorithmus beispiel berechnen brauche dank differenz einfachheit facharbeit idee jemand klasse grundkurs koeffizient letzten zeile positiven zahlen schritt stehen verstehen zahl zweiten zeile zwischenschritt
  1. Autor dieses Themas

    tibel

    tibel hat kostenlosen Webspace.

    12:44, 7.2.2009
    Hi,
    meine Freundin schreibt in Mathe eine Facharbeit über Kryptografie und RSA. (Gymnasium NRW, 12. Klasse Grundkurs)
    Irgendwie hängen wir am euklid. Algorithmus fest. An sich ist das ja soweit klar, nur an einer Stelle kommen wir nicht weiter:
    Formel: 99 = 1 * 78 + 21 <=> 21 = 1 * 99 - 1 * 78 78 = 3 * 21 + 15 <=> 15 = 1 * 78 - 3 * 21 = -3 * 99 + 4 * 78 21 = 1 * 15 + 6 <=> 6 = 1 * 21 - 1 * 15 = 4 * 99 - 5 * 78 15 = 2 * 6 + 3 <=> 3 = 1 * 15 - 2 * 6 = -11 * 99 + 14 * 78
    Wie kommen in der zweiten Zeile die -3 und die 4 zustande. Ich meine, dass das dann in der Differenz 15 ergibt und deswegen da diese Zahlen stehen müssen, ist klar. Nur: wie komme ich bei einer realen Aufgabe darauf (kgV)?

    Danke und Gruß
    Tim

  2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

    lima-city: Gratis werbefreier Webspace für deine eigene Homepage

  3. c*****s

    16:53, 7.2.2009
    Was immer du da geschrieben hast, ich kann keine Ähnlichkeit mit dem Euklidischen Algorithmus erkennen :wink:

    Ich würde sagen, wir bleiben der Einfachheit halber in den positiven Zahlen, dann geht der Euklidische Algorithmus folgendermaßen:

    Formel: \\ 99 = 1\cdot78 + 21 \\ 78 = 3\cdot21 + 15 \\ 21 = 1\cdot15 + 6 \\ 15 = 2\cdot6 + 3 \\ 6 = 2\cdot3

    Beitrag zuletzt geändert: 7.2.2009 17:47:51 von calexus
  4. Autor dieses Themas

    tibel

    tibel hat kostenlosen Webspace.

    17:36, 7.2.2009
    Sorry, meinte natürlich den erweiterten euklidischen Algorithmus. Das Beispiel ist aus Wikipedia.
    Viel einfach gehts leider nicht, brauche den erweiterten euklidischen algorithmus unbedingt.

    Hat soonst noch jemand ne Idee?

    Danke
    Tim

  5. c*****s

    18:07, 7.2.2009
    tibel schrieb: Sorry, meinte natürlich den erweiterten euklidischen Algorithmus. Das Beispiel ist aus Wikipedia.
    Viel einfach gehts leider nicht, brauche den erweiterten euklidischen algorithmus unbedingt.

    Hat soonst noch jemand ne Idee?

    Danke
    Tim
    wenn du nur das kgV berechnen willst, reicht der normale euklidische Algorithmus schon aus.

    kgV(a*b) = a*b/ggT(a,b)

    brauchst du die Bezout-Koeffizienten oder was?

    Formel: \\ 99 = 1\cdot78 + 21 \Leftrightarrow 21 = 1\cdot99 - 78 \\ 78 = 3\cdot21 + 15 \Leftrightarrow 15 = 78 - 3\cdot21 \Leftrightarrow 15 = 78 - 3\cdot(99 - 1\cdot78) = \\ = -3\cdot99 + 4\cdot78

    du setzt einfach für 21 die 99 - 1*78 ein, die du im Schritt vorher berechnet hast und vereinfachst.

    Beitrag zuletzt geändert: 7.2.2009 18:26:57 von calexus
  6. Autor dieses Themas

    tibel

    tibel hat kostenlosen Webspace.

    18:15, 7.2.2009
    Ich meine in deiner letzten Zeile die -3 und die 4. warum stehen da genau diese beiden Zahlen?

  7. c*****s

    18:22, 7.2.2009
    Im Schritt vorher habe ich berechnet Formel: 21 = 99-1\cdot 78 jetzt setze ich das für die 21 in Formel: 15 = 78 - 3\cdot 21 ein. Dann ergibt sich durch ausmultiplizieren und vereinfachen Formel: \\ 15 = 78 - 3\cdot(99-1\cdot 78) = 78 - 3\cdot 99 -(-3\cdot 1)\cdot 78 = 78 -3\cdot 99 + 3\cdot 78 = 4\cdot 78 - 3\cdot 99
    also noch mehr Zwischenschritte gehen nicht :wink:

    Beitrag zuletzt geändert: 7.2.2009 18:26:08 von calexus
  8. Autor dieses Themas

    tibel

    tibel hat kostenlosen Webspace.

    18:35, 7.2.2009
    Ah wunderbar, jetzt habe selbst ich es ^^
    Wie war das noch? Um Rekursion zu verstehen muss man erst Rekursion verstehen? :D

    Danke, das hilft mir einen großen Schritt weiter.

    Gruß
    Tim

  9. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

    lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

lima-city bietet dir kostenlosen und werbefreien Speicherplatz für Deine Homepage. Sofort anmelden und direkt loslegen mit Webspace, PHP, Datenbanken, günstigen Domains und einer tollen Community!

Login zum Webhosting ohne Werbung!

Hast Du schon kostenlosen Webspace oder bist Du auf der Suche nach WordPress-Hosting mit Staging-Funktion und wp-cli? Jetzt günstige Prepaid Domains registrieren!