Im letzten Kapitel haben wir uns mit Super- und Quanten-Computer befasst:

• Von Super-Computern wissen wir, dass diese sehr viel Parallelisieren. Können wir das auch auf unserem eigenen Computer? Bringt das etwas?
• Bei den Quantencomputern haben wir gesehen, dass diese eine Gefahr für die auf dem Faktorisierungs-Problem basierenden asymmetrischen Verschlüsselungen darstellen

Faktorisieren #

Wir möchten eine Zahl faktorisieren. Wie können wir vorgehen? Wie können wir das Vorgehen optimieren?

def factorize(n):
zahl = n
factors = []
i = 2
while i <= n:
	if zahl % i == 0:
		factors.append(i)
		zahl = zahl // i
	else:
		i = i + 1
return factors

Brute-Force #

Wir testen alle möglichen Faktoren aus.

Optimieren:

• nur die 2 und ungerade Zahlen testen
• nur bis zur Hälfte der Zahl testen (aber Achtung Primzahl)

def factorize(n):
zahl = n
factors = []
i = 2
while zahl % i == 0:
	factors.append(i)
	zahl = zahl // i
i = 3
while i < n//2+1:
	if zahl % i == 0:
		factors.append(i)
		zahl = zahl // i
	else:
		i = i + 2
if len(factors) == 0:
	factors.append(zahl)

return factors

def factorize(n):
if n == 1:
	return []
for i in range(2,n+1):
	if n%i == 0:
		return [i] + factorize(n//i)

Zeit messen #

Mit der Funktion time aus dem gleichnamigen Modul, können wir die aktuelle Systemzeit in Sekunden abfragen. Wenn wir das 2x machen und die Differenz berechnen, dann haben wir die dazwischen verstrichene Zeit in Sekunden:

from time import time

start = time()
# mach etwas
end = time()
print(end - start)

Dictionary #

Wir könnten Primzahlen vorberechnen und so die Zeit der Primfaktorenzerlegung. Die folgende Webseite hat Primzahlen vorberechnet:

👉 http://www.math.uchicago.edu/~luis/allprimes.html

Wenn man aber grössere Listen hat, sollte man die in einer externen Datei speichern und in Python einlesen. Wenn man die Zahlen Komma-getrennt in ewiner CSV-Datei hat, kann man sie wie folgt einlesen:

txt_file = open("primes.csv", "r")
file_content = txt_file.read()
txt_list = file_content.split(",")

primes = []
for txt_prime in txt_list:
	primes.append(int(txt_prime))

Primzahlen #

Primzahlfunktion #

$\pi (x)$ sei die Primzahlfunktion, die Anzahl Primzahlen, die kleiner als $x$ sind.

Primzahlsatz #

Bereits 1851 bewies Pafnuti Lwowitsch Tschebyschow eine schwächere Version des Primzahlsatzes:

Das heisst, dass die Anzahl der Primzahlen unter einer gegebenen Grösse um nicht mehr als ungefähr 10 % nach oben oder unten von der logarithmischen Funktion $x/\ln (x)$ abweicht.

Parallelisieren #

In Python kann man Abläufe mit Hilfe von sogenannten Threads parallelisieren:

Das folgende Beispiel starte eine Funktion 3x parallel.

import logging
import threading
import time

def thread_function(name):
	logging.info("Thread %s: starting", name)
	time.sleep(2)
	logging.info("Thread %s: finishing", name)


format = "%(asctime)s: %(message)s"
logging.basicConfig(format=format, level=logging.INFO,
					datefmt="%H:%M:%S")

threads = []
for index in range(3):
	logging.info("Main    : create and start thread %d.", index)
	x = threading.Thread(target=thread_function, args=(index,))
	threads.append(x)
	x.start()

for index, thread in enumerate(threads):
	logging.info("Main    : before joining thread %d.", index)
	thread.join()
	logging.info("Main    : thread %d done", index)

Mehr zum Beispiel und zu Threads:
👉 https://realpython.com/intro-to-python-threading/