Faktorisierungsangriff

Faktorisierung

Bei diesem Angriff werden Algorithmen eingesetzt, die die Primfaktorzer legung einer natürlichen Zahl berechnen. Eines dieser Verfahren ist das der Fermat’schen Faktorisierung. Es führt besonders schnell zum Ziel, wenn sich die beiden Primzahlen p und q, deren Produkt n ist, nur wenig von n unterscheiden. Der Algorithmus beruht auf dem Satz, dass es für eine natürliche Zahl n, die Produkt zweier Primzahlen p und q ist, zwei natürliche Zahlen a und b gibt, so dass gilt:

n= a 2 b 2 = ( a+b ) =p ( ab ) =q =pq.

Die Idee des Algorithmus besteht nun darin, nach Zahlen a und b zu suchen, die die obige Gleichung erfüllen. Man beginnt mit a= n + 1 und erhöht a schrittweise um ...

Get IT-Sicherheit, 10th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.