Pseudoprime Lucas

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 1. tammikuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Lukuteoriassa Lucasin pseudoalkulukujen ja Fibonaccin pseudoalkulukujen luokat koostuvat Lucas-luvuista , jotka läpäisevät joitain testejä, jotka kaikki alkuluvut läpäisevät .

Perusominaisuus

Tarkastellaan Lucas-sarjoja U n ( P , Q ) ja V n ( P , Q ), joissa kokonaisluvut P ja Q täyttävät ehdon:

Sitten jos p  on alkuluku , joka on suurempi kuin 2, niin

ja jos Jacobi-symboli

silloin p jakaa U p-ε .

Pseudosimple Lucas

Lucasin pseudoalkuluku [1]  on yhdistelmäluku n , joka jakaa U n-ε . (Riesel ( englanniksi  Riesel ) lisää ehdon: Jacobi-symboli .)

Fibonacci-sekvenssin erikoistapauksessa , kun P = 1, Q = -1 ja D = 5, ensimmäiset Lucasin pseudoalkuluvut ovat 323 ja 377; ja molemmat ovat −1, 324. Fibonacci-luku on jaollinen luvulla 323 ja 378. on jaollinen luvulla 377.

Lucasin vahva pseudoalkuluku on pariton yhdistelmäluku n , jossa (n,D)=1 ja n-ε=2 rs parittoman s :n kanssa ja joka täyttää yhden seuraavista ehdoista:

n jakaa U :n n jakaa V 2 j s:n

joillekin j < r . Vahva Lucasin pseudoalkuluku on myös Lucasin pseudoalkuluku.

Supervahva Lucas- pseudoalkuluku on vahva Lucas-pseudoalkuluku parametrijoukolle ( P , Q ), jossa Q = 1, joka täyttää yhden hieman muokatuista ehdoista:

n jakaa U s :n ja V s :n , yhtäpitävästi ±2 modulo n :n kanssa n jakaa V 2 j s:n

joillekin j < r . Supervahva Lucasin pseudoprime on myös vahva Lucasin pseudoalkuluku.

Yhdistämällä Luken pseudoprimaalisuustesti Fermatin primaalisuustestiin , esimerkiksi modulo 2:een, voidaan saada erittäin vahvoja todennäköisyystestejä.

Pseudo-yksinkertainen Fibonacci

Pseudo-alkuluku Fibonacci  on yhdistelmäluku , jolle n

V n on kongruentti P -moduulin kanssa ,

missä Q = ±1.

Vahva pseudoalkuluku Fibonacci voidaan määritellä yhdistelmäluvuksi, joka on pseudoprimi Fibonacci mille tahansa P :lle. Määritelmästä (katso Müller ja Oswald) seuraa, että:

  1. Pariton yhdistetty kokonaisluku n , joka on myös Carmichael-luku
  2. 2( p i + 1) | ( n − 1) tai 2( p i + 1) | ( n − p i ) mille tahansa alkuluvulle p i jakamalla n .

Pienin vahva Fibonaccin pseudoalkuluku on 443372888629441, jolla on jakajat 17, 31, 41, 43, 89, 97, 167 ja 331.

On ehdotettu, että edes Fibonacci-pseudoalkulukuja ei ole olemassa [2]

Katso myös

Muistiinpanot

  1. ↑ Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprimes  //  Laskennan matematiikka : päiväkirja. - 1980. - lokakuu ( osa 35 , nro 152 ) . - s. 1391-1417 . - doi : 10.1090/S0025-5718-1980-0583518-6 .
  2. ↑ Somer, Lawrence. Jopa Fibonacci -pseudoalkukirjoista // Fibonacci-lukujen sovellukset  (uuspr.) / GE Bergum et al.. - Dordrecht: Kluwer, 1991. - T. 4. - S. 277-288.

Kirjallisuus

Linkit