İçerik

• adımlar
• Bölüm 1/3: Basitlik Testleri
• Bölüm 2/3: Basitlik Testleri Nasıl Çalışır?
• Bölüm 3/3: Çin Kalan Teoremini Kullanma
• İpuçları
• Neye ihtiyacın var

Asal sayılar yalnızca kendilerine ve 1'e bölünebilen sayılardır. Diğer tüm sayılara bileşik sayılar denir. Bir sayının asal olup olmadığını belirlemenin birçok yolu vardır ve hepsinin kendi avantajları ve dezavantajları vardır. Bir yandan, yöntemlerden bazıları çok doğrudur, ancak büyük sayılarla uğraşıyorsanız oldukça karmaşıktır. Öte yandan, çok daha hızlı yollar var, ancak yanlış sonuçlara yol açabilirler. Uygun yöntemin seçimi, üzerinde çalıştığınız sayıların ne kadar büyük olduğuna bağlıdır.

adımlar

Bölüm 1/3: Basitlik Testleri

Not: tüm formüllerde n kontrol edilecek numarayı belirtir.

1. 1 Bölenlerin numaralandırılması. bölmek yeterli n 2'den yuvarlatılmış değere kadar tüm asal sayılara (${ görüntü stili { sqrt {n}}}$).
2. 2 Fermat'ın küçük teoremi. Uyarı: bazen test, a'nın tüm değerleri için bile bileşik sayıları asal olarak tanımlayacaktır.
   • Bir tamsayı seçelim aöyle ki 2 ≤ a ≤ n - 1.
   • a (mod n) = a (mod n) ise, sayı muhtemelen asaldır. Eşitlik sağlanmazsa, n sayısı bileşiktir.
   • Birden çok değer için verilen eşitliği kontrol edin atest edilen sayının gerçekten asal olma olasılığını artırmak için.
3. 3 Miller-Rabin testi. Uyarı: bazen, nadiren de olsa, a'nın birden çok değeri için test, bileşik sayıları asal olarak yanlış tanımlayacaktır.
   • s ve d miktarlarını bulunuz. ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Bir tamsayı seçin a 2 ≤ a ≤ n - 1 aralığında.
   • a = +1 (mod n) veya -1 (mod n) ise, n muhtemelen asaldır. Bu durumda, test sonucuna gidin. Eşitlik sağlanmazsa bir sonraki adıma geçin.
   • Cevabınızı kareleyin (${ görüntü stili a ^ {2d}}$). -1 (mod n) alırsanız, n muhtemelen bir asal sayıdır. Bu durumda, test sonucuna gidin. Eşitlik başarısız olursa, tekrarlayın (${ displaystyle a ^ {4d}}$ ve benzeri) kadar ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • dışında bir sayının karesini aldıktan sonra herhangi bir adımda ${ görüntü stili pm 1}$ (mod n), +1 (mod n) elde ettiniz, yani n bir bileşik sayıdır. Eğer ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), o zaman n asal değildir.
   • Test sonucu: n testi geçerse, diğer değerler için tekrarlayın agüveni artırmak için.

Bölüm 2/3: Basitlik Testleri Nasıl Çalışır?

1. 1 Bölenlerin numaralandırılması. Tanım olarak, sayı n sadece 2'ye ve 1 ve kendisinden başka tam sayılara bölünemiyorsa basittir. Yukarıdaki formül, gereksiz adımları kaldırmanıza ve zamandan tasarruf etmenize olanak tanır: örneğin, bir sayının 3'e bölünüp bölünemeyeceğini kontrol ettikten sonra, 9'a bölünüp bölünemeyeceğini kontrol etmeye gerek yoktur.
   • Floor (x) işlevi, x'i x'ten küçük veya ona eşit en yakın tam sayıya yuvarlar.
