Primzahltest < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:59 Sa 26.06.2004 | | Autor: | blubli89 |
Hallo,
Ich habe einen Primzahltest entwickelt,der mit Potenzendifferenzen arbeitet und würde ihn gerne überprüfen lassen.
Es ist ja bekannt das teilbare ungerade Zahlen sich ausser aus
[mm] a^2-(a-1)^2 [/mm] auch aus [mm] a^2-(a-n)^2 [/mm] ergeben,wobei n>1 ist.
Hat man also eine Differenz: [mm] a^2-(a-n)^2 [/mm] , ist das Ergebnis immer teilbar.
Es geht also darum herauszufinden ob eine primverdächtige Zahl sich ausser durch [mm] a^2-(a-1)^2 [/mm] auch durch [mm] a^2-(a-n)^2 [/mm] darstellen lässt.
Ich habe nun heraus gefunden:
Ist eine zu testende Pseudoprimzahl 6n-1 , so ist sie die Differenz von
[mm] (3n)^2 -(3n+-1)^2 [/mm] , ist sie 6n+1 ist sie die Differenz von
[mm] (3n+-1)^2-(3n)^2.
[/mm]
Beispiele: 6n-1
[mm] 65=9^2-4^2=81-16 [/mm]
[mm] 77=9^2-2^2=81-4 [/mm]
[mm] 95=12^2-7^2=144 [/mm] -49
usw...
6n+1
[mm] 55=8^2-3^2=64-9 [/mm]
[mm] 85=11^2-6^2=121-36 [/mm]
[mm] 91=10^2-3^2=100-9 [/mm]
usw...
Das Gleiche gilt für die triviale Darstellung:
[mm] 65=33^2-32^2 [/mm]
[mm] 77=39^2-38^2 [/mm]
[mm] 95=48^2-47^2 [/mm]
[mm] 55=28^2-27^2 [/mm]
[mm] 85=43^2-42^2 [/mm]
[mm] 91=46^2-45^2 [/mm]
Dieser Sachverhalt lässt sich nutzen um Potenzendifferenzen effektiv als Primzahltest einzusetzen.
Allerdings nur wenn der Abstand der Primfaktoren zueinander kleiner ist als der Abstand des kleinsten Faktors zu 0.
Ich möchte mal 2 Beispiele geben um den Lösungsweg zu veranschaulichen.
21293 :ist 6n-1, (alle 6n-1 haben die Quersummen 2,5,8)
deshalb entspricht sie [mm] (3n)^2-(3n+-1)^2. [/mm]
Ist sie teilbar und sind die Primfaktoren nicht zu weit auseinander , muss sie sich aus einer [mm] Differenz:(3n)^2-(3n+-1)^2 [/mm] bilden lassen.
Jetzt zieht man einfach die Wurzel und bildet von allen 3n oberhalb der Wurzel die Potenz,zieht die 21293 ab und prüft ob das Ergebnis eine Potenz ist. Da [mm] a^2-b^2=21293 [/mm] , ist auch [mm] a^2-21293=b^2
[/mm]
sqrt 21293=145.9....
[mm] 147^2-21293=316 [/mm]
[mm] 150^2-21293=1207
[/mm]
[mm] 153^2-21293=2116=46^2
[/mm]
[mm] 21293=153^2-46^2 [/mm]
aus der gefundenen Potenzendifferenz lassen sich jetzt die Primfaktoren bestimmen=> 153+-46=107,199 =>21293=107*199
5141: ist 6n-1 sqrt=71,7...
[mm] 72^2-5141=43 [/mm]
[mm] 75^2-5141=484=22^2 [/mm]
75+-22=53,97 5141=53*97
Ich hoffe meine Erklärungen waren zu verstehen und die Beispiele auch.
Eine Erläuterung zu den 6n+1Pseudoprimzahlen möchte ich jetzt noch nicht geben,das wäre zu viel auf einmal.
Ich wäre für eine ,auch einem Laien verständliche Antwort,dankbar.Ausserdem interessiert mich eure Meinung,ich glaube ich kann beweisen das sich mit dieser Methode bestimmte zusammengesetzte Zahlen sehr schnell entlarven lassen,schneller als durch normales Probeteilen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:43 Mo 28.06.2004 | | Autor: | Paulus |
Hallo blubli89
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Da dir bis jetzt noch niemand geantwortet hat, möchte ich doch wenigsten ein Lebenszeichen aus dem Matheraum schicken, wenn auch nicht eine komplette Lösung.
> Ich habe einen Primzahltest entwickelt,der mit
> Potenzendifferenzen arbeitet und würde ihn gerne überprüfen
> lassen.
> Es ist ja bekannt das teilbare ungerade Zahlen sich ausser
> aus
> [mm]a^2-(a-1)^2[/mm] auch aus [mm]a^2-(a-n)^2[/mm] ergeben,wobei n>1 ist.
>
>
> Hat man also eine Differenz: [mm]a^2-(a-n)^2[/mm] , ist das Ergebnis
> immer teilbar.
> Es geht also darum herauszufinden ob eine primverdächtige
> Zahl sich ausser durch [mm]a^2-(a-1)^2[/mm] auch durch [mm]a^2-(a-n)^2[/mm]
> darstellen lässt.
>
> Ich habe nun heraus gefunden:
> Ist eine zu testende Pseudoprimzahl 6n-1 , so ist sie die
> Differenz von
> [mm](3n)^2 -(3n+-1)^2[/mm] , ist sie 6n+1 ist sie die Differenz von
>
> [mm](3n+-1)^2-(3n)^2.
[/mm]
Hier würde ich unbedingt empfehlen, in der gleichen Formel nicht den gleichen Buchstaben für unterschiedliche Sachen zu verwenden. Es sollte also eher etwa so aussehen:
Hat die zu testende Zahl die Gestalt $6n-1$, so kann sie dargestellt werden als
[mm] $(3p)^2 [/mm] - (3q [mm] \pm 1))^2$
[/mm]
respektive:
Hat die zu testende Zahl die Gestalt $6n+1$, so kann sie dargestellt werden als
$(3p [mm] \pm 1)^2 [/mm] - [mm] (3q)^2$
[/mm]
Ich weiss jetzt nicht, ob das wirklich stimmt (hast du denn einen Beweis dafür ausgearbeitet?)
Jedenfalls gilt aber die Umgekehrte Richtung:
Wenn eine ungerade Zahl als
[mm] $(3p)^2 [/mm] - (3q [mm] \pm 1))^2$
[/mm]
dargestellt werden kann, dann hat sie die Form
$6n-1$
respektive:
Wenn eine ungerade Zahl als
$(3p [mm] \pm 1)^2 [/mm] - [mm] (3q)^2$
[/mm]
dargestellt werden kann, dann hat sie die Form
$6n+1$
> Dieser Sachverhalt lässt sich nutzen um Potenzendifferenzen
> effektiv als Primzahltest einzusetzen.
> Allerdings nur wenn der Abstand der Primfaktoren zueinander
> kleiner ist als der Abstand des kleinsten Faktors zu 0.
>
![[ok]](/images/smileys/ok.gif "[ok]") Das Problem hierbei scheint mir aber zu sein, dass du am Anfang gar nicht weisst, wie weit die Faktoren auseinander liegen. Aber trotzdem: ich würde es auch auf diese oder ähnliche Art machen. Diese Methode hat übrigens bereits Fermat verwendet, um Zahlen zu faktorisieren.
> Ich möchte mal 2 Beispiele geben um den Lösungsweg zu
> veranschaulichen.
>
> 21293 :ist 6n-1, (alle 6n-1 haben die Quersummen 2,5,8)
>
> deshalb entspricht sie [mm](3n)^2-(3n+-1)^2.[/mm]
> Ist sie teilbar und sind die Primfaktoren nicht zu weit
> auseinander , muss sie sich aus einer
> [mm]Differenz:(3n)^2-(3n+-1)^2[/mm] bilden lassen.
> Jetzt zieht man einfach die Wurzel und bildet von allen 3n
Wie aufwändig ist denn das Wurzelziehen?
> oberhalb der Wurzel die Potenz,zieht die 21293 ab und prüft
> ob das Ergebnis eine Potenz ist. Da [mm]a^2-b^2=21293[/mm] , ist
> auch [mm]a^2-21293=b^2
[/mm]
>
> sqrt 21293=145.9....
>
> [mm]147^2-21293=316[/mm]
> [mm]150^2-21293=1207
[/mm]
> [mm]153^2-21293=2116=46^2
[/mm]
>
> [mm]21293=153^2-46^2[/mm]
> aus der gefundenen Potenzendifferenz lassen sich jetzt die
> Primfaktoren bestimmen=> 153+-46=107,199 =>21293=107*199
>
>
> 5141: ist 6n-1 sqrt=71,7...
>
> [mm]72^2-5141=43[/mm]
> [mm]75^2-5141=484=22^2[/mm]
>
> 75+-22=53,97 5141=53*97
>
Für die Zahlen der Form $6n-1$ scheint das zu funktionieren, wenn deine noch nicht bewiesene Vermutung stimmt. Wie willst du das aber für $6n+1$ machen?
Ich würde deshalb eher einen etwas modifizierten Weg gehen: Jede ungerade Zahl ist die Differenz zwischen 2 Quadratzahlen. Die Differenz zwischen zwei aufeinanderfolgenden Quadratzahlken ist eine ungerade Zahl, die sich selber jeweils um $2$ erhöht, also etwa so:
$0+1=1 = [mm] 1^2$
[/mm]
$1+3=4 = [mm] 2^2$
[/mm]
$4+5=9 = [mm] 3^2$
[/mm]
$9+7=16 = [mm] 4^2$
[/mm]
$16+9=25 = [mm] 5^2$
[/mm]
$25+11=36 = [mm] 6^2$
[/mm]
$36+13=49 = [mm] 7^2$
[/mm]
etc.
Von dieser Ueberlegung ausgehend, würde ich es etwa so untersuchen:
(ich zeicgs an einem kleinen Beispiel, um nicht zu viel schreiben zu müssen: zu untersuchen sei die Zahl $133$)
Die nächsthöhere Quadratzahl ist $144$ (Es ist Vorsicht geboten, wenn die zu untersuchende Zahl selber bereits eine Quadratzah ist!)
Um die nächste Quadsratzahl zu bestimmen, muss dann einfach $25$ addiert werden, das nächste mal $27$, dann $29$ etc.)
$DeltaQ = 25$
$144$
$DeltaT = 1$
$133 < 144$, also $133+DeltaT = 133+1 = 134$, $DeltaT = DeltaT+2=3$
$133 < 144$, also $134+DeltaT = 134+3 = 137$, $DeltaT = DeltaT+2=5$
$137 < 144$, also $137+DeltaT = 137+5 = 142$, $DeltaT = DeltaT+2=7$
$142 < 144$, also $142+DeltaT = 142+7 = 149$, $DeltaT = DeltaT+2=9$
$149 > 144$, also $144+DeltaQ = 144+25 = 169$, $DeltaQ = DeltaQ+2=27$
$149 < 169$, also $149+DeltaT = 149+9 = 158$, $DeltaT = DeltaT+2=11$
$158 < 169$, also $158+DeltaT = 158+11 = 169$, $DeltaT = DeltaT+2=13$
$169 = 169$, wir sind am Ende des Programms. Es müssen nur noch die Faktoren ausgegeben werden.
Ich habe das am Beispiel VB-Skript gemacht:
-------------------------------------------------------------------------------------------
const Testzahl = 21293
dim Q
dim T
dim deltaQ
dim deltaT
DeltaT=1
Q=int(sqr(Testzahl))
DeltaQ=2*Q+1
Q=Q*Q
T=Testzahl
Do While T<>Q
if T < Q then
T = T + DeltaT
deltaT = DeltaT + 2
else
Q=Q+deltaQ
DeltaQ = DeltaQ + 2
end if
Loop
msgbox Testzahl & " = " & sqr(Q) - sqr(T - Testzahl) & " * " & sqr(Q) + sqr(T - Testzahl)
-------------------------------------------------------------------------------------------
Aber achtung: das Programm funktioniert natürlich nur für Zahlen einer Grössenordnung, die das Programm auch intern darstellen kann. Eine zum Beispiel 193-stellige Zahl kann so nicht bearbeitet werden.
Mit lieben Grüssen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:50 Mo 28.06.2004 | | Autor: | blubli89 |
Hallo Paulus,
ja da hast du schon recht ,man sieht einer zu testenden Zahl nicht an wie weit die Faktoren auseinander liegen.
Für 6n+1 gibt es ein leicht abgewandeltes Verfahren mit dem man ähnlich schnell faktorisieren kann.
Ich arbeite gerade an einem Beweis,er wird vielleicht nicht das Nonplusultra sein,aber nachvollziehbar.Es geht dabei um Quersummen.
Sobald ich ihn fertig habe,bekommst du eine Antwort.
Deinen Alternativvorschlag konnte ich leider nicht verstehen.Ich habe nur mittlere Reife, besitze keinen PC ,und kann auch nicht programmieren.
Gruß Gerold
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:50 Mo 28.06.2004 | | Autor: | blubli89 |
Hallo Paulus,
einen Beweiß habe ich jetzt erarbeitet,es geht dabei um Quersummen.Ich weiß nicht ob er den strengen Ansprüchen akkurater Mathematik genügt,aber die Logik dahinter müsste eigentlich zu verstehen sein.
Versuch eines Beweises
Potenzen,Potenzbasen und ihre Quersummen
Sei Q=Quersumme,B=Potenzbasis und P=Potenz,dann gilt:
QB=1,8 => QP=1
QB=2,7 => QP=4
QB=4,5 => QP=7
Alle 3n haben Q=3,6 oder 9
Alle 3n-1 haben Q=2,5 oder 8
Alle 3n+1 haben Q=1,4 oder 7
[mm] (3n)^2 [/mm] mit Q=9,abzüglich [mm] (3n+-1)^2 [/mm] mit Q=1,4,7,ist also immer:
9-1=8
9-4=5
9-7=2
Alle 6n-1 besitzen die Quersummen 8,5 oder 2.
Also ist 6n-1= [mm] (3n)^2-(3n+-1)^2
[/mm]
Ausnahmen :
n=0
[mm] (3n)^2<(3n+-1)^2 [/mm]
Man sollte also nicht in den negativen Bereich gehen.
..........................................................
[mm] (3n+-1)^2 [/mm] mitQ=1,4,7, abzüglich [mm] (3n)^2 [/mm] mit Q=9 ,ist immer:
10-9=1, 13-9=4
16-9=7
Alle 6n+1 besitzen die Quersummen1,4 oder 7.
Also ist [mm] 6n+1=(3n+-1)^2-(3n)^2
[/mm]
Ausnahmen : [mm] (3n+-1)^2<(3n)^2 [/mm] (negativer Bereich)
Anmerkung: n in den Ausdrücken 3n , 3n+-1 und 6n+-1 ist nicht unbedingt identisch.Ich wollte Verwirrung(durch 3 verschiedene Variablen) vermeiden.Nennen wir n eine variable Variable.
Grüße Gerold
|
|
|
|
