İçerik

• Adım atmak
• Yöntem 1/4: Bölmeyi deneyin
• Yöntem 2/4: Fermat'ın Küçük Teoremini Kullanma
• Yöntem 3/4: Miller-Rabin Testini Kullanma
• Yöntem 4/4: Çin kalan teoremini kullanma
• İpuçları
• Gereklilikler

Asal sayılar, yalnızca kendi kendilerine bölünebilen ve 1 olarak adlandırılan sayılardır - diğer sayılar bileşik sayılar. Bir sayının asal olup olmadığını test etmek söz konusu olduğunda, birkaç seçenek vardır. Bu yöntemlerden bazıları nispeten basittir, ancak daha büyük sayılar için hiç de pratik değildir. Sıklıkla kullanılan diğer testler aslında bir teste dayalı tam algoritmalardır. olasılık Bazen yanlışlıkla bir sayıyı asal kabul eden. Bir asal sayı ile uğraşıyorsanız kendinizi nasıl test edeceğinizi öğrenmek için 1. adımı okuyun.

Adım atmak

Yöntem 1/4: Bölmeyi deneyin

Bölmeye çalışmak, bir sayıyı test etmenin en kolay yoludur. Küçük sayılar için genellikle en hızlı yoldur. Test, bir asal sayının tanımına dayanır: Bir sayı, yalnızca kendisine ve 1'e bölünebiliyorsa asaldır.

1. Varsayalım n test etmek istediğiniz sayıdır. N sayısını tüm olası bölünebilir tam sayılara bölün. N = 101 gibi daha büyük sayılar için, n'den küçük herhangi bir olası tamsayıya bölmek son derece pratik değildir. Neyse ki, test edilecek faktörlerin sayısını azaltmak için birkaç numara var.
2. Belirle n hatta. Tüm çift sayılar tamamen 2'ye bölünebilir. Bu nedenle, n çift ise, şunu söyleyebilirsiniz. n bileşik bir sayıdır (dolayısıyla asal sayı değildir). Bir sayının çift olup olmadığını hızlı bir şekilde belirlemek için, yalnızca son basamağa dikkat etmeniz gerekir. Son rakam 2, 4, 6, 8 veya 0 ise, sayı çifttir ve asal değildir.
   • Bu kuralın tek istisnası, kendisi ve 1 ile bölünebildiği için aynı zamanda asal olan 2 sayısının kendisidir. 2 tek çift asaldır.
3. Bölüm n 2 ile n-1 arasında herhangi bir sayı ile. Bir asal sayının kendisinden ve 1'den başka hiçbir çarpanı olmadığı ve tamsayı çarpanları çarpımından daha küçük olduğu için, n'den küçük ve 2'den büyük bir tamsayının bölünebilirliğini kontrol etmek, n'nin asal olup olmadığını belirleyecektir. 2'den sonra başlarız çünkü çift sayılar (2'nin katları) asal sayı olamaz. Aşağıda göreceğiniz gibi bu, test etmenin etkili bir yolu olmaktan uzaktır.
   • Örneğin, 11'in asal olup olmadığını test etmek için bu yöntemi kullanmak istersek, 11'i 3, 4, 5, 6, 7, 8, 9 ve 10'a bölerek, kalansız bir tamsayı cevabı ararız. Bu sayıların hiçbiri 11'e tam olarak uymadığına göre 11'in bir olduğunu söyleyebiliriz asal.
4. Zaman kazanmak için yalnızca sqrt'ye kadar test edin (n), yuvarlanmış. 2 ile n-1 arasındaki tüm sayıları kontrol ederek bir n sayısını test etmek hızlı bir şekilde çok zaman alabilir. Örneğin, bu yöntemle 103'ün asal olup olmadığını kontrol etmek istersek, 3, 4, 5, 6, 7 ... vb. İle 102'ye bölmemiz gerekir! Neyse ki, böyle test etmeye gerek yok. Pratikte, sadece 2 ile n'nin karekökü arasındaki faktörleri test etmek gerekir. N'nin karekökü bir sayı değilse, onu en yakın tam sayıya yuvarlayın ve bu sayıya test edin. Bir açıklama için aşağıya bakın:
   • 100'ün faktörlerini inceleyelim. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 ve 100 × 1. 10 × 10'dan sonra faktörlerin aynı olduğuna dikkat edin 10 × 10 için ise, ancak o zaman ters çevrilir. Genel olarak, n'nin sqrt (n) 'den büyük olan faktörlerini göz ardı edebiliriz çünkü bunlar sadece sqrt (n)' den küçük faktörlerin devamıdır.
   • Bir örnek deneyelim. Eğer n = 37 ise, n'nin asal olup olmadığını belirlemek için 3'ten 36'ya kadar olan tüm sayıları test etmemize gerek yoktur. Bunun yerine, 2 ile sqrt (37) (yuvarlanmış) arasındaki sayılara bakmamız gerekiyor.
     • sqrt (37) = 6.08 - bunu 7'ye yuvarlayacağız.
     • 37, 3, 4, 5, 6 ve 7 ile tamamen bölünemez ve bu yüzden emin bir şekilde bunun bir olduğunu söyleyebiliriz asal sayı dır-dir.
