modulo rechnung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:23 Mi 30.05.2007 | | Autor: | Riley |
Guten Morgen!
könnt ihr mir helfen, wie man z.B. eine solche Gleichung löst:
[mm] x^2 \equiv [/mm] 13 mod [mm] 2^{16} [/mm] + 1
Viele Grüße,
Riley
|
|
| |
|
>
> könnt ihr mir helfen, wie man z.B. eine solche Gleichung
> löst:
>
> [mm]x^2 \equiv[/mm] 13 mod [mm]2^{16}[/mm] + 1
Hallo,
das würde ich so machen:
[mm]x^2 \equiv[/mm] 13 mod [mm]2^{16}[/mm] + 1
<==>
[mm] x^2-1=13 [/mm] mod [mm] 2^{16}
[/mm]
[mm] ==>x^2-1=13 [/mm] mod [mm] 2^{4}
[/mm]
[mm] ==>x^2-1=5 [/mm] mod [mm] 2^{3}
[/mm]
[mm] ==>x^2-1=1 [/mm] mod 4
Und ob das möglich ist, würde ich nachschauen.
x läßt bei Division durch 4 den Rest 0,1,2 oder 3.
[mm] x--x^2--(x^2-1)
[/mm]
0 0 3
1
2
3
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:03 Mi 30.05.2007 | | Autor: | statler |
> >
> > könnt ihr mir helfen, wie man z.B. eine solche Gleichung
> > löst:
> >
> > [mm]x^2 \equiv[/mm] 13 mod [mm]2^{16}[/mm] + 1
>
> Hallo,
>
> das würde ich so machen:
>
> [mm]x^2 \equiv[/mm] 13 mod [mm]2^{16}[/mm] + 1
>
> <==>
>
> [mm]x^2-1=13[/mm] mod [mm]2^{16}[/mm]
Hallo, ich denke, da ist
[mm]x^2 \equiv[/mm] 13 mod ([mm]2^{16}[/mm] + 1)
gemeint.
Gruß von Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:26 Mi 30.05.2007 | | Autor: | Riley |
Hallo,
gute Frage, aber wahrscheinlich hast du Recht, sonst wäre es wohl zu "einfach".
Wie kann man das denn lösen, wenn eine Klammer darum ist?
Viele Grüße,
Riley
|
|
|
| |
|
Hallo,
ein Hinweis, von dem ich mir ziemlich sicher bin, daß er nützlich ist:
[mm] 2^{16}+1 [/mm] ist eine Primzahl, die 5. der fünf bekannten Fermatschen Primzahlen.
Wir haben es also mit der Frage zu tun, ob 13 quadratischer Rest modulo der Primzahl [mm] 2^{16}+1 [/mm] ist.
Vielleicht hilft das Euler-Kriterium weiter?
Für Genaueres müßte ich erst in schlauen Büchern gucken.
Aus dem Stand kann ich das nicht mehr - leider.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:48 Mi 30.05.2007 | | Autor: | statler |
Mahlzeit!
> könnt ihr mir helfen, wie man z.B. eine solche Gleichung
> löst:
>
> [mm]x^2 \equiv[/mm] 13 mod ([mm]2^{16}[/mm] + 1)
Nun, zunächst ist [mm] 2^{16}+1 [/mm] eine Fermatsche Primzahl. Mit dem Quadratischen Reziprozitätsgesetz kann man also mal prüfen, ob es überhaupt Lösungen gibt. Ergebnis der Prüfung: Das tut es!
[mm] 2^{16}+1 \equiv [/mm] 4 [mm] \equiv 2^{2} [/mm] mod 13
Die beiden Lösungen wirklich zu finden, ist oft ein mühsames Geschäft. Letztlich läuft es auf intelligentes Probieren hinaus. Am besten schreibt man sich wohl ein Computer-Programm dafür.
Eben weil das so zeitraubend ist, funktionieren die heutzutage verwendeten Chiffrier-Codes.
Mit dieser wenig hilfreichen Antwort und vielen Grüßen
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:55 Mi 30.05.2007 | | Autor: | Marc |
Hallo zusammen,
> Die beiden Lösungen wirklich zu finden, ist oft ein
> mühsames Geschäft. Leztlich läuft es auf intelligentes
> Probieren hinaus. Am besten schreibt man sich wohl ein
> Computer-Programm dafür.
| 1: | >>> for i in xrange( 1, 2**16+1+1 ):
| | 2: | ... if i*i % ( 2**16+1 ) == 13:
| | 3: | ... print i
| | 4: | ...
| | 5: | 12930
| | 6: | 52607 |
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:15 Mi 30.05.2007 | | Autor: | Riley |
Hallo!
Vielen vielen Dank für eure Antworten, das ist wirklich faszinierend! =)
@Marc: besten Dank für das Programm! aber kannst du mir bitte noch erklären, was die einzelnen Befehle genau bedeuten? Ich kenn leider nur ein bissle Matlab...
Viele Grüße,
Riley
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:28 Mi 30.05.2007 | | Autor: | Riley |
Hallo Marc,
hey das ist cool, habs verstanden und mal in Matlab versucht:
for i=1:(2^(16)+1)
if mod(i*i,(2^(16)+1))==13
p=i;
end
end
p
bekomm aber nur das Ergebnis 52 607, das andere nicht. hast du eine idee woran das liegen könnte? (auch wenn du Matlab nicht kennst ... warum kennst du das eigentlich nicht?)
keine ahnung wie das mit den eingebauten funktionen ist, aber mit der schleife funktioniert es ja :)
Viele Grüße & vielen Dank,
Riley
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:38 Mi 30.05.2007 | | Autor: | Marc |
Hallo Riley!
> hey das ist cool, habs verstanden und mal in Matlab
> versucht:
![[ok]](/images/smileys/ok.gif "[ok]")
> for i=1:(2^(16)+1)
> if mod(i*i,(2^(16)+1))==13
> p=i;
> end
> end
> p
>
> bekomm aber nur das Ergebnis 52 607, das andere nicht. hast
> du eine idee woran das liegen könnte?
Ich vermute mal, 52 607 ist die größere der beiden Zahlen 
Der Grund dafür ist, dass der vorherige Inhalt von p in der if-Anweisung überschrieben wird, falls diese mehrmals zutrifft. So hat p ausserhalb der Schleife nur den letzten zuwegiesenen Wert.
> (auch wenn du Matlab
> nicht kennst ... warum kennst du das eigentlich nicht?)
Ich weiß es nicht, ich hatte bisher noch nicht die Einsicht, dass es lohnen könnte, Matlab zu haben. Als CAS gibt es ja mehrere freie Softwarepakete, die haben mir immer gereicht.
> keine ahnung wie das mit den eingebauten funktionen ist,
> aber mit der schleife funktioniert es ja :)
Wie statler schon schrieb, wird Matlab --wenn es eine solche Funktion hat-- sie sehr ähnliche dieser Schleife umgesetzt haben. Der Vorteil wird nur sein, dass eine eventuell eingebaute Funktion schneller sein wird
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:52 Mi 30.05.2007 | | Autor: | Riley |
Hi Marc,
ah, das ist natürlich ein dummer Fehler, mit dem Befehl fprintf('%d [mm] \n',p) [/mm] funktioniert es dann, habs grad nochmal ausprobiert 
achso ;) stimmt auch wieder.
hm, aber für das ist es so ja schnell genug.
Viele Grüße,
Riley
|
|
|
|
