In der Literatur über RSA wird oft empfohlen, bei der Wahl eines Schlüsselpaares sogenannte "starke" Primzahlen für p und q zur Bildung des Moduls n zu wählen. Starke Primzahlen haben bestimmte Eigenschaften, die es schwer machen sollen, das Produkt n mit bestimmten Methoden zu faktorisieren. Diese Eigenschaften umfassen bspw. die Existenz eines großen Primteilers von p-1 und eines großen Primteilers von p+1. Der Grund dafür liegt darin, daß einige Faktorisierungsmethoden besonders gut arbeiten, wenn p-1 oder p+1 nur kleine Faktoren besitzen. Starke Primzahlen widerstehen diesen Angriffen.
Egal, die Fortschritte der letzten 10 Jahren Faktorisierungstheorie (siehe Frage 48), wie bspw. die elliptischen Faktorisierungsmethoden, haben die Vorteile von starken Primzahlen zunichte gemacht. Die neuen Methoden haben die gleichen Chancen gegen "starke" wie "schwache" Primfaktoren. Deshalb erhöhen "starke" Primzahlen allein die Sicherheit nicht sonderlich. Große Primzahlen zu wählen, ist entscheidend. Es ist birgt keine Gefahr, große und "starke" Primzahlen zu wählen, es dauert nur etwas länger als beliebige gleichgroße Primzahlen zu erzeugen.
Es ist möglich, daß neue Faktorisierungserkenntnisse gewonnen werden, in den erneut von bestimmten Eigenschaften der Primzahlen profitieren. Dann kann die Wahl von "starken" Primzahlen vielleicht wieder helfen, die Sicherheit zu erhöhen.