5. Daha da fazla zaman kazanmak için yalnızca asal çarpanları kullanıyoruz. Asal sayı olmayan faktörleri dahil etmeyerek test sürecini daha da kısaltarak yapmak mümkündür. Tanım gereği, her bileşik sayı iki veya daha fazla asal sayının çarpımı olarak ifade edilebilir. Dolayısıyla, n sayısını bileşik bir sayıya bölmek gereksizdir - bu, birkaç kez asal sayılara bölmeye eşdeğerdir. Böylece, olası faktörler listesini yalnızca sqrt (n) 'den küçük asal sayılara daraltabiliriz.
   • Bu, tüm çift faktörlerin yanı sıra asal sayıların katları olan faktörlerin atlanabileceği anlamına gelir.
   • Örneğin, 103'ün asal olup olmadığını belirlemeye çalışalım. 103'ün karekökü 11'dir (yukarı yuvarlanmıştır). 2 ile 11 arasındaki asal sayılar 3, 5, 7 ve 11'dir. 4, 6, 8 ve 10 çifttir ve 9 3'ün katıdır, asal sayıdır, bu yüzden onu atlayabiliriz. Bunu yaparak olası faktörler listemizi sadece 4 rakama indirdik!
     • 103, 3, 5, 7 veya 11 ile tamamen bölünemez, bu yüzden artık 103'ün bir olduğunu biliyoruz asal sayı dır-dir.

Yöntem 2/4: Fermat'ın Küçük Teoremini Kullanma

1640 yılında, Fransız matematikçi Pierre de Fermat, bir sayının asal olup olmadığını belirlemede çok yardımcı olabilecek bir teorem (şimdi onun adı verilmiştir) önerdi. Teknik olarak, Fermat'ın testi, bir sayının asal olmaktan çok bileşik olduğunu doğrulamayı amaçlamaktadır. Bunun nedeni, testin bir sayının bileşik olduğunu "mutlak kesinlik" ile gösterebilmesidir, ancak yalnızca bir sayının asal olduğunu "olasılıkla" gösterebilmesidir. Fermat'ın küçük teoremi, bölmeye çalışmanın pratik olmadığı durumlarda ve teoremin istisnaları olan mevcut sayıların bir listesi olduğunda kullanışlıdır.

1. Varsayalım n numara test etmek içindir. Belirli bir n sayısının asal olup olmadığını belirlemek için bu testi kullanırsınız. Bununla birlikte, yukarıda belirtildiği gibi, bu teorem bazen hatalı bir şekilde bazı bileşikleri asal olarak nitelendirebilir. Bunu dikkate almak ve aşağıda açıklanan cevabınızı kontrol etmek önemlidir.
2. Bir tam sayı seçin a 2 ile n-1 (dahil). Seçtiğiniz tam sayı önemli değildir. İçerme 2 ve n-1 için parametreler olduğundan, bunları da kullanabilirsiniz.
   • Bir örnek: 100 üssü mü değil mi? Varsayalım biz alıyoruz 3 test değeri olarak - bu 2 ile n-1 arasındadır, bu nedenle yeterlidir.
3. hesaplamak a (mod n). Bu ifadeyi çözmek, adı verilen matematiksel bir sistem hakkında biraz bilgi gerektirir. modüler matematik. Modüler matematikte, sayılar belirli bir değere ulaştığında sıfıra döner; modül. Bunu bir saat gibi düşünebilirsiniz: zamanın ibresi eninde sonunda saat 12'den sonra saat 1'e dönecektir, saat 13'e değil. Modül, (mod n). Yani bu adımda, modülü n olan a'yı hesaplıyorsunuz.
   • Diğer bir yöntem de a'yı hesaplamak, sonra onu n'ye bölmek, sonra kalanı cevabınız olarak kullanmaktır. Modül işlevine sahip özel hesap makineleri, büyük sayıları bölerken çok yararlı olabilir, çünkü bir bölümün kalanını hemen hesaplayabilirler.
   • Örneğimizde böyle bir hesap makinesi kullanarak, 3 / 100'ün 1'in kalanına sahip olduğunu görebiliriz. Yani, 3 (mod 100) 1.
