Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

CRS, Prim, Carmichael...Brauche dring...

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Zahlentheorie » CRS, Prim, Carmichael...Brauche dringend Hilfe! Prüfung in Zwei wochen! « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 60
Registriert: 10-2003
Veröffentlicht am Freitag, den 24. Dezember, 2004 - 15:03:   Beitrag drucken

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!!
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 61
Registriert: 10-2003
Veröffentlicht am Dienstag, den 28. Dezember, 2004 - 16:46:   Beitrag drucken

kann mir jemdand die aufgaben 2,3,4 lösen ????
Rest habe ich selber gelöst!!
Mfg
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 1059
Registriert: 05-2002
Veröffentlicht am Mittwoch, den 29. Dezember, 2004 - 07:12:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 62
Registriert: 10-2003
Veröffentlicht am Donnerstag, den 30. Dezember, 2004 - 20:25:   Beitrag drucken

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 ????
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 1060
Registriert: 05-2002
Veröffentlicht am Donnerstag, den 30. Dezember, 2004 - 20:37:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 63
Registriert: 10-2003
Veröffentlicht am Freitag, den 31. Dezember, 2004 - 14:03:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 1061
Registriert: 05-2002
Veröffentlicht am Freitag, den 31. Dezember, 2004 - 14:35:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 64
Registriert: 10-2003
Veröffentlicht am Dienstag, den 04. Januar, 2005 - 21:25:   Beitrag drucken

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!
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 1070
Registriert: 05-2002
Veröffentlicht am Dienstag, den 04. Januar, 2005 - 21:49:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 65
Registriert: 10-2003
Veröffentlicht am Dienstag, den 04. Januar, 2005 - 22:21:   Beitrag drucken

aber was wäre denn ein beispiel wo beide bedingungen erfüllt sind also i) und ii)
???
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 66
Registriert: 10-2003
Veröffentlicht am Dienstag, den 04. Januar, 2005 - 22:51:   Beitrag drucken

hast du vielleicht eine idee zu 6i)also den Test mit Miller Rabin-Test durchführen ????

Gruß
EmrePB
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 1072
Registriert: 05-2002
Veröffentlicht am Mittwoch, den 05. Januar, 2005 - 21:54:   Beitrag drucken

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*

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page