Lehr- und Forschungseinheit
Institut
Universität
Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik der Ludwig-Maximilians-Universität
München
Das Problem des Faktorisierens einer Zahl hat Anwendung z.B. in der Kryptologie. Die Aufgabe dabei ist es, eine (meist große) Zahl n in ihre Primfaktoren zu zerlegen. Um dieses Problem zu lösen, kann man sich auf das einfachere Problem beschränken, zu einer gegebenen Zahl n zwei Zahlen m ≠ 1 und k ≠ 1 zu finden, so dass n = m * k und gilt.
Die Umkehrung, d.h. die Multiplikation zwei Zahlen ist einfach und lässt sich z.B. mit einem Schaltkreis der Größe O(log(n)2) lösen.
Ziel dieses FoPras ist es, ein Programm zu entwickeln, welches solche Schaltkreise in Aussagenlogik erzeugt und sich von einem SAT-Solver mögliche Eingabewerte m und k bei vorgegebener Ausgabe n berechnen lässt.
Literatur/Material/Links:
Dr. Martin Lange, D1.07, Oettingenstr. 67, Tel.: 089 21809313