Pseudoprime Lucas

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 1-jén felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A számelméletben a Lucas- pszeudoprímek és a Fibonacci-pszeudoprímek osztályai olyan Lucas-számokból állnak, amelyek megfelelnek néhány olyan tesztnek, amelyen minden prím megfelel .

Alaptulajdonság

Tekintsük az U n ( P , Q ) és V n ( P , Q ) Lucas sorozatokat , ahol a P és Q egész számok kielégítik a feltételt:

Ekkor ha p 2-  nél nagyobb prímszám , akkor

és ha a Jacobi-szimbólum

akkor p osztja U p-ε -t .

Pszeudosimple Lucas

A Lucas-pszeudoprím [1]  egy n összetett szám , amely osztja U n-ε -t . (A Riesel ( angolul  Riesel ) egy feltételt ad hozzá: a Jacobi szimbólumot .)

A Fibonacci sorozat speciális esetben , amikor P = 1, Q = -1 és D = 5, az első Lucas-pszeudoprímek 323 és 377; és mindkettő −1, a 324. Fibonacci-szám osztható 323-mal, a 378. pedig osztható 377-tel.

Egy Lucas-féle erős pszeudoprím egy páratlan összetett n szám , ahol (n,D)=1, és n-ε=2 r s páratlan s - sel , amely teljesíti a következő feltételek egyikét:

n osztja U -t n osztja V 2 j s -t

néhány j < r . Az erős Lucas-pszeudoprím egyben Lucas-pszeudoprím is.

A szupererős Lucas-pszeudoprím egy erős Lucas-pszeudoprím egy paraméterkészlethez ( P , Q ), ahol Q = 1, és amely kielégíti az egyik kissé módosított feltételt:

n osztja U s -t és V s -t, egybevágó ±2 modulo n értékkel n osztja V 2 j s -t

néhány j < r . A szupererős Lucas-pszeudoprím egyben erős Lucas-pszeudoprím is.

A Luke-féle pszeudoprimalitás- teszt és a Fermat -féle primalitásteszt kombinálásával , mondjuk a modulo 2-vel, nagyon erős valószínűségi primalitásteszteket kaphatunk.

Ál-egyszerű Fibonacci

A Fibonacci pszeudo-prím  egy összetett szám , amelyre n

V n kongruens P modulo n -al ,

ahol Q = ±1.

Egy erős pszeudoprím Fibonacci olyan összetett számként definiálható, amely bármely P pszeudoprím Fibonacci. A meghatározásból (lásd Müller és Oswald) az következik, hogy:

  1. Egy páratlan összetett n egész szám , amely egyben Carmichael-szám is
  2. 2( p i + 1) | ( n − 1) vagy 2( p i + 1) | ( n − p i ) bármely p i prímre, osztva n -t .

A legkisebb erős Fibonacci pszeudoprím a 443372888629441, amelynek 17, 31, 41, 43, 89, 97, 167 és 331 osztói vannak.

Feltételezik, hogy még Fibonacci pszeudoprímek sem léteznek [2]

Lásd még

Jegyzetek

  1. ↑ Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprimes  //  Számítási matematika : folyóirat. - 1980. - október ( 35. évf. , 152. sz.). - P. 1391-1417 . - doi : 10.1090/S0025-5718-1980-0583518-6 .
  2. ↑ Somer, Lawrence. Még Fibonacci pszeudoprímekről // Fibonacci számok alkalmazása  (neopr.) / GE Bergum et al.. - Dordrecht: Kluwer, 1991. - T. 4. - S. 277-288.

Irodalom

Linkek