4. Bunu elle hesaplarsak, üssü kısa format olarak kullanırız. Modül fonksiyonu olan bir hesap makineniz yoksa, kalanı belirleme prosedürünü kolaylaştırmak için üslü gösterimi kullanın. Aşağıya bakınız:
   • Örneğimizde 3'ü 100'lük bir modülle hesaplıyoruz. 3 çok, çok büyük bir sayıdır - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - çalışmak çok zor hale gelecek kadar büyük. 3 için 48 basamaklı cevabı kullanmaktansa üs olarak yazsak iyi olur, bu yüzden (((((((3)*3))))*3)). Bir üssün üssünü almanın üsleri çarpma etkisine sahip olduğunu unutmayın ((x) = x).
     • Şimdi gerisini belirleyebiliriz. İç parantez kümesinde ((((((3) * 3))) * 3)) 'ü çözerek başlayın ve her adımı 100'e bölerek çıkış yolunu bulun. Gerisini bulduktan sonra, bunu gerçek cevap yerine bir sonraki adım için kullanacağız. Aşağıya bakınız:
       • ((((((9) * 3))) * 3)) - 9 / 100'ün bakiyesi yok, yani devam edebiliriz.
       • (((((27)))) * 3)) - 27 / 100'ün bakiyesi yok, bu yüzden devam edebiliriz.
       • ((((729))) * 3)) - 729/100 = 7 R 29. Kalanımız 29. 729 değil, sonraki adıma devam ediyoruz.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Kalan 41'imizi bir sonraki adımda tekrar kullanıyoruz.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Bir sonraki adımda kalan 81'i kullanıyoruz.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Kalan 43'ümüzü bir sonraki adımda kullanacağız.
       • (43 = 1849) - 1849/100 = 18 R 49. Kalan 49'umuzu bir sonraki adımda kullanacağız.
       • 49 = 2401 - 2401/100 = 24 R 1. Son kalanımız 1. Diğer bir deyişle, 3 (mod 100) = 1. Bunun bir önceki adımda hesapladığımız yanıtın aynısı olduğuna dikkat edin!
5. Eğer öğrenmek a (mod n) = a (mod n). Değilse, n bileşiktir. Eğer doğruysa n muhtemelen, (ama emin değil) asal sayı. Testi a için farklı değerlerle tekrarlamak, sonucu daha kesin hale getirebilir, ancak Fermat'ın teoremini karşılayan nadir bileşik sayılar vardır. herşey a değerleri Bunlar Carmichael sayıları olarak adlandırılır - bu sayıların en küçüğü 561'dir.
   • Örneğimizde 3 (mod 100) = 1 ve 3 (mod 100) = 3.1 ≠ 3, yani 100'ün bileşik bir sayı olduğunu söyleyebiliriz.
6. Sonucunuzdan emin olmak için Carmichael sayılarını kullanın. Devam etmeden önce hangi sayıların Carmichael serisini karşıladığını bilmek, sizi bir sayının asal olup olmadığı konusunda endişelenmekten kurtarabilir. Genel olarak, Carmichael sayıları bireysel asal sayıların çarpımıdır; burada tüm asal sayılar için p, n'nin böleni ise p-1'in de n-1'in bölen olduğunu varsayar. Carmichael sayılarının çevrimiçi listesi, Fermat'ın Küçük Teoremini kullanarak bir sayının asal olup olmadığını belirlemede çok yararlı olabilir.
   
   

Yöntem 3/4: Miller-Rabin Testini Kullanma

Miller-Rabin testi, Fermat'ın küçük teoremi ile aynı şekilde çalışır, ancak Carmichael sayıları gibi standart olmayan sayılarla daha iyi ilgilenir.

