Die Mathe-Redaktion - 10.12.2018 14:37 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 758 Gäste und 19 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Fleißner-Verschlüsselung
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Fleißner-Verschlüsselung
OlafMussler
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.03.2007
Mitteilungen: 83
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2013-05-30


Hallo,
ich beschäftige mich in der Schule gerade mit dem Thema Verschlüsselung. Als besondere Form behandeln wir die sogenannten "Fleißner-Schablonen". Hierbei wird ein quadratisches Raster zum Verschlüsseln genutzt, das aus nxn Feldern besteht, wovon ein Viertel der Felder ausgeschnitten sind.
Zum Verschlüsseln wird nun der Klartext in die Lücken geschrieben, dann die Schablone um 90° gedreht, dann der nächste Teil des Klartextes geschrieben, und dann noch zweimal gedreht und geschrieben.
Natürlich müssen die Lücken bei der Schablone so gewählt werden, dass beim Drehen eine Lücke niemals auf ein Feld zweimal trifft.
Dies kann man beim Erstellen der Schablone zum Beispiel dadurch erreichen, dass man eine Feld als Lücke wählt und danach alle Felder markiert, die beim Drehen dieser Lücke vorkommen. Diese schließt man als weitere Lücken also aus. Dann wählt man die nächste Lücke und verfährt genauso...
In Wikipedia wird dieses Verfahren (Fleißner-Schablone) ausführlich erklärt.
Nun endlich zu meiner Frage:
Mich interessiert die Anzahl der möglichen Schablonen, also die Anzahl der möglichen Schlüssel.
Mein bisheriger Ansatz: (am Beispiel einer 6x6-Schablone)
Für die erste Lücke habe ich 36 Möglichkeiten. Für die nächste nur noch 32, da durch das Drehen der ersten Lücke 4 Felder wegfallen.
Entsprechend für die nächsten Lücken: 28, 24, 20, 16, 12, 8, 4.
Nun ist es natürlich egal in welcher Reihenfolge die Lücken gewählt wurden, daher teile ich durch die Anzahl der möglichen Permutationen, also durch 9!.
Somit komme ich auf:
Anzahl = fed-Code einblenden
fed-Code einblenden
Dies kann man noch etwas vereinfachen, indem man jede der 9 Faktoren als Produkt mit dem Faktor 4 schreibt:
Anzahl = fed-Code einblenden
fed-Code einblenden
Anzahl = fed-Code einblenden
fed-Code einblenden
Anzahl = 262144

Soweit so gut.
Auf Wikipedia (und auch auf anderen Seiten) finde ich aber eine andere Rechnung, die ich nicht nachvollziehen kann.
Dort kommt man auf die Anzahl 181440

Versteht das jemand?
Kann mir jemand deren Rechnung erklären oder kann mir jemand den Fehler in meiner Rechnung erklären?

Vielen Dank schon mal!

[ Nachricht wurde editiert von OlafMussler am 30.05.2013 18:10:32 ]



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4517
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2013-05-30


Hallo Olaf,

sehr interessant! Ich verstehe nämlich die Rechnung auf Wikipedia ebenfalls nicht. Auf welcher anderen Seite hast du das Ergebnis gefunden? Google liefert mir nämlich erst mal keine weitere Quelle.

Dein Ergebnis könnte man noch durch 4 teilen, wenn man Schablonen, die durch Drehen auseinander hervorgehen, als gleich betrachtet.

Außerdem müsste man wohl noch ein paar Möglichkeiten abziehen. Z. B. darf folgendes nicht auftreten:

XXXXX
XOOOX
XOXOX
XOOOX
XXXXX

"O" steht hier für ein ausgeschnittenes Feld.



  Profil  Quote  Link auf diesen Beitrag Link
OlafMussler
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.03.2007
Mitteilungen: 83
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2013-05-30


Auf Wikipedia (Fleißner Schablone) findet man unten folgenden Link:
projects.404-net.de/fleissner/
Dort findet man einen "Schablonen-Generator". Dieser liefert auch zu jeder Schablonengröße die Anzahl an Schablonen, die es in dieser Größe angeblich gibt. Das Ergebnis deckt sich bei einer Größe von 6x6 mit Wikipedia. Leider aber nicht mit meiner Rechnung ...

