Pseudoprimzahlen: Die konstruierte Pseudoprimzahl

Aus Wikibooks

[Bearbeiten] Die Kunst, eine Pseudoprimzahl nach Maß zu konstruieren

Eine Pseudoprimzahl $q\$ , die zu irgendeiner natürlichen Zahl $a\$ pseudoprim, im Sinne des kleinen fermatschen Satz ist, ist recht einfach. Man nehme zwei beliebige, zueinander teilerfremde Primzahlen $p\$ mit $p \ge 3$ , und multipliziere miteinander. Das Produkt wird dann schon zu wenigstens einer natürlichen Zahl $a\$ pseudoprim sein. Aber zu welcher Zahl $a\$ ? Interessant ist es ja, eine Pseudoprimzahl zu erzeugen, die zu einer vorher ausgewählten Zahl $a\$ pseudoprim ist, ohne sie testen zu müssen.

[Bearbeiten] $a\$ und $q\$ müssen zueinander teilerfremd sein

Damit zusammengesetzte Zahl $q\$ zu einer natürlichen Zahl $a\$ pseudoprim sein kann, muß immerhin sichergestellt sein, das $a\$ und $q\$ zueinander teilerfremd sind. Zu jeder solcher Fermatschen Pseudoprimzahlen der Form $q = p_1 \cdot p_2\$ lassen sich zwei Basen $a\$ finden, und zwar durch folgende Vorgehensweise:

Man ermittelt die Vielfachen von $p_1\$ und $p_2\$ :

$p_1, \ 2\cdot p_1, \ 3\cdot p_1, \ 4\cdot p_1, \ 5\cdot p_1, ...$

und

$p_2, \ 2\cdot p_2, \ 3\cdot p_2, \ 4\cdot p_2, \ 5\cdot p_2, ...$

Dann sucht man jeweils ein Vielfaches $m\cdot p_1$ und $n\cdot p_2$ heraus, für die $| m\cdot p_1 - n\cdot p_2 | = 2$ gilt. Die zwischen $m\cdot p_1$ und $n\cdot p_2$ liegende Zahl ist eine Basis, zu der die Zahl $q = p_1\cdot p_2$ pseudoprim ist (im Sinne des kleine fermatschen Satzes), und sie ist teilerfremd zu $p_1, \ p_2, \ m$ und $n\$ . Es gibt zu jeder Zahl $q = p_1\cdot p_2$ genau zwei Basen $a\$ die kleiner als $q\$ sind. Die Summe dieser beiden Basen $a_1\$ und $a_2\$ ist $q\$ . Alle Basen $a\$ , die größer als $q\$ sind und sich nach dem beschriebenen Algorithmus konstruieren lassen, haben entweder die Form $a = a_1 + m\cdot q$ oder $a = a_1 + m\cdot q$ .

[Bearbeiten] Beispiel

$391 = 17\cdot 23$

Die Vielfachen von $17\$ sind: $17,\ 34,\ 51,\ 68,\ 85,\ 102,\ 119,\ 136,\ 153,\ 170,\ 187,\ 204,\ 221,\ 238,\ 255,\ 272,\ ...$

Die Vielfachen von $23\$ sind: $23,\ 46,\ 69,\ 92,\ 115,\ 138,\ 161,\ 184,\ 207,\ 230,\ 253,\ 276,\ ...$

Von diesen Vielfachen haben $136\$ und $138\$ beziehungsweise $253\$ und $255\$ eine Differenz von $2\$ . Die zwischen $136\$ und $138\$ liegende Zahl $137\$ und die zwischen $253\$ und $255\$ liegende Zahl $254\$ sind Basen zu denen die Zahl $391\$ pseudoprim ist.