| Autor |
Beitrag |
    
Emrepb (Emrepb)
Erfahrenes Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 60
Registriert: 10-2003
| | Veröffentlicht am Freitag, den 24. Dezember, 2004 - 15:03: | 
|
Hallo an alle. Habe bald eine Klausur und wir haben nur ein Ansammlung von übungsaufgaben bekommen (Ohne Lösung natürlich). Werde die Aufgaben hier reinlegen und hoffe das Ihr mir dabei helfen könnt! Wäre ein schönes Weihnachtsgeschenk 
Aufgabe1
(Chinesischer Restsatz).
Sei N=12345678901234567890 und M = 345567.
i)Berechne N * M mod 11 und N * M mod 1001 ohne Verwendung eines Computeralgebrasystems.
ii)Berechne N * M mod (1001 * 11) ohne Verwendung eines Computeralgebrasystems.
Aufgabe2 (Chinesischer Restsatz).
Sei N = 39497. Finde alle Lösungen der Gleichung x^2 * 1 mod N.
Hinweis: 39497 = 127 * 311 und 127 und 311 sind Primzahlen.
Aufgabe3 (Pollard-Rho-Methode)
Fülle die folgende Tabelle, um die Zahl N = 3979 zu faktorisieren. Verwende als Startwert
x0 = 6090471 mod N.
__________________________
i | xi | yi | gcd(xi-y1,N)
| | |
Aufgabe4 (Primheit).
Betrachte die Menge M aller sechsstelligen Zahlen, in denen jede der Ziffern 0,1,2,3,4,5 genau einmal vorkommt.
i)Wie viele Primzahlen sind in M enthalten?
ii)Wie viele Quadratzahlen sind in M enthalten?
Aufgabe5 (Primheit)
Bestimme die Anzahl Nullen am Ende von 128! ohne Verwendung eines Computeralgebrasystems.
Aufgabe6 (Miller-Rabin / Carmichael).
i)Führe den Fermat Primzahltest und Miller-Rabin Test für N = 341 und a = 2 aus und gib alle Zwischenergebnisse an. Probiere jeweils zwei
weitere a's.
ii)Beweise den folgenden Satz:
Satz 7.7. Sind für eine natürliche Zahl m>=1 die Zahlen p1 = 6m + 1 ,p2 = 12m+1 und p3 = 18m+1 prim, so ist n = p1*p2*p3 eine Carmichaelzahl.
Aufgabe7(Kettenbrüche).
i)Berechne die Kettenbruchentwicklung von 37/42 und 19/68 und deren vierte Konvergente C3.
ii)Ein endlicher Kettenbruch heißt einfach, falls für 0 <= i <= n gilt a_i Element Z.
Zeige, daß
[a0,a1,...,a_n]=[a0,a1,....,(a_n)-1,1],falls
a_n > 1
und
[a0,a1,...,a_n]=[a0,a1,....,(a_n-1)+1,1],
falls a_n = 1
Aufgabe8(Montgomery)
Sei a = 17 und b = 23. Berechne x = a * b
mod 133 mit der Montgomery-Methode. Wähle hierzu ein geeignetes R
Ich hoffe ihr könnt die meisten Aufgaben lösen. Werde auch jetzt versuche etwas davon zu lösen.
VIELEN DANK IM VORAUS!! |
Emrepb (Emrepb)
Erfahrenes Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 61
Registriert: 10-2003
| | Veröffentlicht am Dienstag, den 28. Dezember, 2004 - 16:46: |
|
kann mir jemdand die aufgaben 2,3,4 lösen ????
Rest habe ich selber gelöst!!
Mfg |
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 1059
Registriert: 05-2002
| | Veröffentlicht am Mittwoch, den 29. Dezember, 2004 - 07:12: |
|
hm,
wo ist bei Aufgabe 2 das "="-Zeichen?
Aufgabe 4:
i)
0+1+2+3+4+5 = 15, durch 3 teilbar; gibt keine
ii)
0+1+2+3+4+5 = 15, durch 3, aber nicht durch 9 teilbar; gibt keine
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
Emrepb (Emrepb)
Erfahrenes Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 62
Registriert: 10-2003
| | Veröffentlicht am Donnerstag, den 30. Dezember, 2004 - 20:25: |
|
Hi, danke erstmal für die Lösung. Die Aufgabe wurde einfach so gestellt wie es oben steht....vielleicht sollte man es gleich 0 setzen (x^2 * 1 mod N=0).
Zu 4) was ich da nicht verstehe ist wie du auf so eine lösung kommst??????
warum addierst du die zahlen ???? |
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 1060
Registriert: 05-2002
| | Veröffentlicht am Donnerstag, den 30. Dezember, 2004 - 20:37: |
|
Na, egal welche Zahl ich nehm, ich weiß auf jeden Fall die Quersumme
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
Emrepb (Emrepb)
Erfahrenes Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 63
Registriert: 10-2003
| | Veröffentlicht am Freitag, den 31. Dezember, 2004 - 14:03: |
|
Das ist eine gute idee
zu aufgabe 2.)
die Aufgabe sollte so lauten:
Aufgabe2 (Chinesischer Restsatz).
Sei N = 39497. Finde alle Lösungen der Gleichung x^2 ist kongurrent 1 mod N.
Hinweis: 39497 = 127 * 311 und 127 und 311 sind Primzahlen. |
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 1061
Registriert: 05-2002
| | Veröffentlicht am Freitag, den 31. Dezember, 2004 - 14:35: |
|
Aufgabe 2:
x^2 == 1 (mod 127 * 311 )
x^2 - 1 == 0 (mod 127 * 311)
(x - 1) * (x + 1) == 0 (mod 127 * 311)
x1 = 1 und x2 = 39496 [=-1] sind offensichtlich
wie man auf die beiden anderen Lsg.
x3 = 9018 und x4 = 30479
kommt ist mir selbst Rätsel;
mit folgendem hab ich die Lsg. bestimmt
#include <stdio.h>
int main( int argc, char* argv[ ] )
{ for ( int i = 1; i < ( 127 * 311 ); i++ )
if ( ( ( i * i ) % ( 127 * 311 ) ) == 1 )
printf( "%d is invers to itself\n", i );
return 0; }
}
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
Emrepb (Emrepb)
Erfahrenes Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 64
Registriert: 10-2003
| | Veröffentlicht am Dienstag, den 04. Januar, 2005 - 21:25: |
|
Danke für die Lösung. aber frage zu Aufgabe 4 nochmal.:
was wäre wenn ich eine Quersumme 17 und 25 hätte ????
wie wäre dann die Lösung für
i)Wie viele Primzahlen sind in M enthalten?
ii)Wie viele Quadratzahlen sind in M enthalten?
Danke! |
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 1070
Registriert: 05-2002
| | Veröffentlicht am Dienstag, den 04. Januar, 2005 - 21:49: |
|
Dann würdest Dir schwer tun es auf die Art zu machen, wobei, schon mal probiert zweimal die selben Zahlen zu addieren und unterschiedliche Summen zu bekommen? 
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
Emrepb (Emrepb)
Erfahrenes Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 65
Registriert: 10-2003
| | Veröffentlicht am Dienstag, den 04. Januar, 2005 - 22:21: |
|
aber was wäre denn ein beispiel wo beide bedingungen erfüllt sind also i) und ii)
??? |
Emrepb (Emrepb)
Erfahrenes Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 66
Registriert: 10-2003
| | Veröffentlicht am Dienstag, den 04. Januar, 2005 - 22:51: |
|
hast du vielleicht eine idee zu 6i)also den Test mit Miller Rabin-Test durchführen ????
Gruß
EmrePB |
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 1072
Registriert: 05-2002
| | Veröffentlicht am Mittwoch, den 05. Januar, 2005 - 21:54: |
|
Da findest was zu (6k+1)(12k+1)(18k+1)
http://mathworld.wolfram.com/CarmichaelNumber.html
Da findest was zum Rabin-Miller-Test
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
