Faktorisierung großer Zahlen < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | [mm] N_1 [/mm] = 12273592092943213182276511177442430412531910236149
53829893295528858325277628193488630991322041481745938
01305041686278551453480033661367979510067412914004717
46371034582025592673361252278763772367396389601506819
33779398030085478890814598986062293299579515495826898
8338557711867690464970192513381388506805266162376723951
[mm] N_2 [/mm] = 41495155688810047421500343386587831477748516603218
903336573756286812251818334512361091943489182655810632
784061938246443183760189998823448366610965660503860072
23291874536016780844841
Faktorisiere [mm] N_1 [/mm] und [mm] N_2!
[/mm]
(Die RSA Moduln sind recht schwach. [mm] N_1 [/mm] hat einen Primfaktor [mm] p_1, [/mm] für den [mm] p_1-1 [/mm] ziemlich "glatt" ist. [mm] N_2=p_2q_2 [/mm] mit Primzahlen [mm] p_2 [/mm] und [mm] q_2, [/mm] die recht nah beisammen liegen. |
der Aufgabenstellung nach soll ich [mm] N_1 [/mm] mit der (p-1) Methode von Pollard faktorisieren und [mm] N_2 [/mm] mit Fermat.
mein problem ist nun, dass ich nicht weiß wie man das macht!
zu [mm] N_1:
[/mm]
Eine Zahl n heißt B-glatt, wenn es keine Primzahlpotenz q>B gibt, die teiler von n ist.
Könnt ihr mir erklären oder zeigen, wie ich diese beiden großen Primzahlen faktorisieren kann?
MfG
Mathegirl
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:08 So 08.01.2012 | | Autor: | Mathegirl |
Kann mir niemand Tipps geben wie ich das machen kann?
Ich kriege das mit so einer großen Zahl nicht hin!
MfG
Mathegirl
|
|
|
| |
|
Das Problem geht schon bei Fermat beim Wurzelziehen los! Wo soll ich so eine große Zahl eingeben? Taschenrechner sowieso nicht und die online Rechner können das auch nicht. Und wenn ich dann die Quadratzahl habe, dann muss die ja auch wieder echt riesig sein!!!
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:09 So 08.01.2012 | | Autor: | felixf |
Moin!
> Das Problem geht schon bei Fermat beim Wurzelziehen los! Wo
> soll ich so eine große Zahl eingeben? Taschenrechner
> sowieso nicht und die online Rechner können das auch
> nicht. Und wenn ich dann die Quadratzahl habe, dann muss
> die ja auch wieder echt riesig sein!!!
Du kannst das z.B. mit dem ![[]](/images/popup.gif) MAGMA-Calculator machen. Gib dort z.B. das hier ein (ohne die Zeilennummern davor):
| 1: | R := RealField(1024);
| | 2: | x := (Ceiling(Sqrt(R!4149515568881004742150034338658783147774851660321890333657375628681225181833451236109194348918265581063278406193824644318376018999882344836661096566050386007223291874536016780844841)) + 2)^2 - 4149515568881004742150034338658783147774851660321890333657375628681225181833451236109194348918265581063278406193824644318376018999882344836661096566050386007223291874536016780844841;
| | 3: | x;
| | 4: | Sqrt(R!x); |
Das rechnet dir [mm] $(\lceil \sqrt{N_2} \rceil [/mm] + [mm] 2)^2 [/mm] - [mm] N_2$ [/mm] aus und die Wurzel davon.
LG Felix
|
|
|
| |
|
Okay danke, vielleicht hilft mir das weiter!
Nur wie kommst du auf die folgende Formel?
[mm](\lceil \sqrt{N_2} \rceil + 2)^2 - N_2[/mm]
Und wenn ich das dann eingebe was du gepostet hast, dann kommt irgendwas komisches raus wenn ich auf submit klicke.
Ich kriege es einfach nicht hin die Zahl zu faktorisieren.
Ich habe eben einen online Rechner gefunden wo ich die zahl eingeben kann aber ich kriege keine vernünftige Faktoriesierung hin.
Ebenso bei dem [mm] N_1 [/mm] mit der (p-1) Methode. Da verstehe ich gar nicht wie ich das machen soll.
MfG
Mathegirl
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:30 So 08.01.2012 | | Autor: | felixf |
Moin,
> Nur wie kommst du auf die folgende Formel?
>
> [mm](\lceil \sqrt{N_2} \rceil + 2)^2 - N_2[/mm]
schau doch mal in die Links, die ich dir geschrieben hatte!
> Und wenn ich das dann eingebe was du gepostet hast, dann
> kommt irgendwas komisches raus wenn ich auf submit klicke.
Was kommt denn raus? Weisst du, meine Kristallkugel ist gerade nicht hier...
> Ebenso bei dem [mm]N_1[/mm] mit der (p-1) Methode. Da verstehe ich
> gar nicht wie ich das machen soll.
Was verstehst du an dem Algorithmus denn nicht?
LG Felix
|
|
|
| |
|
Das Rechenverfahren ist mir ja bei Fermat klar, es hängt nur an dem Rechnen mit großen Zahlen.
Ich Rechne [mm] \wurzel{N}=x
[/mm]
[mm] r=x^2-N
[/mm]
Und das so lange, bis eine Quadratzahl raus kommt. Kommt keine Quadratzahl raus addiere ich 1, kommt dann keine Quadratzahl raus addiere ich wieder 1 usw..
Aber ich kann das mit einem Normalen Online Rechner nicht machen.
Bei deinem Link kommt folgendes raus:
[mm] 1222221585799508681051364816254053255153265457085432543884968999788063383297042\
[/mm]
7090450911515
[mm] 3496028583692514206631426765447898242325577096.03608024976794118424193166175575\
[/mm]
[mm] 9646982448065924518500087413690310175631770990769311395332399490880119940830765\
[/mm]
[mm] 0314270492840688650567079762674156471815784042789669840347632265445780616764680\
[/mm]
[mm] 0482101119013024508782239818104792212551494416254779350152552272055486113637756\
[/mm]
[mm] 6228731665777517448192744050327710207922205515390231364168020718220919330083575\
[/mm]
[mm] 1989193637843417732482074734692038859940352364735122118604699919361504015140540\
[/mm]
[mm] 6714134269572525318117844313455590328011641690676997263909975388003150870251483\
[/mm]
[mm] 0896421790690130461549440485091855040482472909233326203969034755186807211018231\
[/mm]
[mm] 5229314051024230931128124213604389364469298323022999533554857270037348101061994\
[/mm]
[mm] 8350758745753408902120795866705066040468051323052690805875618230833137212594057\
[/mm]
[mm] 3044853107408465286900757427345531681454398140229334910434630537372992683181363\
[/mm]
[mm] 3124514985545584694995329197578682284850350139629174535354280770384865991891782\
[/mm]
55708398052159933752407006583408741875667958434057429620843193065746076444093
Allerdigs weiß ich nicht was das was raus kommt sein soll!
Und die (p-1) Methode kann ich nicht anwenden. Da ist mir das Vorgehen nicht schlüssig bzw ich kann es bei kleineren Zahlen anwenden, aber nicht bei so einer großen zahl.
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:15 Mo 09.01.2012 | | Autor: | felixf |
Moin!
> Das Rechenverfahren ist mir ja bei Fermat klar, es hängt
> nur an dem Rechnen mit großen Zahlen.
>
> Ich Rechne [mm]\wurzel{N}=x[/mm]
>
> [mm]r=x^2-N[/mm]
>
> Und das so lange, bis eine Quadratzahl raus kommt. Kommt
> keine Quadratzahl raus addiere ich 1, kommt dann keine
> Quadratzahl raus addiere ich wieder 1 usw..
> Aber ich kann das mit einem Normalen Online Rechner nicht
> machen.
>
> Bei deinem Link kommt folgendes raus:
>
> [mm]1222221585799508681051364816254053255153265457085432543884968999788063383297042\[/mm]
> 7090450911515
>
> [mm]3496028583692514206631426765447898242325577096.03608024976794118424193166175575\[/mm]
>
> [mm]9646982448065924518500087413690310175631770990769311395332399490880119940830765\[/mm]
>
> [mm]0314270492840688650567079762674156471815784042789669840347632265445780616764680\[/mm]
>
> [mm]0482101119013024508782239818104792212551494416254779350152552272055486113637756\[/mm]
>
> [mm]6228731665777517448192744050327710207922205515390231364168020718220919330083575\[/mm]
>
> [mm]1989193637843417732482074734692038859940352364735122118604699919361504015140540\[/mm]
>
> [mm]6714134269572525318117844313455590328011641690676997263909975388003150870251483\[/mm]
>
> [mm]0896421790690130461549440485091855040482472909233326203969034755186807211018231\[/mm]
>
> [mm]5229314051024230931128124213604389364469298323022999533554857270037348101061994\[/mm]
>
> [mm]8350758745753408902120795866705066040468051323052690805875618230833137212594057\[/mm]
>
> [mm]3044853107408465286900757427345531681454398140229334910434630537372992683181363\[/mm]
>
> [mm]3124514985545584694995329197578682284850350139629174535354280770384865991891782\[/mm]
>
> 55708398052159933752407006583408741875667958434057429620843193065746076444093
>
> Allerdigs weiß ich nicht was das was raus kommt sein soll!
Ich zitiere mal mich selber: "Das rechnet dir $ [mm] (\lceil \sqrt{N_2} \rceil [/mm] + [mm] 2)^2 [/mm] - [mm] N_2 [/mm] $ aus und die Wurzel davon."
Damit ist die erste Zahl $12222215857995086810513648162540532551532654570854325438849689997880633832970427090450911515$ offenbar gleich $ [mm] (\lceil \sqrt{N_2} \rceil [/mm] + [mm] 2)^2 [/mm] - [mm] N_2 [/mm] $, und die zweite Zahl [mm] $\approx [/mm] 3496028583692514206631426765447898242325577096.03608$ ist die Wurzel davon. Damit siehst du insbesondere, dass die erste Zahl kein Quadrat ist.
> Und die (p-1) Methode kann ich nicht anwenden. Da ist mir
> das Vorgehen nicht schlüssig bzw ich kann es bei kleineren
> Zahlen anwenden, aber nicht bei so einer großen zahl.
Wenn du nicht etwas genauer wirst koennen wir dir allerdings nicht helfen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:28 Di 10.01.2012 | | Autor: | reverend |
Hallo Mathegirl,
ich habe den Thread bis zum jetzigen Zeitpunkt gelesen und frage mich, ob Dir einfach ein Langzahlenrechner fehlt - also schlicht die technische Möglichkeit, so große Zahlen zu bearbeiten.
Wo das online geht, hat Felix schon geschrieben. Ansonsten hat jedes größere CAS natürlich auch einen Langzahlenrechner.
Allerdings hat jedes davon, auch Magma, eine eigene Syntax, so dass die Eingabe manchmal schlicht daran scheitert, dass man die Syntax nicht kennt bzw. nicht intuitiv erschließen kann.
Ich nehme aber an, dass Du selbst programmieren kannst. Bei einer Vorlesung zu Kryptographie (und Du hattest ja schon mehrere Fragen in dieser Richtung) ist von einem von zwei Dingen auszugehen:
1) Entweder Ihr habt Zugang zu Rechnern mit entsprechenden, womöglich spezialisierten Programmen bzw. eine Studi-Lizenz, um entsprechende Programme günstig zu erwerben, oder
2) ihr sollt Euch im Lauf der Vorlesung die nötigen Programmteile selber schreiben.
Da es ja gar nicht darum geht, hier z.B. die vorliegenden Zahlen zu faktorisieren (die Zerlegung ist dem Aufgabensteller ja längst bekannt), sondern verschiedene Methoden zu lernen, kann es gut sein, dass einfach erwartet wird, dass Du den entsprechenden Schritt bzw. Algorithmus programmierst. Dabei wirst Du natürlich auf die dann schon bestehenden Unterprogramme wie Multiplikation großer Zahlen, Modulrechnung, Potenzierung, Wurzelziehen etc. zurückgreifen. Standardmäßig sind in allen Programmiersprachen die Mantissen begrenzt, selbst "große" Variablentypen werden hier nicht ausreichen.
Also - ist das das Problem?
Grüße
reverend
|
|
|
|