2. 2 Modüler aritmetik hakkında bilgi edinin. "x mod y" işlemi (mod, Latince "modulo", yani "module" kelimesinin kısaltmasıdır), "x'i y'ye böl ve kalanı bul" anlamına gelir. Başka bir deyişle, modüler aritmetikte belirli bir değere ulaştıktan sonra buna denir. modül, sayılar tekrar sıfıra "döner". Örneğin, saat modül 12 ile geri sayım yapar: 10, 11 ve 12 saati gösterir ve ardından 1'e döner.
   • Birçok hesap makinesinde mod tuşu bulunur. Bu bölümün sonu, büyük sayılar için bu işlevi manuel olarak nasıl hesaplayacağınızı gösterir.
3. 3 Fermat'ın Küçük Teoreminin tuzakları hakkında bilgi edinin. Test koşullarının karşılanmadığı tüm sayılar bileşiktir, ancak sayıların geri kalanı yalnızca muhtemelen basit. Yanlış sonuçlardan kaçınmak istiyorsanız, arama yapın n "Carmichael sayıları" (bu testi karşılayan bileşik sayılar) ve "Fermat sözde asal sayılar" (bu sayılar yalnızca bazı değerler için test koşullarını karşılar) listesinde a).
4. 4 Uygunsa Miller-Rabin testini kullanın. Bu yöntem, manuel hesaplamalar için oldukça zahmetli olsa da, genellikle bilgisayar programlarında kullanılır. Fermat'ın yöntemine göre kabul edilebilir hız ve daha az hata sağlar. ¼'den fazla değer için hesaplamalar yapılırsa, bileşik sayı asal sayı olarak alınmayacaktır. a... Rastgele farklı değerler seçerseniz a ve hepsi için test olumlu bir sonuç verecektir, oldukça yüksek bir güvenle varsayabiliriz ki n bir asal sayıdır.
5. 5 Büyük sayılar için modüler aritmetik kullanın. Kullanışlı bir mod hesap makineniz yoksa veya hesap makinesi bu kadar büyük sayıları işlemek için tasarlanmadıysa, hesaplamaları kolaylaştırmak için güç özelliklerini ve modüler aritmetiği kullanın. Aşağıda için bir örnek ${ görüntü stili 3 ^ {50}}$ mod 50:
   • İfadeyi daha uygun bir biçimde yeniden yazın: ${ görüntü stili (3 ^ {25} * 3 ^ {25})}$ mod 50. Manuel hesaplamalar daha fazla basitleştirme gerektirebilir.
   • ${ görüntü stili (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ görüntü stili (3 ^ {25}}$ mod 50 ${ görüntü stili * 3 ^ {25}}$ mod 50) mod 50. Burada modüler çarpma özelliğini dikkate aldık.
   • ${ görüntü stili 3 ^ {25}}$ mod 50 = 43.
   • ${ görüntü stili (3 ^ {25}}$ mod 50 ${ görüntü stili * 3 ^ {25}}$ mod 50) mod 50 = ${ görüntü stili (43 * 43)}$ mod 50.
   • ${ görüntü stili = 1849}$ mod 50.
   • ${ görüntü stili = 49}$.

Bölüm 3/3: Çin Kalan Teoremini Kullanma

1. 1 İki sayı seçin. Sayılardan biri bileşik olmalı, diğeri ise basitlik için test etmek istediğiniz tam olarak olmalıdır.
   • Sayı1 = 35
   • Sayı2 = 97
2. 2 Sıfırdan büyük ve sırasıyla Sayı1 ve Sayı2 sayılarından daha küçük iki değer seçin. Bu değerler aynı olmamalıdır.
   • Değer1 = 1
   • Değer2 = 2
3. 3 Sayı1 ve Sayı2 için MMI'yi (Matematiksel Çarpımsal Ters) hesaplayın.
   • MMI hesaplayın
     • MMI1 = Sayı2 ^ -1 Mod Numarası1
     • MMI2 = Sayı1 ^ -1 Mod Numarası2
   • Yalnızca asal sayılar için (bu, bileşik sayılar için bir sayı verecektir, ancak bu onun MMI'sı olmayacaktır):
     • MMI1 = (Sayı2 ^ (Sayı1-2))% Sayı1
     • MMI2 = (Sayı1 ^ (Sayı2-2))% Sayı2
   • Örneğin:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Log2 modüllerine kadar her MMI için bir tablo oluşturun:
   • MMI1 için
     • F (1) = %2 Sayı1 = %97 35 = 27
     • F (2) = F (1) * F (1)% Sayı1 = 27 * %27 35 = 29
     • F (4) = F (2) * F (2)% Sayı1 = 29 * %29 35 = 1
     • F (8) = F (4) * F (4)% Sayı1 = 1 * %1 35 = 1
     • F (16) = F (8) * F (%8) Sayı1 = 1 * %1 35 = 1
     • F (32) = F (16) * F (16)% Sayı1 = 1 * %1 35 = 1
   • Eşleştirilmiş Sayıları Hesapla 1 - 2
     • 35 -2 = 33 (10001) taban 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • MMI2 için
     • F (1) = Sayı %1 Sayı2 = %35 97 = 35
     • F (2) = F (1) * F (1)% Sayı2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Sayı2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Sayı2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Sayı2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Sayı2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Sayı2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Sayı2 = 35 * 35 mod 97 = 61
   • Eşleştirilmiş Sayı 2 - 2'yi hesaplayın
     • 97 - 2 = 95 = (1011111) taban 2
     • MMI2 = ((((K (64) * K (16)% 97) * K (%8)% 97) * K (4)% 97) * K (2)% 97) * F (1)% 97)
     • MMI2 = ((((35 * 35)% 97) * 61)% 97) * %35 97) * %61 97) * %35 97)
     • MMI2 = 61
