Lucas sahte suçu - Lucas pseudoprime

Lucas sahte suçları ve Fibonacci sahte suçları vardır bileşik belirli testleri geçen tam sayılar asal ve çok az bileşik sayı geçer: bu durumda, bazılarına göre kriterler Lucas dizisi.

Baillie-Wagstaff-Lucas sahte suçları

Baillie ve Wagstaff, Lucas'ın sahte suçlarını şu şekilde tanımlar:^[1] Verilen tam sayılar P ve Q, nerede P > 0 ve ${ displaystyle D = P ^ {2} -4Q}$,İzin Vermek U_k(P, Q) ve V_k(P, Q) karşılık gelen olmak Lucas dizileri.

İzin Vermek n pozitif bir tamsayı olsun ve ${ displaystyle sol ({ tfrac {D} {n}} sağ)}$ ol Jacobi sembolü. Biz tanımlıyoruz

${ displaystyle delta (n) = n- sol ({ tfrac {D} {n}} sağ).}$

Eğer n bir önemli öyle ki en büyük ortak böleni nın-nin n ve Q (yani, GCD (n, Q)) 1 ise, aşağıdaki eşleşme koşulu geçerlidir:

${ displaystyle U _ { delta (n)} eşdeğeri 0 { pmod {n}}.}$

(1)

Bu uyum varsa değil bekle o zaman n dır-dir değil prime.If n dır-dir bileşik, sonra bu eşleşme genelde tutmaz.^[1] Bunlar, Lucas dizilerini, asallık testi.

Uygunluk (1), a tanımlayan iki uyumdan birini temsil eder Frobenius sözde suçu. Bu nedenle, her Frobenius sözde suçu aynı zamanda bir Baillie-Wagstaff-Lucas sahte suçudur, ancak sohbet her zaman geçerli değildir.

Bazı iyi referanslar, Bressoud ve Wagon'un kitabının 8. bölümüdür ( Mathematica kodu),^[2] Crandall ve Pomerance tarafından yazılan kitabın 142–152. sayfaları,^[3] ve Ribenboim tarafından yazılan kitabın 53-74. sayfaları.^[4]

Lucas olası asal sayılar ve sahte suçlar

Bir Lucas olası asal verilen için (P, Q) çifti hiç pozitif tamsayı n hangi denklem için (1) yukarıdaki doğrudur (bkz.^[1] sayfa 1398).

Bir Lucas sahte suçu verilen için (P, Q) çift pozitiftir bileşik tamsayı n hangi denklem için (1) doğrudur (bkz.^[1] sayfa 1391).

Lucas'ın muhtemel asal testi en çok aşağıdaki durumlarda kullanışlıdır: D Jacobi sembolü olacak şekilde seçilir ${ displaystyle sol ({ tfrac {D} {n}} sağ)}$ -1'dir (bkz. sayfaların 1401-1409'u,^[1] sayfa 1024 /^[5] veya 266-269. sayfalar ^[2]). Bu, özellikle bir Lucas testini bir güçlü sözde suç test, örneğin Baillie-PSW asallık testi. Tipik olarak uygulamalar, bu koşulu sağlayan bir parametre seçim yöntemi kullanacaktır (örneğin, ^[1] ve aşağıda açıklanmıştır).

Eğer ${ displaystyle sol ({ tfrac {D} {n}} sağ) = - 1,}$ sonra denklem (1) olur

${ displaystyle U_ {n + 1} equiv 0 { pmod {n}}.}$

(2)

Uygunsa (2) yanlıştır, bu bir kanıtı oluşturur n bileşiktir.

Uygunsa (2) doğrudur, o zaman n Lucas olası bir asaldır. Bu durumda ya n asal veya Lucas sahte suçudur.2) doğrudur, o zaman n dır-dir muhtemelen asal olmak (bu, terimi haklı çıkarır muhtemel prime), ancak bu değil kanıtlamak o n Diğer olasılıksal asallık testlerinde olduğu gibi, farklı ek Lucas testleri yaparsak D, P ve Q, o zaman testlerden biri bunu kanıtlamadıkça n bileşikse, daha fazla güven kazanıyoruz n asal.

