Pseudoprimzahlen: Fermatsche Pseudoprimzahlen

Die fermatsche Pseudoprimzahl

Eine zusammengesetzte Zahl $q\$ gilt dann als fermatsche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl $a\$ mit $\operatorname {ggT} (a,q)=1$ und $2\leq a\leq q-2$ gibt, so das für $a\$ und $q\$ gilt: $a^{q-1}\equiv 1\mod q$ .

Beispiel:

15=3\cdot 5

ist eine zusammengesetze Zahl

$4^{15-1}\$	$\equiv 1\mod 15$
$11^{15-1}\$	$\equiv 1\mod 15$

Wie man, bei Kenntnis einer Basis zu einer fermatschen Pseudoprimzahl, weitere Basen findet

Natürlich gibt es zu einer fermatschen Pseudoprimzahl $q\$ niemals nur eine Basis $a\$ , zu der $q\$ pseudoprim ist.

Das läßt sich an einer Pseudoprimzahl, sagen wir beispielsweise mal 21, zeigen:

Die 21 ist pseudoprim zur Basis 13 pseudoprim.

Wenn eine ungerade, fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ mit $a<q\$ pseudoprim ist, so ist $q\$ auch zu der Basis $(q-a)\$ pseudoprim.

Da 21 pseudoprim zur 13 ist, ist 21 auch pseudoprim zu (21-13) = 8.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis $a\$ mit $a<q\$ pseudoprim ist, so ist $q\$ auch zu der Basis $a^{n}\$ mit einer natürlichen Zahl $n\geq 1\$ pseudoprim.

Da 21 pseudoprim zu 8 und 13 ist, ist 21 auch zu

8^{2}=64,\ 13^{2}=169,\ 8^{3}=512,\ 13^{3}=2197,\ ...\

pseudoprim.

Wenn eine fermatsche Pseudoprimzahl $q\$ zu einer Basis der Form $a^{n}\$ mit $n\geq 1\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu $a^{n}\mod q\$ mit $n\geq 1\$

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.