Übrigens denke ich nicht, dass man das Ergebnis unbedingt durch 4 teilen muss, denn natürlich kann man 4 Schablonen durch Drehen aufeinander abbilden, aber das Verschlüsselungsergebnis hängt davon ab, welche Seite der Schablone zu Beginn "oben" ist. Somit kann man diese 4 Schablonen durchaus als verschieden betrachten. Aber darüber könnte man durchaus streiten.

Übrigens: Eine 5x5-Schablone, wie in deinem Beispiel, darf es eigentlich nicht geben, da dann das mittlere Feld immer auf sich selbst gedreht würde. Daher muss die Zahl n (bei einer nxn-Schablone) immer gerade sein.
Ich denke, dass ich in meiner Rechnung bereits die Möglichkeiten berücksichtigt habe, bei denen eine Lücke auf ein Feld gedreht wird, auf das bereits eine andere Lücke gedreht wurde.
(Dazu habe ich mir ja überlegt, dass ich bei der Wahl einer Lücke sofort die anderen drei Felder, auf die diese Lücke gedreht wird, markiere und somit für die Wahl der folgenden Lücken auslasse. Daher gibt es ja für die erste Lücke 36 Möglichkeiten (bei 6x6) und für die nächste nur noch 32 ...)

Wirklich verzwickt ...



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4517
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2013-05-31


Hi Olaf,

du hast Recht, ob durch 4 geteilt wird oder nicht, ist Ansichtssache.

Vielleicht sollte man mal Stefan Kalscheuer fragen, wie er auf die Zahl kommt  confused

Angeblich existieren 576 mögliche Schablonen der Größe 4x4. Keine Ahnung, wie er darauf kommt. Nach deiner (unserer) Rechnung müssten es 4^4 = 256 sein.

Was ich mit der verbotenen 5x5-Matrix meinte, betrifft eher größere Schablonen, und tritt bei 6x6 wohl nicht auf. Es sollte auch nicht eine 5x5-Matrix sein, sondern ein nicht zulässiger Teil einer größeren nxn-Matrix darstellen. Ich meinte, wenn man die Os wegschneidet, dass dann das X in der Mitte in der Luft hängt. Vergiss es vorerst!

Grüße
StrgAltEntf

[ Nachricht wurde editiert von StrgAltEntf am 31.05.2013 00:41:41 ]



  Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.10.2012
Mitteilungen: 826
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2013-05-31


Hallo OlafMussler und StrAltEntf,

schaut mal  hier auf den Seiten 63 bis 65:
     Schablone 4x4 liefert 256 Möglichkeiten,
     Schablone 6x6 liefert 262144 Möglichkeiten,
Die Herleitung unterscheidet sich ein wenig, aber die Ergebnisse stimmen mit Euren überein.

Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
OlafMussler
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.03.2007
Mitteilungen: 83
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2013-05-31


Danke für den Link.
Da bin ich aber froh, dass ich nicht der einzige bin, der so rechnet ;-)

Wie es scheint liege ich also mit der Anzahl doch richtig.

Falls doch jemand einen Fehler in meiner Rechnung findet, dann schreibt dies bitte! Es wundert mich ehrlich gesagt, dass auf Wikipedia dieser Fehler nach langer Zeit noch immer steht ...

Grüße
Olaf.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4517
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2013-05-31


Hi,

ich glaube, ich bin jetzt dahinter gestiegen, wie der Wikipediaartikel gemeint ist. Siehe Bild 1 bis 4. (Erläuterung weiter unten.)
Beispiel

Im Artikel heißt es:
"Erzeugen lassen sich die Schablonen, indem man beispielsweise ein Viertel der Matrix mit den Werten 1 bis 4 füllt ..."

Dieses ist wie folgt zu interpretieren, siehe Bild 1: Man wählt hier das linke obere Viertel und trägt dort Zahlen von 1 bis 4 ein. (Hierfür gibt es übrigens 4^9 Möglichkeiten, also deine Lösung!)

