MəZmun

• Addımlar
• 3 -dən 1 -ci hissə: Sadəlik testləri
• 3 -dən 2 -ci hissə: Sadəlik testləri necə işləyir
• 3 -dən 3 -cü hissə: Çin Qalan Teoremindən istifadə
• İpuçları
• Sənə nə lazımdır

Baş ədədlər yalnız özlərinə və 1 -ə bölünən ədədlərdir. Bütün digər ədədlərə kompozit ədədlər deyilir. Bir ədədin əsas olub olmadığını müəyyən etməyin bir çox yolu var və bunların hamısının öz üstünlükləri və dezavantajları var. Bir tərəfdən, bəzi üsullar çox dəqiqdir, lakin çox sayda işlə məşğul olsanız olduqca mürəkkəbdir. Digər tərəfdən, daha sürətli yollar var, ancaq səhv nəticələrə səbəb ola bilərlər. Uyğun metodun seçimi, işlədiyiniz rəqəmlərin nə qədər böyük olduğuna bağlıdır.

Addımlar

3 -dən 1 -ci hissə: Sadəlik testləri

Qeyd: bütün düsturlarda n yoxlanılacaq nömrəni bildirir.

1. 1 Bölücülərin sayı. Bölmək kifayətdir n 2 -dən yuvarlaqlaşdırılmış dəyərə qədər olan bütün sadə ədədlərə (${ Displaystyle { sqrt {n}}}$).
2. 2 Fermatın kiçik teoremi. Xəbərdarlıq: bəzən test, a -nın bütün dəyərləri üçün belə, kompozit ədədləri saxta olaraq baş olaraq təyin edəcək.
   • Gəlin tam ədəd seçək abelə ki, 2 ≤ a ≤ n - 1.
   • Bir (mod n) = a (mod n) olarsa, ehtimal ki, ədəd başdır. Bərabərlik təmin edilmədikdə, n sayı kompozitdir.
   • Verilən bərabərliyi birdən çox dəyər üçün yoxlayın atest edilən sayın həqiqətən üstün olması ehtimalını artırmaq.
3. 3 Miller-Rabin testi. Xəbərdarlıq: bəzən, nadir hallarda olsa da, a -nın çoxlu dəyərləri üçün test səhv olaraq kompozit ədədləri əsas olaraq təyin edəcək.
   • S və d miqdarlarını tapın ${ Displaystyle n-1 = 2 ^ {s} * d}$.
   • Tam ədəd seçin a 2 ≤ a ≤ n - 1 aralığında.
   • Əgər a = +1 (mod n) və ya -1 (mod n) olarsa, n, ehtimal ki, baş sayılır. Bu vəziyyətdə test nəticəsinə keçin. Bərabərlik yoxdursa, növbəti addıma keçin.
   • Cavabınızı düzəldin (${ Displaystyle a ^ {2d}}$). -1 (mod n) alsanız, n, ehtimal ki, əsas ədəddir. Bu vəziyyətdə test nəticəsinə keçin. Əgər bərabərlik uğursuz olarsa, təkrarlayın (${ Displaystyle a ^ {4d}}$ və sairə) qədər ${ Displaystyle a ^ {2 ^ {s-1} d}}$.
   • Kvadrat çəkdikdən sonra bir addım başqa ${ displaystyle pm 1}$ (mod n), +1 (mod n) əldə etdiniz, buna görə n kompozit bir ədəddir. Əgər ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), onda n əsas deyil.
   • Test nəticəsi: n testdən keçərsə, digər dəyərlər üçün təkrarlayın ainamı artırmaq üçün.

3 -dən 2 -ci hissə: Sadəlik testləri necə işləyir

1. 1 Bölücülərin sayı. Tərifə görə nömrə n yalnız 2 və 1 -dən başqa bütün ədədlərə bölünmədikdə sadədir. Yuxarıdakı düstur lazımsız addımları silməyə və vaxta qənaət etməyə imkan verir: məsələn, ədədin 3 -ə bölünüb -bölünmədiyini yoxladıqdan sonra 9 -a bölünüb -bölünmədiyini yoxlamağa ehtiyac yoxdur.
   • Döşəmə (x) funksiyası x -i x -dən az və ya bərabər olan ən yaxın tamsayıya yuvarlaqlaşdırır.
2. 2 Modul hesab haqqında məlumat əldə edin. "X mod y" əməliyyatı (mod, latınca "modulo" sözünün qısaltmasıdır, yəni "modul") "x -ı y -yə bölün və qalanını tapın" deməkdir. Başqa sözlə, modul hesabda, müəyyən bir dəyərə çatdıqda, deyilən modul, ədədlər yenidən sıfıra "dönür". Məsələn, saat 12 modulu ilə geri sayılır: 10, 11 və 12 saatları göstərir və sonra 1 -ə qayıdır.
   • Bir çox kalkulyatorda mod düyməsi var. Bu hissənin sonu, bu funksiyanı çoxlu sayda əllə necə hesablayacağınızı göstərir.