Örnekler: If P = 3, Q = −1 ve D = 13, dizisi U 's OEIS: A006190: U₀ = 0, U₁ = 1, U₂ = 3, U₃ = 10 vb.

İlk önce n = 19. Jacobi sembolü ${ displaystyle sol ({ tfrac {13} {19}} sağ)}$ 1, yani δ (n) = 20, U₂₀ = 6616217487 = 19 · 348221973 ve bizde

${ displaystyle U_ {20} = 6616217487 equiv 0 { pmod {19}}.}$

Bu nedenle, 19 bunun için Lucas olası asaldır (P, Q) çifti. Bu durumda 19 asaldır, yani öyle değil Lucas sahte suçu.

Sonraki örnek için n = 119. Elimizde ${ displaystyle sol ({ tfrac {13} {119}} sağ)}$ = −1 ve hesaplayabiliriz

${ displaystyle U_ {120} eşdeğeri 0 { pmod {119}}.}$

Bununla birlikte, 119 = 7 · 17 asal değildir, dolayısıyla 119 bir Lucas sahte suç bunun için (P, QAslında, 119 en küçük sahte suçtur. P = 3, Q = −1.

Göreceğiz altında denklemi kontrol etmek için (2) verilen için n, yaparız değil ilkinin tamamını hesaplamanız gerekiyor n + 1 terim U sıra.

İzin Vermek Q = −1, en küçük Lucas sahte suçu P = 1, 2, 3, ...

323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ...

Güçlü Lucas sahte suçları

Şimdi, faktör ${ displaystyle delta (n) = n- sol ({ tfrac {D} {n}} sağ)}$ forma ${ displaystyle d cdot 2 ^ {s}}$ nerede ${ displaystyle d}$ garip.

Bir güçlü Lucas sahte suçu verilen için (P, Q) çift tek bir bileşik sayıdır n GCD ile (n, D) = 1, koşullardan birinin karşılanması

${ displaystyle U_ {d} eşdeğeri 0 { pmod {n}}}$

veya

${ displaystyle V_ {d cdot 2 ^ {r}} eşdeğeri 0 { pmod {n}}}$

bazıları için 0 ≤ r < s; bkz. sayfa 1396.^[1] Güçlü bir Lucas sözde suçu aynı zamanda bir Lucas sahte suçudur (aynı şekilde (P, Q) çifti), ancak tersi mutlaka doğru değildir. kuvvetli test, denklemden daha katı bir asallık testidir (1).

Ayarlayabiliriz Q = −1, sonra ${ displaystyle U_ {n}}$ ve ${ displaystyle V_ {n}}$ vardır P-Fibonacci dizisi ve P-Lucas dizisi, sahte suçlar çağrılabilir temelde güçlü Lucas sahte suçu P, örneğin, en az güçlü Lucas sahte suçlu P = 1, 2, 3, ... 4181, 169, 119, ...

Bir ekstra güçlü Lucas sahte suçu^[6]bir dizi parametre için güçlü bir Lucas sahte suçudur (P, Q) nerede Q = 1, koşullardan birinin karşılanması

${ displaystyle U_ {d} equiv 0 { pmod {n}} { text {ve}} V_ {d} equiv pm 2 { pmod {n}}}$

veya

${ displaystyle V_ {d cdot 2 ^ {r}} eşdeğeri 0 { pmod {n}}}$

bazı ${ displaystyle 0 leq r$. Ekstra güçlü bir Lucas sahte suçu, aynı zamanda güçlü bir Lucas sahte suçudur. ${ displaystyle (P, Q)}$ çift.

Lucas olası asal testinin uygulanması

Olası bir asal teste başlamadan önce, genellikle n, asallık için test edilecek sayı tuhaftır, tam bir kare değildir ve uygun bir sınırdan daha küçük herhangi bir küçük asal sayı ile bölünemez. Mükemmel kareler kullanılarak tespit edilmesi kolaydır Newton yöntemi karekökler için.

Jacobi sembolünün olduğu bir Lucas sekansı seçiyoruz. ${ displaystyle sol ({ tfrac {D} {n}} sağ) = - 1}$, böylece δ (n) = n + 1.

Verilen n, seçim için bir teknik D ilkini bulmak için deneme yanılma kullanmaktır D sırayla 5, −7, 9, −11, ... öyle ki ${ displaystyle sol ({ tfrac {D} {n}} sağ) = - 1}$. Bunu not et ${ displaystyle sol ({ tfrac {k} {n}} sağ) sol ({ tfrac {-k} {n}} sağ) = - 1}$.(Eğer D ve n ortak bir ana faktöre sahipse ${ displaystyle sol ({ tfrac {D} {n}} sağ) = 0}$Bu sekansla D değerler, ortalama sayısı D Jacobi sembolü −1 olan biriyle karşılaşmadan önce denenmesi gereken değerler yaklaşık 1.79; görmek,^[1] s. 1416. D, ayarladık ${ displaystyle P = 1}$ ve ${ displaystyle Q = (1-B) / 4}$Bunu kontrol etmek iyi bir fikirdir. n ortak asal faktörleri yoktur P veya QBu seçim yöntemi D, P, ve Q tarafından önerildi John Selfridge.

(Bu arama, eğer n kare şeklindedir ve tersine, başarılı olursa, bu, n kare değil. Böylece testi geciktirerek biraz zaman kazanılabilir. n ilk birkaç arama adımının tümü başarısız olana kadar karesellik için.)

Verilen D, P, ve Qhızlı bir şekilde hesaplama yapmamızı sağlayan tekrarlama ilişkileri vardır ${ displaystyle U_ {n + 1}}$ ve ${ displaystyle V_ {n + 1}}$ içinde ${ displaystyle O ( log _ {2} n)}$ adımlar; görmek Lucas dizisi § Diğer ilişkiler. Başlamak,

${ displaystyle U_ {1} = 1}$

${ displaystyle V_ {1} = P = 1}$

İlk olarak, alt simgeyi ikiye katlayabiliriz ${ displaystyle k}$ -e ${ displaystyle 2k}$ yineleme ilişkilerini kullanarak tek adımda

${ displaystyle U_ {2k} = U_ {k} cdot V_ {k}}$

${ displaystyle V_ {2k} = V_ {k} ^ {2} -2Q ^ {k} = { frac {V_ {k} ^ {2} + DU_ {k} ^ {2}} {2}}}$.

Ardından, yinelemeleri kullanarak alt simgeyi 1 artırabiliriz

${ displaystyle U_ {2k + 1} = (P cdot U_ {2k} + V_ {2k}) / 2}$

${ displaystyle V_ {2k + 1} = (D cdot U_ {2k} + P cdot V_ {2k}) / 2}$.

Eğer ${ displaystyle P cdot U_ {2k} + V_ {2k}}$ tuhaf, bununla değiştir ${ displaystyle P cdot U_ {2k} + V_ {2k} + n}$; bu bile artık 2'ye bölünebilir. ${ displaystyle V_ {2k + 1}}$ aynı şekilde ele alınır. (Ekleme n sonucu değiştirmez modulo nBurada hesapladığımız her terim için U dizisi, karşılık gelen terimi hesaplıyoruz V sıra. İlerledikçe, aynı, karşılık gelen güçleri de hesaplıyoruz Q.

Her aşamada azaltıyoruz ${ displaystyle U}$, ${ displaystyle V}$ve gücü ${ displaystyle Q}$, mod n.

İkili açılımının bitlerini kullanıyoruz n karar vermek hangi şartlar U hesaplanacak sıra. Örneğin, eğer n+1 = 44 (= ikili olarak 101100), ardından, soldan sağa bitleri birer birer alarak, hesaplanacak indis dizisini elde ederiz: 1₂ = 1, 10₂ = 2, 100₂ = 4, 101₂ = 5, 1010₂ = 10, 1011₂ = 11, 10110₂ = 22, 101100₂ = 44. Bu nedenle, hesaplıyoruz U₁, U₂, U₄, U₅, U₁₀, U₁₁, U₂₂, ve U₄₄. Aynı numaralı terimleri de hesaplıyoruz. V sıra ile birlikte Q¹, Q², Q⁴, Q⁵, Q¹⁰, Q¹¹, Q²², ve Q⁴⁴.

Hesaplamanın sonunda hesaplamış olacağız U_{n + 1}, V_{n + 1}, ve Q^{n + 1}, (mod nDaha sonra uyumu kontrol ederiz (2) bilinen değerimizi kullanarak U_{n + 1}.

Ne zaman D, P, ve Q yukarıda açıklandığı gibi seçilirse, ilk 10 Lucas sahte suçu (bkz. sayfa 1401, ^[1]): 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179 ve 10877 (sıra A217120 içinde OEIS )

kuvvetli Lucas testinin versiyonları da benzer şekilde uygulanabilir.

Ne zaman D, P, ve Q yukarıda açıklandığı gibi seçilir, ilk 10 kuvvetli Lucas sahte suçları: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309 ve 58519 (dizi A217255 içinde OEIS )

Bir listesini hesaplamak için ekstra güçlü Lucas sahte suçları, set ${ displaystyle Q = 1}$.O zaman dene P = 3, 4, 5, 6, ..., değerine kadar ${ displaystyle D = P ^ {2} -4Q}$ Jacobi sembolünün ${ displaystyle sol ({ tfrac {D} {n}} sağ) = - 1}$Bu seçim yöntemi ile D, P, ve Q, ilk 10 ekstra güçlü Lucas sahte suçları 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059 ve 72389 (dizi A217719 içinde OEIS )

Ek uyum koşullarını kontrol etme

Bu uyumu kontrol ettiysek (2) doğruysa, neredeyse hiç ek hesaplama maliyeti olmayan kontrol edebileceğimiz ek uyum koşulları vardır. n bileşik olursa, bu ek koşullar bu gerçeği keşfetmeye yardımcı olabilir.

Eğer n garip bir asal ve ${ displaystyle sol ({ tfrac {D} {n}} sağ) = - 1}$, sonra aşağıdakine sahibiz (bkz. denklem 2, sayfa 1392, ^[1]):

${ displaystyle V_ {n + 1} equiv 2Q { pmod {n}}.}$

(3)

Bu uyum koşulu, tanımı gereği Lucas'ın olası asal testinin bir parçası olmamasına rağmen, bu koşulu kontrol etmek neredeyse serbesttir çünkü yukarıda belirtildiği gibi, V_{n + 1} hesaplama sürecinde hesaplandı U_{n + 1}.

Uygunluktan biri (2) veya (3) yanlıştır, bu bir kanıtı oluşturur n asal değil. eğer her ikisi de bu eşlemelerden biri doğruysa, o zaman daha da büyük olasılıkla n sadece uyumu kontrol ettiğimizden daha asaldır (2).

Selfridge yöntemi (yukarıda) seçmek için D, P, ve Q ayarlamak için oldu Q = −1, sonra ayarlayabiliriz P ve Q Böylece D ve ${ displaystyle sol ({ tfrac {D} {n}} sağ)}$ değişmeden kalır ve P = Q = 5 (bakınız Lucas dizisi-Cebirsel ilişkiler Bu gelişmiş yöntemi seçmek için kullanırsak P ve Q913 = 11 · 83, sadece 10'dan az kompozit⁸ hangi uyum için (3) doğrudur (bkz. sayfa 1409 ve Tablo 6;^[1]).

Eğer ${ displaystyle Q neq pm 1}$, daha sonra çok az ek hesaplama içeren başka bir uygunluk koşulu uygulanabilir.

Hatırlamak ${ displaystyle Q ^ {n + 1}}$ hesaplanırken hesaplanır ${ displaystyle U_ {n + 1}}$ve daha önce hesaplanmış gücünden kolayca tasarruf edebiliriz ${ displaystyle Q}$, yani, ${ displaystyle Q ^ {(n + 1) / 2}}$.

Eğer n asaldır, sonra Euler'in kriteri,

${ displaystyle Q ^ {(n-1) / 2} equiv sol ({ tfrac {Q} {n}} sağ) { pmod {n}}}$ .

(Buraya, ${ displaystyle sol ({ tfrac {Q} {n}} sağ)}$ ... Legendre sembolü; Eğer n asal, bu Jacobi sembolü ile aynıdır).

Bu nedenle, eğer n asal, sahip olmalıyız

${ displaystyle Q ^ {(n + 1) / 2} eşdeğeri Q cdot Q ^ {(n-1) / 2} eşdeğeri Q cdot sol ({ tfrac {Q} {n}} sağ ) { pmod {n}}.}$

(4)

Sağ taraftaki Jacobi sembolünün hesaplanması kolaydır, bu nedenle bu uyuşmayı kontrol etmek kolaydır. Bu uyuşmazsa, o zaman n asal olamaz. Sağlanan GCD (n, Q) = 1 sonra uyum testi (4), Lucas testimizi "temel Q" ile güçlendirmeye eşdeğerdir Solovay-Strassen asallık testi.

Aşağıdaki durumlarda sağlanması gereken ek uyum koşulları n asal, Bölüm 6'da açıklanmıştır.^[1] Eğer hiç bu koşulların tutmaması durumunda, bunu kanıtladık n asal değil.

Miller-Rabin asallık testi ile karşılaştırma

k uygulamaları Miller-Rabin asallık testi bileşik ilan etmek n en fazla (1/4) olasılıkla muhtemelen asal olmak^k.

Güçlü Lucas olası asal testi için benzer bir olasılık tahmini vardır.^[7]

İki önemsiz istisna dışında (aşağıya bakın), (P,Q) çiftler (modulo n) bir kompozit bildiren n muhtemelen asal olmak en fazla (4/15).

Bu nedenle, k Güçlü Lucas testinin uygulamaları bir kompozit ilan eder n en fazla olasılıkla (4/15) muhtemelen asal olmak^k.

İki önemsiz istisna vardır. Biri n = 9. Diğeri ne zaman n = p(p+2) ikinin ürünüdür ikiz asal. Bu tür bir n hesaba katmak kolaydır, çünkü bu durumda n+1 = (p+1)² mükemmel bir karedir. Mükemmel kareler kullanılarak hızlı bir şekilde tespit edilebilir Newton yöntemi karekökler için.

Lucas sözde suç testini bir Fermat asallık testi Örneğin, 2 tabanına göre, asallık için çok güçlü olasılık testleri elde edilebilir, örneğin Baillie – PSW asallık testi.

Fibonacci sahte suçları

Ne zaman P = 1 ve Q = ,1, U_n(P,Q) dizisi Fibonacci sayılarını temsil eder.

Bir Fibonacci sahte suç sıksıktır^{[2]:264,[3]:142,[4]:127}bileşik sayı olarak tanımlanır n uygunluk için 5 ile bölünemez (1) ile tutar P = 1 ve Q = −1 (ancak n dır-dir ). Bu tanıma göre, Fibonacci sahte suçları bir dizi oluşturur:

323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... (sıra A081264 içinde OEIS ).

Aşağıdaki Anderson ve Jacobsen referansları bu tanımı kullanır.

Eğer n 2 veya 3 modulo 5 ile uyumludur, sonra Bressoud,^{[2]:272–273} ve Crandall ve Pomerance^[3]:143,168 bir Fibonacci sahte suçunun aynı zamanda bir Fermat sahte suçu baz 2. Ancak, ne zaman n 1 veya 4 modulo 5 ile uyumludur, bunun tersi doğrudur, Fibonacci sahte primlerinin% 12'sinden fazlası 10'un altında¹¹ aynı zamanda base-2 Fermat sahte suçlarıdır.

Eğer n asal ve OBEB'dir (n, Q) = 1 ise, bizde ayrıca^[1]:1392

${ displaystyle V_ {n} (P, Q) eşdeğeri P { pmod {n}}.}$

(5)

Bu, Fibonacci pseudoprime'ın alternatif bir tanımına yol açar:^[8][9]

a Fibonacci sahte suç bileşik bir sayıdır n hangi uyum için (5) ile tutar P = 1 ve Q = −1.

Bu tanım, Fibonacci sahte suçlarının bir dizi oluşturmasına yol açar:

705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... (sıra A005845 içinde OEIS ),

bunlara aynı zamanda Bruckman-Lucas sahte suçlar.^[4]:129Hoggatt ve Bicknell, 1974'te bu sahte suçların özelliklerini inceledi.^[10] Singmaster bu sahte suçları 100000'e kadar hesapladı.^[11] Jacobsen bu sahte suçların 111443'ünü 10'dan az olarak listeliyor¹³.^[12]

Denklem (5) ile tanımlandığı gibi Fibonacci pseudoprimlerinin bile olmadığı gösterilmiştir.^[13][14] Bununla birlikte, Fibonacci sahte suçları bile mevcuttur (dizi A141137 içinde OEIS ) tarafından verilen ilk tanıma göre (1).

Bir güçlü Fibonacci pseudoprime bileşik bir sayıdır n hangi uyum için (5) için tutar Q = −1 ve tümü P.^[15] Takip eder^[15]:460 tuhaf bir bileşik tam sayı n güçlü bir Fibonacci sahte suçudur, ancak ve ancak:

1. n bir Carmichael numarası
2. 2(p + 1) | (n - 1) veya 2 (p + 1) | (n − p) her asal için p bölme n.

Güçlü bir Fibonacci sahte suçunun en küçük örneği 443372888629441 = 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331'dir.

Pell sahte suçları

Bir Pell sahte suç bileşik bir sayı olarak tanımlanabilir n hangi denklem için (1) yukarıdaki ile doğrudur P = 2 ve Q = −1; sekans U_n o zaman Pell dizisi. İlk sahte suçlar 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...

Bu, içindeki tanımdan farklıdır OEIS: A099011 şu şekilde yazılabilir:

${ displaystyle { text {}} U_ {n} equiv left ({ tfrac {2} {n}} sağ) { pmod {n}}}$

ile (P, Q) = (2, −1) yeniden tanımlıyor U_n olarak Pell dizisi. İlk sahte suçlar ise 169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215 ...

Üçüncü bir tanım, denklem (5) ile (P, Q) = (2, −1), sahte suçlar 169, 385, 961, 1105, 1121, 3827, 4901, 6265, 6441, 6601, 7107, 7801, 8119, ...

Referanslar

Dış bağlantılar

• Anderson, Peter G. Fibonacci Pseudoprimes, faktörleri ve giriş noktaları.
• Anderson, Peter G. 2,217,967,487 altındaki Fibonacci Pseudoprimleri ve faktörleri.
• Jacobsen, Dana Pseudoprime İstatistikleri, Tabloları ve Verileri (Lucas, Strong Lucas, AES Lucas, ES Lucas sahte suçları için veriler 10'un altında¹⁴; 10'un altındaki Fibonacci ve Pell sahte suçları¹²)
• Weisstein, Eric W. "Fibonacci Pseudoprime". MathWorld.
• Weisstein, Eric W. Lucas Pseudoprime. MathWorld.
• Weisstein, Eric W. "Güçlü Lucas Pseudoprime". MathWorld.
• Weisstein, Eric W. "Ekstra Güçlü Lucas Sahte Suçu". MathWorld.