Hintergrundwissen

Starke Pseudoprimzahl zur Basis a

Starke Pseudoprimzahlen sind eine echte Teilmenge der Pseudoprimzahlen. Auf der Grundlage starker Pseudoprimzahlen lässt sich ein Primzahltest formulieren, der wesentlich effektiver ist als auf der Grundlage der Psuedoprimzahlen.

Definition: Sei $2^{\alpha }t+1$ eine natürliche, zusammengesetzte ungerade Zahl. Sei a eine zu n teilerfremde natürliche Zahl. Wir nennen n eine starke Pseudoprimzahl zur Basis a, genau dann wenn

$a^{t}=1$ $(\func{mod}$ oder $a^{2^{\beta }t}$ $(\func{mod}$ (*)

für ein

Bemerkung: Jede starke a-Pseudoprimzahl ist eine a-Pseudoprimzahl.

Klar, nach Definition. Die Implikation lässt sich nicht umkehren: 561 eine 2-Pseudoprimzahl, aber 561 ist keine starke 2-Pseudoprimzahl (n-1=560=2⁴*35, also t=35 und α=4. 2³⁵=263, 2⁷⁰=166, 2¹⁴⁰=67, 2²⁸⁰=1).

Bemerkung: Jede Primzahl erfüllt die Bedingung (*).

Sei p eine PZ, α=1 also n=2t+1, so gilt nach Fermat:

p | a^p-1-1 = a^2t-1 = (a^t+1)(a^t-1)

Also ist a^t = +1 (mod p) oder a^t = -1 (mod p). Für &alpha>1 spaltet man das Produkt weiter auf:

p | a^p-1-1 = (a^t-1)(a^t+1)(a^2t+1)(a^4t+1)...(a^{2^(α-1)*t}+1)

Da p prim ist, teilt es genau einen der Faktoren.

Anzahl der starken Pseudoprimzahlen im Vergleich mit Pseudoprimzahlen
Glücklicherweise sind starke Pseudoprimzahlen ziemlich selten, viel seltener als Pseudoprimzahlen. Die kleinste Pseudoprimzahl zur Basis 2 ist 2047. Pommerance, Selfridge und Wagstaff veröffentlichten 1980 die folgenden Zahlen:

n	#Pseudoprimzahlen < n	#starken Pseudoprimzahlen < n
10³	3	0
10⁶	245	46
10⁹	5597	1282

Starke Pseudoprimzahlen für unterschiedliche Basen
Ebenso erfreilich ist, dass sich die starken Pseudoprimzahlen bei verschiedenen Basen unterscheiden.

Basis	starke a-Pseudoprimzahlen	OLEIS
2	2047, 3277, 4033, 4681, 8321, ...	A001262
3	121, 703, 1891, 3281, 8401, 8911, ...	A020229
4	341, 1387, 2047, 3277, 4033, 4371, ...	A020230
5	781, 1541, 5461, 5611, 7813, ...	A020231
6	217, 481, 1111, 1261, 2701, ...	A020232
7	25, 325, 703, 2101, 2353, 4525, ...	A020233
8	9, 65, 481, 511, 1417, 2047, ...	A020234
9	91, 121, 671, 703, 1541, 1729, ...	A020235

Für einen Primzahltest auf der Grundlage starker Pseudoprimzahlen, kann man verschiedene Basen kombinieren. Nach Jaeschke (1993) gilt sogar (A014233):

(n < 1.373.653 und n ist 2-SPRP und 3-SPRP) => n Primzahl

(n < 341.550.071.728.321 und n ist 2, 3, 5, 7, 11, 13, und 17-SPRP) => n Primzahl

Gibt es so 'starke Carmichael-Zahlen'?
Carmichael Zahlen sind auf der Menge der primen Restklassengruppe mod n überall pseudoprim, aber nicht prim. Starke Carmichael Zahlen, d.h. natürliche Zahlen, die bei allen teilerfremden Basen stark pseudoprim sind, aber nicht prim sind kann es nicht geben, denn:

Satz: n Primzahl <=> (Für alle Basen a teilerfremd zu n gilt: n starke a-Pseudoprimzahl)

--> neue Version!

Infos

Online Programme

Sonstiges

User Favorites

Hintergrundwissen

Starke Pseudoprimzahl zur Basis a