Primfaktorenzerlegung

Übersicht

BlitzBasic

Codearchiv

	Triton Betreff: Primfaktorenzerlegung	Di, Dez 27, 2005 22:09 Antworten mit Zitat
Da man sowas manchmal schon braucht (z.B zum Knacken vom Verschlüsselungsalgorithmen ), hier ein Programm um eine natürliche Zahl in ihre Primfaktoren zu zerlegen. Dass dies bei jeder natürlichen Zahl geht, besagt der Fundamentalsatz der Zahlentheorie. Jede Zahl kann also als Produkt aus Primzahlen geschrieben werden. Die Primfaktoren werden in einen Array geschrieben. Bis 2^31 hat jede Zahl 31 oder weniger Primfaktoren, weshalb man da in der Regel nichts ändern müsste. Theoretisch ginge es noch schneller, indem beim Primzahltest nur jede Primzahl als Teiler überprüft wird. Da es aber auch so für jede Zahl nur ein- oder zweistellige ms-Zeiten in Anspruch nimmt, dürfte das praktisch kaum noch mehr Geschwindigkeit bringen. Nur wenn eine Zahl ein Produkt aus 2 großen Primzahlen ist (etwa 3998940009=1599919901), dauert eine Primfaktorenzerlegung schon recht lange. Weil das bilden so einer Zahl sehr schnell, das Zerlegen aber sehr lange dauert, sind moderne Verschlüsselungsalgorithmen auch so sicher. Gerade für diese Zahlen sollte man die 2. Funktion nehmen. BlitzBasic:* [AUSKLAPPEN] [EINKLAPPEN] ; zerlegt eine natürliche Zahl in ihre Primfaktoren ; 27.12.2005 by Triton ;** http://www.silizium-net.de Graphics 640,480,32,2 AppTitle("Primfaktorenzerlegung") zahl=33219280 Dim primfaktoren(31) t1= MilliSecs() b = primfaktorzerlegung(zahl) f$ = Str(zahl)+" = " For pf = 0 To b-1 f$ = f$ + Str(primfaktoren(pf)) If pf < b-1 Then f$ = f$ + " * " Next Print f$ Print b+" Primfaktoren gefunden. Dauer: "+Str(MilliSecs()-t1)+" ms" WaitKey End ;--- Function primzahl(zahl) If zahl=1 Or zahl=0 Then Return 0 wurzel=Sqr(zahl) For a = 2 To wurzel If zahl Mod a = 0 Then Return 0 Next Return 1 End Function ;--- Function primfaktorzerlegung(zahl) ; schreibt die Primfaktoren in array primfaktoren ; gibt anzahl der Primfaktoren zurück If primzahl(zahl) = 1 Then primfaktoren(0) = zahl Return 1 End If zahl2=zahl a=1 While primzahl(zahl2) = 0 a=a+1 If primzahl(a) And zahl2 Mod a = 0 Then primfaktoren(b) = a zahl2=zahl2/a b=b+1 a=1 End If Wend primfaktoren(b) = zahl2 b=b+1 Return b End Function ;--- Function primfaktorzerlegung2(zahl) ; geht davon aus, dass eine Zahl aus nur 2 Pf besteht ; -> viel schneller bei diesen speziellen Zahlen zahl2=zahl a=1 While b = 0 a=a+1 If primzahl(a) And zahl2 Mod a = 0 Then primfaktoren(0) = a b=2 primfaktoren(1)=zahl2/a Return b End If Wend End Function
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Betreff: Primfaktorenzerlegung

Di, Dez 27, 2005 22:09
Antworten mit Zitat

Da man sowas manchmal schon braucht (z.B zum Knacken vom Verschlüsselungsalgorithmen Wink

), hier ein Programm um eine natürliche Zahl in ihre Primfaktoren zu zerlegen.
Dass dies bei jeder natürlichen Zahl geht, besagt der Fundamentalsatz der Zahlentheorie. Jede Zahl kann also als Produkt aus Primzahlen geschrieben werden.

Die Primfaktoren werden in einen Array geschrieben. Bis 2^31 hat jede Zahl 31 oder weniger Primfaktoren, weshalb man da in der Regel nichts ändern müsste.

Theoretisch ginge es noch schneller, indem beim Primzahltest nur jede Primzahl als Teiler überprüft wird. Da es aber auch so
für jede Zahl nur ein- oder zweistellige ms-Zeiten
in Anspruch nimmt, dürfte das praktisch kaum noch mehr Geschwindigkeit bringen.

Nur wenn eine Zahl ein Produkt aus 2 großen Primzahlen ist (etwa
39989*40009=1599919901), dauert eine Primfaktorenzerlegung schon recht lange. Weil das bilden so einer Zahl sehr schnell, das Zerlegen aber sehr lange dauert, sind moderne Verschlüsselungsalgorithmen auch so sicher. Gerade für diese Zahlen sollte man die 2. Funktion nehmen.

BlitzBasic: [AUSKLAPPEN]


;** zerlegt eine natürliche Zahl in ihre Primfaktoren
;** 27.12.2005 by Triton
;** http://www.silizium-net.de
Graphics 640,480,32,2
AppTitle("Primfaktorenzerlegung")
zahl=33219280
Dim primfaktoren(31)
t1= MilliSecs()

b = primfaktorzerlegung(zahl)
f$ = Str(zahl)+" = " 
For pf = 0 To b-1
	f$ = f$ + Str(primfaktoren(pf))
	If pf < b-1 Then f$ = f$ + " * "
Next
Print f$
Print b+" Primfaktoren gefunden. Dauer: "+Str(MilliSecs()-t1)+" ms"
WaitKey
End

;---
Function primzahl(zahl)
If zahl=1 Or zahl=0 Then Return 0
wurzel=Sqr(zahl)
For a = 2 To wurzel
	If zahl Mod a = 0 Then Return 0
Next
Return 1
End Function


;---
Function primfaktorzerlegung(zahl)
;** schreibt die Primfaktoren in array primfaktoren
;** gibt anzahl der Primfaktoren zurück
If primzahl(zahl) = 1 Then
	primfaktoren(0) = zahl
	Return 1
End If

zahl2=zahl
a=1
While primzahl(zahl2) = 0
	a=a+1
	If primzahl(a) And zahl2 Mod a = 0 Then
		primfaktoren(b) = a
		zahl2=zahl2/a
		b=b+1
		a=1
	End If
Wend
primfaktoren(b) = zahl2
b=b+1
Return b
End Function

;---
Function primfaktorzerlegung2(zahl)
;** geht davon aus, dass eine Zahl aus nur 2 Pf besteht
;** -> viel schneller bei diesen speziellen Zahlen

zahl2=zahl
a=1
While b = 0
a=a+1
If primzahl(a) And zahl2 Mod a = 0 Then
primfaktoren(0) = a
b=2
primfaktoren(1)=zahl2/a
Return b
End If
Wend

End Function

Coding: silizium-net.de | Portfolio: Triton.ch.vu