Aufgabe 7:  (Faktorisierung)

Sie wollen die natürliche Zahl n faktorisieren (in Faktoren zerlegen).

1. Erstellen Sie eine Excel-Tabelle mit drei Zeilen:

   - mit den auf n folgenden ganzen Zahlen x_i

   - mit den zugehörigen Differenzen x_i² – n

   - mit den Quadratwurzeln y_i aus diesen Differenzen

   Sobald eine dieser Quadratwurzeln y_i eine ganze Zahl ist, haben Sie mit x_i + y_i einen Faktor von n gefunden!

   Probieren Sie das Verfahren mit n = 2041 aus.

   xi	46	47	48	49	50	51	...
   xi2-n	75	168	263	360	459	560	...
   yi	8,66	12,96	16,22	18,97	21,42	23,66	...

    

    

2. Implementieren Sie die p-1-Methode zur Faktorisierung von natürlichen Zahlen.

    

3. Schreiben Sie ein Programm, das eine zufällige Zahl n = p·q mit p und q Primzahlen der Länge jeweils k = 28 erzeugt und anschließend versucht, n mit der p-1-Methode wieder zu faktorisieren. Lassen Sie das Programm ein paarmal laufen.