"... und diese unter zyklischer Verschiebung der Ziffern dreimal um 90° in den jeweils nächsten Quadranten dreht."

Siehe Bild 2 und 3. Bei Bild 2 wird das linke obere Viertel um 90° gedreht und alle Werte werden um 1 modulo 4 erhöht. Aus 1 wird also 2, aus 2 wird 3 aus 3 wird 4 und aus 4 wird 1.

Dieses Viertel, was jetzt rechts oben steht, wird dann weitere zwei Mal gedreht und die Werte werden modulo 4 erhöht. Dies gibt dann schließlich Bild 3.

"Ausgeschnitten werden alle Felder mit der gleichen Ziffer, z.B. der 1."

Dies ist in Bild 4 dargestellt. Die weißen Felder sind ausgeschnitten, und die grauen bleiben stehen.

Auf diese Weise lassen sich tatsächlich alle möglichen (4^9 viele) Schablonen erzeugen! Jetzt kommt im Artikel aber eine weitere Einschränkung:

"Geht man von gleichmäßiger Verteilung über alle vier Quadranten aus ..."

Dies soll besagen, dass die Ziffern in Bild 1 nicht beliebig gewählt werden sollen, sondern dass jede Ziffer mindestens zwei Mal vorkommen soll. Das mag durchaus sinnvoll sein. Die folgende Formel im Artikel ist jedoch falsch!

"ergibt sich die Anzahl der so möglichen Schablonen durch folgende Rechnung: <math>n = 4 \cdot \binom 9 3 \cdot 3 \cdot \binom 6 2 \cdot 2 \cdot \binom 4 2 \cdot 1 \cdot \binom 2 2</math>"

Hier müsste es korrekt heißen: <math>n = 4 \cdot \binom 9 3 \cdot \binom 6 2 \cdot \binom 4 2</math>

Der Wert im Artikel ist also um den Faktor 6 zu groß.

(Mein) Fazit: Es ist äußerst undurchsichtig, was uns der Autor sagen will, und zudem ist die Formel falsch.

Grüße
StrgAltEntf

[ Nachricht wurde editiert von StrgAltEntf am 31.05.2013 22:29:06 ]



  Profil  Quote  Link auf diesen Beitrag Link
OlafMussler
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.03.2007
Mitteilungen: 83
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2013-06-01


Danke für die Erläuterung!
Also, dass man modulo rechnen muss, ging für mich nicht aus dem Wiki-Artikel hervor. Dann macht das natürlich Sinn.
Aber in der Tat muss deren Formel falsch sein, denn wenn man eine Einschränkung vornimmt, müssen es ja weniger Schablonen sein, als nach meiner Rechnung. Dies war aber leider nicht der Fall, was mich ja so verwirrt hat.

Nochmals vielen Dank für die Hilfe!

Grüße
Olaf.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4517
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2013-06-01


Habe auf der Diskussionsseite des Artikels mal auf diesen Thread verwiesen. Eine Mail-Adresse vom Autor dieses Beitrags konnte ich nicht finden.

Grüße
StrgAltEntf

Edit: Mittlerweile habe ich den Autor doch auffindig gemacht und ihm eine Anfrage gestellt. Habe auch schon eine Antwort erhalten. Er wird sich demnächst noch mal der Sache annehmen.

[ Nachricht wurde editiert von StrgAltEntf am 02.06.2013 18:22:40 ]



  Profil  Quote  Link auf diesen Beitrag Link
OlafMussler
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.03.2007
Mitteilungen: 83
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2013-06-02


Danke für deine Bemühungen!



  Profil  Quote  Link auf diesen Beitrag Link
stkl
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 03.07.2015
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2015-07-03


Hallo zusammen,

lange ist es her, aber ich bin gerade noch einmal über mein Projekt gestolpert. Ich bin der Autor des oben verlinkten Generators und habe auch die Zeilen auf Wikipedia "verbrochen".

Ist seitdem etwas in Vergessenheit geraten, aber irgendwie war ich mir da auch relativ sicher, dass meine Variante stimmmte... Die Erklärungen haben sicher Verbesserungspotential, war halt irgendwie ein Schnellschuss am Nachmittag. Wie dem auch sei, hier meine Ausarbeitungen.