1. Varsayalım n asallık için test etmek istediğimiz tek sayıdır. Yukarıda belirtilen yöntemlerde olduğu gibi, asallığını belirlemek istediğimiz değişkendir n.
2. Basınç n-1, 2 × biçiminde d hangi d garip. Tek ise n sayısı asaldır. Yani n - 1 eşit olmalıdır. N - 1 çift olduğu için tek sayının 2 katı kuvvet olarak yazılabilir. Yani, 4 = 2 × 1; 80 = 2 × 5; ve benzeri.
   • N = 321'in asal olup olmadığını belirlemek istediğimizi varsayalım. 321 - 1 = 320, bunu şu şekilde ifade edebiliriz: 2 × 5.
     • Bu durumda n = 321 uygun bir sayıdır. N = 371 için n - 1'in belirlenmesi, d için büyük bir değer gerektirebilir, bu da tüm süreci sonraki bir aşamada daha zor hale getirir. 371-1 = 370 = 2 × 185
3. Herhangi bir sayı seçin a 2 ile n-1. Seçtiğiniz tam sayı önemli değildir - sadece n'den küçük ve 1'den büyük olması gerekir.
   • N = 321 örneğimizde a = 100.
4. hesaplamak a (mod n). Eğer a = 1 veya -1 (mod n), sonra geçer n Miller-Rabin testi ve muhtemelen asal sayı. Fermat'ın Küçük Teoreminde olduğu gibi, bu test bir sayının asallığını mutlak kesinlikle belirleyemez, ancak ek testler gerektirir.
   • Örneğimizde n = 321, a (mod n) = 100 (mod 321). 100 = 10.000.000.000 (mod 321) = 313. 100 / 321'in geri kalanını bulmak için özel bir hesap makinesi veya daha önce açıklandığı gibi bir üslü stenografi yöntemi kullanıyoruz.
     • 1 veya -1 elde etmediğimiz için, n'nin asal olduğunu kesin olarak söyleyemeyiz. Ancak yine de yapmamız gereken daha çok şey var - okumaya devam edin.
5. Sonuç 1 veya -1 olmadığından hesaplayın a, a, ... ve benzeri, şuna kadar ad. 2'ye kadar d'nin kuvvetine yükseltilmiş bir hesaplayın. Bunlardan herhangi biri 1 veya -1'e eşitse (mod n), sonra geçer n Miller-Rabin testleri yapıyor ve muhtemelen birinci sınıf. N'nin testi geçtiğini belirlediyseniz, cevabınızı kontrol edin (aşağıdaki adıma bakın). N bu testlerden herhangi birinde başarısız olursa, bu bir bestelenmiş numara.
   • Bir hatırlatma olarak, örneğimizde, a'nın değeri 100, s'nin değeri 6 ve d'nin 5 olduğunu hatırlatalım. Aşağıda gösterildiği gibi test etmeye devam ediyoruz:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 veya -1. Sakince devam edin.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244,244 ≠ 1 veya -1.
     • Bu noktada durabiliriz. s - 1 = 6 - 1 = 5. Şimdi 4d = 2'ye ulaştık ve 5d'nin altında 2 çarpı d'nin kuvveti yok. Hesaplamalarımızın hiçbiri 1 veya -1 cevabını vermediğinden, n = 321 bestelenmiş numara.
6. Eğer n Miller-Rabin testini geçer, diğer değerler için tekrarlayın a. N'nin değerinin asal olabileceğini bulduysanız, testin sonucunu onaylamak için farklı, rastgele bir a değeri ile tekrar deneyin. Eğer n aslında asal ise, a'nın herhangi bir değeri için doğru olacaktır. Eğer n bir bileşik sayı ise, a'nın değerlerinin dörtte üçü için başarısız olacaktır. Bu size, kesin olduğu durumlarda Fermat'ın Küçük Teoreminden daha fazla kesinlik verir. bileşik sayılar (Carmichael sayıları) a'nın herhangi bir değeri için testi geçer.

Yöntem 4/4: Çin kalan teoremini kullanma

1. İki sayı seçin. Sayılardan biri asal değil, ikincisi asallık için test edilen sayıdır.
   • "Test Numarası1" = 35
   • Test numarası2 = 97
2. Sırasıyla sıfırdan büyük ve TestNumarası1 ve TestNumarası2'den küçük iki veri noktası seçin. Birbirlerine eşit olamazlar.
   • Veri1 = 1
   • Veri2 = 2
