Pseudoprimzahlen: Fermatsche Pseudoprimzahlen

Aus Wikibooks

[Bearbeiten] 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 \le a \le 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$

[Bearbeiten] 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 \ge 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 \ge 1\$ pseudoprim ist, so ist $q\$ auch pseudoprim zu $a^n \mod q\$ mit $n \ge 1\$

Pseudoprimzahlen: Fermatsche Pseudoprimzahlen

Aus Wikibooks

[Bearbeiten] Die fermatsche Pseudoprimzahl

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

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Mitmachen

Werkzeuge

Drucken/exportieren