Problem ohne Berücksichtigung von Gleichmäßigkeit (selbst das Beispiel ist schon nicht gleichmäßig:
Verteile <math>i</math> Felder auf <math>k</math> Ziffern, wobei jede Ziffer mindestens einem Feld zugeordnet ist.

Daraus ergibt sich für die Anzahl der Möglichkeiten:
<math>n = k! \cdot S_{i,k}</math> (mit <math>S_{i,k}}</math> Stirling-Zahl zweiter Art)

Im klassischen Beispiel mit 4 Ziffern auf 9 Felder entsprechend <math>n = 4! \cdot S_{9,4} = 186480</math>


Wenn wir die Gleichmäßigkeit voraussetzen (schließt einige "ungünstige" Fälle aus und macht es programmatisch recht einfach), sollte es meine ursprüngliche Formel mit Faktor <math>4!</math> sein:
<math>n = 4! \cdot \binom 9 3 \cdot \binom 6 2 \cdot \binom 4 2 \cdot \binom 2 2 </math>

Der Binomial-Teil sollte klar sein. Erste Ziffer auf 3 von 9 Felder Verteilen, zweite auf 2 von 6, usw.

Warum 4! und nicht 4?
Es geht um die Möglichkeiten, die Ziffern 1-4 auf "erste Ziffer", "zweite Ziffer", etc. zu verteilen, sprich die Anzahl der Permutationen der Menge <math>\{1,2,3,4\}</math>, welche gerade <math>4!</math> ist.



Schon interessant, wie ein eigentlich garnicht so kompliziert aussehendes Problem einem Kopfzerbrechen bereiten kann. Ich hoffe die Hitze hat mich nicht zu sehr beeinflusst und dass es damit geklärt wäre. Habe sowas auch nur mal vor einiger Zeit am Rande gelernt, ist auch eher nicht mein Lieblingsthema ;)

Gruß,
Stefan



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4517
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2015-07-04


Hallo stkl,

willkommen auf dem Matheplaneten! Dieses Thema ist schon längst von mir in Vergessenheit geraten. Danke fürs Auffrischen smile

2015-07-03 20:23 - stkl in Beitrag No. 10 schreibt:
Warum 4! und nicht 4?
Es geht um die Möglichkeiten, die Ziffern 1-4 auf "erste Ziffer", "zweite Ziffer", etc. zu verteilen, sprich die Anzahl der Permutationen der Menge <math>\{1,2,3,4\}</math>, welche gerade <math>4!</math> ist.

Du zählst hierbei aber jede Möglichkeit mehrfach - um genau zu sein: 6-fach.

Für die Ziffer, die drei Mal platziert werden soll, gibt es vier Auswahlmöglichkeiten und <math>9\choose3</math> Platzierungen. Das ist richtig.

Alle anderen Ziffern sollen zwei Mal platziert werden. Nehmen wir oBdA an, dass die anderen Ziffern 2, 3 und 4 sind. Für die 2 gibt es dann <math>6\choose2</math> Platzierungen und für die 3 noch <math>4\choose2</math>. Die restlichen beiden Plätze gehen an die 4.

Das darf jetzt aber nicht mit 3! multipliziert werden. Wieso auch?

Viele Grüße
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
stkl
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 03.07.2015
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2015-07-04


OK, mir scheint gestern die Hitze nicht bekommen zu sein, jetzt ist die Erläuterung klar... Faktor 6 zu groß.

Klar, es geht ja auch nur um eine Startkonfiguration, 2-4 sind entsprechend nicht unterscheidbar.

Oder anders formuliert, man verteilt sie beliebig und wählt eine der 4 Ziffern zum ausschneiden aus So wird es bei meinem Tool auch programmatisch gemacht, 1-4 in fixer Reihenfolge verteilt und danach zufällig eine wählen, die weiß wird... Hätte mir an dem Punkt eigentlich schon klar sein müssen wink

Danke für die Aufklärung.


Hat sich aber auch keiner in den 2 Jahren getraut, mal den Artikel zu korrigieren wink



  Profil  Quote  Link auf diesen Beitrag Link
OlafMussler hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]