Pseudoprim Lucas

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 ianuarie 2020; verificările necesită 2 modificări .

În teoria numerelor, clasele de pseudoprime Lucas și pseudoprime Fibonacci constau din numere Lucas care trec unele teste pe care toate numerele prime le trec .

Proprietatea de bază

Luați în considerare șirurile Lucas U n ( P , Q ) și V n ( P , Q ), unde numerele întregi P și Q satisfac condiția:

Atunci, dacă p  este un număr prim mai mare decât 2, atunci

iar dacă simbolul Jacobi

atunci p împarte U p-ε .

Pseudosimple Lucas

Pseudoprimul Lucas [1]  este un număr compus n care împarte U n-ε . (Riesel (în engleză  Riesel ) adaugă o condiție: simbolul Jacobi .)

În cazul special al șirului Fibonacci , când P = 1, Q = −1 și D = 5, primele pseudoprime Lucas sunt 323 și 377; și ambele sunt −1, al 324-lea număr Fibonacci este divizibil cu 323, iar al 378-lea este divizibil cu 377.

Un pseudoprim puternic Lucas este un număr compus impar n cu (n,D)=1 și n-ε=2 r s cu impar s care îndeplinește una dintre următoarele condiții:

n împarte U s n împarte V 2 j s

pentru unele j < r . Un pseudoprim Lucas puternic este, de asemenea, un pseudoprim Lucas.

Un pseudoprim Lucas superputernic este un pseudoprim Lucas puternic pentru un set de parametri ( P , Q ), unde Q = 1, care satisface una dintre condițiile ușor modificate:

n împarte U s și V s , congruent cu ±2 modulo n n împarte V 2 j s

pentru unele j < r . Un pseudoprim Lucas superputernic este, de asemenea, un pseudoprim Lucas puternic.

Prin combinarea testului de pseudoprimalitate al lui Luke cu testul de primalitate al lui Fermat , să zicem modulo 2, pot fi obținute teste de primalitate probabilistice foarte puternice.

Fibonacci pseudo-simplu

Fibonacci pseudo-prim  este un număr compus , n pentru care

V n este congruent cu P modulo n ,

unde Q = ±1.

Un Fibonacci pseudoprim puternic poate fi definit ca un număr compus care este un Fibonacci pseudoprim pentru orice P. Din definiție (vezi Müller și Oswald) rezultă că:

  1. Un număr întreg compus impar n care este, de asemenea, un număr Carmichael
  2. 2( p i + 1) | ( n − 1) sau 2( p i + 1) | ( n − p i ) pentru orice prim p i împărțind n .

Cel mai mic pseudoprim Fibonacci puternic este 443372888629441, care are divizori 17, 31, 41, 43, 89, 97, 167 și 331.

S-a sugerat că nu există nici măcar pseudoprime Fibonacci [2]

Vezi și

Note

  1. ↑ Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprime  // Matematica  calculului : jurnal. - 1980. - octombrie ( vol. 35 , nr. 152 ). - P. 1391-1417 . - doi : 10.1090/S0025-5718-1980-0583518-6 .
  2. ↑ Somer, Lawrence. Despre pseudoprimele chiar Fibonacci // Aplicații ale numerelor Fibonacci  (neopr.) / GE Bergum și colab.. - Dordrecht: Kluwer, 1991. - T. 4. - S. 277-288.

Literatură

Link -uri