3. Test Numarası1 ve Test Numarası2 için MMI'yi (Matematiksel Çarpımsal Ters) hesaplayın
   • MMI hesaplayın
     • MMI1 = Test Numarası2 ^ -1 Mod Test Numarası1
     • MMI2 = Test Numarası1 ^ -1 Mod Test Numarası2
   • Yalnızca asal sayılar için (asal olmayan sayılar için bir sonuç olacaktır, ancak bu MMI değildir):
     • MMI1 = (TestNumarası2 ^ (TestNumarası1-2))% TestNumarası1
     • MMI2 = (TestNumarası1 ^ (TestNumarası-2))% TestNumarası2
   • Yani:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Modülüsün Log2'sine kadar her MMI için bir ikili tablo oluşturun
   • MMI1 için
     • F (1) = Test Numarası% 2 Test Numarası 1 =% 97 35 = 27
     • F (2) = F (1) * F (1)% Test Numarası 1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Test Numarası 1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Test Numarası 1 = 1 *% 1 35 = 1
     • F (16) = F (8) * F (8)% Test Numarası 1 = 1 *% 1 35 = 1
     • F (32) = F (16) * F (16)% Test Numarası 1 = 1 *% 1 35 = 1
   • TestNumber1 - 2'nin ikili logaritmasını hesaplayın
     • 35-2 = 33 (10001) 2 temel
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • MMI2 için
     • F (1) = Test Numarası% 1 Test Numarası2 =% 35 97 = 35
     • F (2) = F (1) * F (1)% Test Numarası2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Test Numarası2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Test Numarası2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Test Numarası2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Test Numarası2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Test Numarası2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Test Numarası2 = 35 * 35 mod 97 = 61
   • TestNumber2 - 2'nin ikili logaritmasını hesaplayın
     • 97-2 = 95 = (1011111) 2. taban
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = (((((35 * 35)% 97) * 61)% 97) *% 35 97) *% 61% 97) *% 35 97)
     • MMI2 = 61
5. Hesapla (Veri1 * TestNumarası2 * MMI1 + Veri2 * TestNumarası1 * MMI2)% (TestNumarası1 * TestNumarası)
   • Cevap = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Cevap = (2619 + 4270)% 3395
   • Cevap = 99
6. "TestNumarası1" in asal1 olmadığını kontrol edin
   • Hesapla (Cevap - Veri1)% Test Numarası1
   • 99 -1 % 35 = 28
   • 28, 0'dan büyük olduğundan, 35 asal değildir
7. TestNumarası2'nin asal olup olmadığını kontrol edin
   • Hesapla (Cevap - Veri2)% Test Numarası2
   • 99 - 2 % 97 = 0
   • 0, 0'a eşit olduğundan, 97 potansiyel bir asal sayıdır
8. 1'den 7'ye kadar olan adımları en az iki kez daha tekrarlayın.
   • 7. adım 0'a eşitse:
     • TestNumarası1 asal değilse farklı bir "TestNumarası1" kullanın.
     • TestNumarası1'in aslında asal olduğu başka bir TestNumarası1 kullanın. Bu durumda, 6. ve 7. adımlar 0'a eşittir.
     • Data1 ve data2 için farklı veri noktaları kullanın.
   • 7. adım her zaman 0'a eşitse, 2 sayısının asal sayı olma olasılığı çok yüksektir.
   • Birinci sayı asal olmadığında ve ikincisi asal olmayan sayı "Test Numarası 1" in asal çarpanı olduğunda, 1'den 7'ye kadar olan adımların bazı durumlarda yanlış olduğu bilinmektedir. Her iki sayının da asal olduğu tüm senaryolarda çalışır.
   • 1'den 7'ye kadar olan adımların tekrarlanmasının nedeni, TestNumarası1 asal olmasa ve TestNumarası2'nin asal olmasa bile, Adım 7'deki sayılardan herhangi birinin hala sıfır olduğu birkaç senaryo olmasıdır. Bu koşullar nadirdir. TestNumarası1'i asal olmayan başka bir sayıya değiştirerek, TestNumarası2 asal değilse, 7. adımda TestNumarası2 artık sıfıra eşit olmayacaktır. "TestNumarası1" in TestNumarası2'nin bir faktörü olduğu durum dışında, asal sayılar her zaman sıfır olacaktır. 7. adım.

İpuçları

• 1000'in altındaki 168 asal sayı: 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ölmeye çalışmak, daha karmaşık yöntemlerden daha yavaş olduğunda, daha küçük sayılar için yine de etkilidir. Daha büyük sayıları test ederken bile, daha gelişmiş yöntemlere geçmeden önce küçük sayıları kontrol etmek alışılmadık bir durum değildir.

Gereklilikler

• Çalışmak için kağıt, kalem, kurşun kalem ve / veya hesap makinesi