Pseudoprimární Lucas

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. ledna 2020; kontroly vyžadují 2 úpravy .

V teorii čísel se třídy Lucasových pseudoprimes a Fibonacciho pseudoprimes skládají z Lucasových čísel , která projdou některými testy, kterými projdou všechna prvočísla .

Základní vlastnost

Uvažujme Lucasovy posloupnosti U n ( P , Q ) a V n ( P , Q ), kde celá čísla P a Q splňují podmínku:

Pak je-li  p prvočíslo větší než 2, pak

a pokud symbol Jacobi

pak p dělí U p-ε .

Pseudojednoduchý Lucas

Lucasovo pseudoprvo [1]  je složené číslo n , které dělí U n-ε . (Riesel ( anglicky  Riesel ) přidává podmínku: symbol Jacobi .)

Ve speciálním případě Fibonacciho posloupnosti , kdy P = 1, Q = −1 a D = 5, jsou první Lucasova pseudoprima 323 a 377; a obě jsou -1, 324. Fibonacciho číslo je dělitelné 323 a 378. je dělitelné 377.

Lucasovo silné pseudoprvo je liché složené číslo n s (n,D)=1 a n-ε=2 rs s lichým s , které splňuje jednu z následujících podmínek:

n rozděluje U s n dělí V 2 j s

pro některé j < r . Silný Lucas pseudoprime je také Lucas pseudoprime.

Supersilné Lucasovo pseudoprime je silné Lucasovo pseudoprime pro sadu parametrů ( P , Q ), kde Q = 1, které splňuje jednu z mírně upravených podmínek:

n dělí U s a V s , shodné s ±2 modulo n n dělí V 2 j s

pro některé j < r . Supersilný Lucas pseudoprime je také silný Lucas pseudoprime.

Kombinací Lukeova testu pseudoprimality s Fermatovým testem primality , řekněme modulo 2, lze získat velmi silné testy pravděpodobnosti primality.

Pseudojednoduchý Fibonacci

Pseudoprvočíslo Fibonacci  je složené číslo , n pro které

Vn je kongruentní s P modulo n ,

kde Q = ±1.

Silné pseudoprvo Fibonacciho lze definovat jako složené číslo, které je pseudoprvočíslo Fibonacciho pro jakékoli P. Z definice (viz Müller a Oswald) vyplývá, že:

  1. Liché složené celé číslo n , které je také Carmichaelovým číslem
  2. 2( p i + 1) | ( n − 1) nebo 2 ( p i + 1) | ( n − p i ) pro libovolné prvočíslo p i dělící n .

Nejmenší silné Fibonacciho pseudoprvočíslo je 443372888629441, které má dělitele 17, 31, 41, 43, 89, 97, 167 a 331.

Bylo navrženo, že dokonce neexistují žádná Fibonacciho pseudoprima [2]

Viz také

Poznámky

  1. ↑ Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprimes  // Matematika  počítání : deník. - 1980. - říjen ( roč. 35 , č. 152 ). - S. 1391-1417 . - doi : 10.1090/S0025-5718-1980-0583518-6 .
  2. ↑ Somer, Lawrence. On Even Fibonacci Pseudoprimes // Aplikace Fibonacciho čísel  (neopr.) / GE Bergum et al.. - Dordrecht: Kluwer, 1991. - T. 4. - S. 277-288.

Literatura

Odkazy