Pseudoprimzahlen: Pseudoprimzahlen zur Basis a nach Michele Cipolla

Pseudoprimzahlen

Dieses Kapitel oder dieser Abschnitt ist unverständlich formuliert. Ein Hinweis, was nicht verstanden wird, ist möglicherweise auf der Diskussionsseite des Artikels zu finden. Wenn Sie Hilfe benötigen, schauen Sie, welche Qualitätskriterien an ein gutes Buch gestellt werden. Das allgemeine Vorgehen bei diesem Baustein kannst Du hier nachlesen.

Fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

Michele Cipolla hat 1904 ein Verfahren zum Erzeugen beliebiger fermatscher Pseudoprimzahlen zu einer beliebigen, natürlichen Basis $a\geq 2\$ gefunden. Dazu benötigt man eine Primzahl, die $a(a^{2}-1)\$ nicht teilt. Warum, das wird weiter unten erklärt.

Mit der Basis $a\$ und der Primzahl $p\$ werden zwei Zahlen $n_{1}\$ und $n_{2}\$ erzeugt:

$n_{1}={\frac {a^{p}-1}{a-1}},\ \ n_{2}={\frac {a^{p}+1}{a+1}}$

Das Produkt $n=n_{1}\cdot n_{2}\$ ist eine fermatsche Pseudoprimzahl zur Basis $a\$

Erklärung

Die Bedingung, dass $p\$ teilerfremd zu $a(a^{2}-1)\$ sein soll, kann auch so formuliert werden: $p\$ soll eine Primzahl sein, die $(a-1)\cdot a\cdot (a+1)\$ nicht teilt, da nach der dritten binomischen Formel $(a^{2}-1)=(a-1)\cdot (a+1)\$ ist. Damit ist sichergestellt, dass $p\$ zu $a$, $(a-1)\$ und $(a+1)\$ teilerfremd ist.

${\frac {a^{p}-1}{a-1}}$ und ${\frac {a^{p}+1}{a+1}}$ sind beides Partialsummen geometrischer Reihen, nämlich:

${\frac {a^{p}-1}{a-1}}=a^{p-1}+a^{p-2}+...+a^{2}+a+1$ und

${\frac {a^{p}+1}{a+1}}=(-a)^{p-1}+(-a)^{p-2}+...+(-a)^{2}+(-a)+1$

Aus $n_{1}\equiv 1\mod 2p$ und $n_{2}\equiv 1\mod 2p$

folgt, dass auch $n\equiv 1\mod 2p$ ist.

Aus $a^{2p}\equiv 1\mod n$

folgt, dass $a^{n-1}\equiv 1\mod n$ ist,

so dass n eine Pseudoprimzahl zur Basis a sein muss. Da es unendlich viele Primzahlen gibt, muss es demnach auch unendlich viele Pseudoprimzahlen zu jeder Basis a geben.

Liste fermatscher Pseudoprimzahlen zur Basis a nach Michele Cipolla

a	p	n1	n2	n=n1•n2	Faktoren
2	5	31	11	341	11•31
2	7	127	43	5461	43•127
3	5	121	61	7381	11•11•61
3	7	1093	547	597871	547•1093
2	11	2047	683	1398101	23•89•683
7	5	2801	2101	5884901	11•191•2801
2	13	8191	2731	22369621	2731•8191
5	7	19531	13021	254313151	29•449•19531
13	5	30941	26521	809977861	11•2411•30941
3	11	88573	44287	3922632451	23•67•661•3851
2	17	131071	43691	5726623061	43691•131071
17	5	88741	78881	6999978821	11•71•101•88741
2	19	524287	174763	91625968981	174763•524287
3	13	797161	398581	317733228541	398581•797161
11	7	1948717	1623931	3164581946527	43•45319•1623931
2	23	8388608	2796203	23456248059221	47•178481•2796203