5. 5 Hesapla (Değer1 * Sayı2 * MMI1 + Değer2 * Sayı1 * MMI2) (Sayı1 * Sayı2)
   • Cevap = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Cevap = (2619 + 4270)% 3395
   • Cevap = 99
6. 6 Number1'in asal olmadığını kontrol edin
   • Hesapla (Cevap - Değer1)% Sayı1
   • 99 – 1 % 35 = 28
   • 28 0'dan büyük olduğu için 35 asal sayı değildir.
7. 7 Number2'nin asal olduğunu kontrol edin.
   • Hesapla (Cevap - Değer2)% Sayı2
   • 99 – 2 % 97 = 0
   • 0 0 olduğundan, 97 büyük olasılıkla bir asal sayıdır.
8. 8 1'den 7'ye kadar olan adımları en az iki kez daha tekrarlayın.
   • 7. adımda 0 alırsanız:
     • Sayı1 asal değilse, farklı bir Sayı1 kullanın.
     • Sayı1 asal ise başka bir Sayı1 kullanın. Bu durumda, 6. ve 7. adımlarda 0 almalısınız.
     • Farklı Anlam1 ve Anlam2 kullanın.
   • 7. adımda sürekli olarak 0 alırsanız, 2 Numaranın asal olması çok muhtemeldir.
   • Sayı1 asal değilse ve Sayı2 Sayı1'in bir böleniyse, 1'den 7'ye kadar olan adımlar hataya neden olabilir. Açıklanan yöntem, her iki sayının da asal olduğu her durumda çalışır.
   • 1'den 7'ye kadar olan adımları tekrarlamanızın nedeni, bazı durumlarda, Sayı1 ve Sayı 2 asal olmasa bile, 7. adımda 0 (bir veya her iki sayı için) elde etmenizdir. Bu nadiren olur.Başka bir Sayı1 (bileşik) seçin ve Sayı2 asal değilse, Sayı2 7. adımda sıfıra eşit olmayacaktır (Sayı1'in Sayı2'nin böleni olduğu durum dışında - burada asal sayılar 7. adımda her zaman sıfıra eşit olacaktır).

İpuçları

• 168'den 1000'e kadar olan asal sayılar: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Büyük sayılarla çalışırken kaba kuvvet testi sıkıcı bir test olmasına rağmen, küçük sayılar için oldukça etkilidir. Büyük sayılar söz konusu olduğunda bile, küçük bölenleri test ederek başlayın ve ardından sayıların basitliğini kontrol etmek için daha karmaşık yöntemlere geçin (eğer küçük bölenler bulunmazsa).

Neye ihtiyacın var

• Kağıt, kalem veya bilgisayar