3. 3 Fermatın kiçik teoreminin tələləri haqqında məlumat əldə edin. Test şərtlərinin yerinə yetirilmədiyi bütün ədədlər kompozitdir, qalan nömrələr isə yalnızdır yəqin ki sadədir. Yanlış nəticələrin qarşısını almaq istəyirsinizsə, axtarın n "Carmichael ədədləri" (bu testi təmin edən kompozit ədədlər) və "Fermat yalançı nömrələri" siyahısında (bu ədədlər yalnız bəzi dəyərlər üçün test şərtlərinə cavab verir a).
4. 4 Rahat olarsa, Miller-Rabin testindən istifadə edin. Bu üsul əl hesablamaları üçün olduqca çətin olsa da, tez -tez kompüter proqramlarında istifadə olunur. Qəbul edilən sürət və Fermat metodundan daha az səhv təmin edir. Hesablamalar ¼ -dən çox dəyərlər üçün aparılarsa, kompozit ədəd əsas ədəd kimi qəbul edilməyəcək a... Təsadüfi olaraq fərqli dəyərlər seçsəniz a və hamısı üçün testin müsbət nəticə verəcəyini, kifayət qədər yüksək bir inamla güman edə bilərik n əsas rəqəmdir.
5. 5 Böyük ədədlər üçün modul arifmetikdən istifadə edin. Əgər lazımlı bir mod kalkulyatorunuz yoxdursa və ya kalkulyator bu qədər böyük rəqəmləri idarə etmək üçün nəzərdə tutulmamışdırsa, hesablamaları asanlaşdırmaq üçün güc xüsusiyyətlərindən və modul arifmetikdən istifadə edin. Üçün bir nümunə aşağıda verilmişdir ${ Displaystyle 3 ^ {50}}$ mod 50:
   • İfadəni daha əlverişli formada yenidən yazın: ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Manual hesablamalar əlavə sadələşdirmələr tələb edə bilər.
   • ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50. Burada modul vurma xüsusiyyətini nəzərə aldıq.
   • ${ Displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ Displaystyle (43 * 43)}$ mod 50.
   • ${ Displaystyle = 1849}$ mod 50.
   • ${ Displaystyle = 49}$.

3 -dən 3 -cü hissə: Çin Qalan Teoremindən istifadə

1. 1 İki ədəd seçin. Nömrələrdən biri kompozit, digəri isə sadəlik üçün test etmək istədiyiniz rəqəm olmalıdır.
   • Sayı1 = 35
   • Sayı2 = 97
2. 2 Sıfırdan böyük və müvafiq olaraq Number1 və Number2 rəqəmlərindən az olan iki dəyər seçin. Bu dəyərlər eyni olmamalıdır.
   • Dəyər 1 = 1
   • Dəyər2 = 2
3. 3 Number1 və Number2 üçün MMI (Mathematical Multiplicative Ters) hesablayın.
   • MMI hesablayın
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • Yalnız sadə ədədlər üçün (bu, kompozit ədədlər üçün bir rəqəm verəcək, ancaq onun MMI olmayacaq):
     • MMI1 = (Sayı2 ^ (Sayı1-2))% Sayı1
     • MMI2 = (Sayı1 ^ (Sayı2-2))% Sayı2
   • Misal üçün:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Log2 modullarına qədər hər MMI üçün bir cədvəl yaradın:
   • MMI1 üçün
     • F (1) = Sayı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
   • Cütlənmiş Nömrələri 1-2 hesablayın
     • 35 -2 = 33 (10001) əsas 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • MMI2 üçün
     • 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
   • Cütlənmiş 2 - 2 sayını hesablayın
     • 97 - 2 = 95 = (1011111) əsas 2
     • 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. 5 Hesablayın (Dəyər1 * Sayı2 * MMI1 + Dəyəri2 * Sayı1 * MMI2)% (Sayı1 * Sayı2)
   • Cavab = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Cavab = (2619 + 4270)% 3395
   • Cavab = 99
6. 6 Number1 -in əsas olmadığını yoxlayın
   • Hesablayın (Cavab - Dəyər1)% Sayı1
   • 99 – 1 % 35 = 28
   • 28 0 -dan böyük olduğu üçün, 35 əsas ədəd deyil.
7. 7 2 nömrəsinin əsas olduğunu yoxlayın.
   • Hesablayın (Cavab - Dəyər2)% Sayı2
   • 99 – 2 % 97 = 0
   • 0 0 olduğu üçün 97 çox güman ki, əsas ədəddir.
8. 8 1-7 arası addımları ən azı iki dəfə təkrarlayın.
   • 7 -ci addımda 0 alsanız:
     • Sayı 1 əsas deyilsə, fərqli bir Number1 istifadə edin.
     • Başqa bir nömrə1 istifadə edin, əgər nömrə 1 başdır. Bu vəziyyətdə, 6 və 7 -ci addımlarda 0 almalısınız.
     • Fərqli Anlam1 və Məna2 istifadə edin.
   • 7 -ci addımda ardıcıl olaraq 0 alsanız, 2 nömrəsinin çox güman ki, başlıca olması mümkündür.
   • 1 -dən 7 -dək addımlar, Number1 əsas deyilsə və Number2, Number1 -in bölücüdürsə, səhvlə nəticələnə bilər. Təsvir edilən metod, hər iki ədədin hamı olduğu bütün hallarda işləyir.
   • 1 -dən 7 -yə qədər olan addımları təkrarlamağınızın səbəbi, bəzi hallarda, 1 nömrəsi və 2 nömrəsi sadə olmasa belə, 7 -ci addımda 0 (bir və ya hər iki ədəd üçün) alacaqsınız. Bu nadir hallarda olur.Başqa bir Number1 (kompozit) seçin və əgər Number2 asal deyilsə, Number2, 7 -ci addımda sıfıra bərabər olmayacaq (Number1 -in Number2 -in bölücü olması halları istisna olmaqla - burada 7 -ci addımda primerlər həmişə sıfıra bərabər olacaq).

İpuçları

• 168 ilə 1000 arasında sadə ədədlər: 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.
• Kobud qüvvə sınağı çoxlu sayda işləyərkən yorucu bir test olsa da, kiçik ədədlər üçün olduqca təsirli olur. Çox sayda olduqda belə, kiçik bölücüləri sınayaraq başlayın və sonra ədədlərin sadəliyini yoxlamaq üçün daha mürəkkəb üsullara keçin (kiçik bölücülər tapılmasa).

Sənə nə lazımdır

• Kağız, qələm və ya kompüter