Die Mathe-Redaktion [Home] - Neues auf einen Blick 21.09.2023 23:52 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Modulo
Autor
Universität/Hochschule Modulo
ephi
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.05.2002
Mitteilungen: 116
Wohnort: Berlin
  Themenstart: 2004-05-19

Hallo, ich habe folgendes: kb mod n = m Dabei sind mir b,m und n bekannt. Wie bekomme ich auf eine schnelle Weise k raus ? Gruss, ephi

   Profil
Ehemaliges_Mitglied
  Beitrag No.1, eingetragen 2004-05-19

Moin, Deiner Aufgabe nach suchst Du eine Zahl, die hoch k durch n geteilt den Rest m hat. Beispiel: Angenommen b= 2 n=3 m=2 dann steht da k 2 mod 3 = 2 Dieses gilt für alle Vielfachen von 3, zu denen Du 2 addierst. Also u.a. auch für 5, da sqrt(5)^2 mod 3 = 5 mod 3 = 2 Hilft Dir das?

   Profil
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46882
Wohnort: Dresden
  Beitrag No.2, eingetragen 2004-05-19

Hi, @Joda Sorry, das ist keine richtige Antwort, hier ist nach ganzen Zahlen gefragt. @ephi Das Problem ist, allgemein gesehen, recht schwierig. Gerade darauf beruht die Sicherheit mancher Verschlüsselungsverfahren. Für nicht allzugroße b,m und n muß man eben probieren. Wenn dieses Problem allerdings sehr viele Male gelöst werden muß, wobei b und n immer gleich sind und nur m sich ändert, dann kann man eine sogenannte "Tafel diskreter Logarithmen" aufstellen, aus der man dann das Ergebnis b abliest. Aber um zu so einer Tafel zu kommen, muß man auch alle b einzeln durchrechnen, oder weiß jemand was Besseres (das Square & Multiply-Verfahren vielleicht?). Gruß Buri [ Nachricht wurde editiert von Buri am 2004-05-19 11:40 ]

   Profil
JohnDoe
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.07.2003
Mitteilungen: 2146
Wohnort: Tirol
  Beitrag No.3, eingetragen 2004-05-19

Hi ephi, sind für b,m,n irgend welche Einschränkungen bekannt/vorausgesetzt? Unter gewissen Voraussetzungen kann nämlich der Aufwand auf die Bestimmung der Ordnung von m mod n reduziert werden. Für ggT(m,n)=1 , c=ord_n(m) und ggT(b,c)=1 sei d=-c^(-1)(mod b) Dann ist k=m^((c*d+1)/b)(mod n) eine Lösung von k^b=m(mod n) Allerdings ist keine dieser Voraussetzungen notwendig für die Existenz einer Lösung, wie man an folgenden Beispielen sieht: k^2=3(mod 6) mit eindeutiger Lösung k=3 k^270=81(mod 697) mit 20 Lösungen Gruß, Heinz

   Profil
ephi hat die Antworten auf ihre/seine Frage gesehen.

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-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]