Pseudoprime Lucas

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 januari 2020; kontroller kräver 2 redigeringar .

I talteorin består klasserna av Lucas pseudoprimer och Fibonacci pseudoprimer av Lucas-tal som klarar några test som alla primtal klarar .

Basegenskap

Betrakta Lucas-sekvenserna U n ( P , Q ) och V n ( P , Q ), där heltal P och Q uppfyller villkoret:

Om p  är ett primtal större än 2, då

och om Jacobi-symbolen

sedan delar p U p-ε .

Pseudosimple Lucas

Lucas pseudoprime [1]  är ett sammansatt tal n som delar U n-ε . (Riesel ( engelska  Riesel ) lägger till ett villkor: Jacobi-symbolen .)

I det speciella fallet med Fibonacci-sekvensen , när P = 1, Q = −1 och D = 5, är de första Lucas-pseudoprimerna 323 och 377; och båda är −1, det 324:e Fibonacci-talet är delbart med 323, och det 378:e är delbart med 377.

Ett starkt pseudoprimtal från Lucas är ett udda sammansatt tal n med (n,D)=1 och n-ε=2 rs med udda s som uppfyller ett av följande villkor:

n delar U s n delar V 2 j s

för vissa j < r . En stark Lucas pseudoprime är också en Lucas pseudoprime.

En superstark Lucas pseudoprime är en stark Lucas pseudoprime för en uppsättning parametrar ( P , Q ), där Q = 1, som uppfyller ett av de något modifierade villkoren:

n delar U s och V s , kongruent med ±2 modulo n n delar V 2 j s

för vissa j < r . En superstark Lucas pseudoprime är också en stark Lucas pseudoprime.

Genom att kombinera Lukes pseudoprimalitetstest med Fermats primalitetstest , säg modulo 2, kan mycket starka probabilistiska primalitetstester erhållas.

Pseudo-enkel Fibonacci

Pseudoprimtal Fibonacci  är ett sammansatt tal , n för vilket

V n är kongruent med P modulo n ,

där Q = ±1.

En stark pseudoprime Fibonacci kan definieras som ett sammansatt nummer som är en pseudoprime Fibonacci för alla P. Av definitionen (se Müller och Oswald) följer att:

  1. Ett udda sammansatt heltal n som också är ett Carmichael-tal
  2. 2( pi + 1) | ( n − 1) eller 2( pi + 1) | ( n − p i ) för varje primtal p i som delar n .

Den minsta starka Fibonacci-pseudoprimen är 443372888629441, som har divisorerna 17, 31, 41, 43, 89, 97, 167 och 331.

Det har föreslagits att det inte finns några ens Fibonacci-pseudoprimer [2]

Se även

Anteckningar

  1. ↑ Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprimes  // Mathematics of  Computation : journal. - 1980. - Oktober ( vol. 35 , nr 152 ). - P. 1391-1417 . - doi : 10.1090/S0025-5718-1980-0583518-6 .
  2. ↑ Somer, Lawrence. On Even Fibonacci Pseudoprimes // Applications of Fibonacci Numbers  (neopr.) / GE Bergum et al.. - Dordrecht: Kluwer, 1991. - T. 4. - S. 277-288.

Litteratur

Länkar