k (\ រចនាប័ទ្ម k)ក្បួនដោះស្រាយជំនាន់ដែលត្រូវដាក់កម្រិតជាក់លាក់។ ការទទួលបានលេខបឋមចៃដន្យគឺជាផ្នែកសំខាន់មួយនៃនីតិវិធីទាញយកទិន្នន័យសំខាន់ៗនៅក្នុងក្បួនដោះស្រាយគ្រីបគ្រីបជាច្រើន រួមទាំង RSA និង ElGamal ។

ដោយសារតែការធ្វើតេស្តភាពសាមញ្ញ លេខធំទាមទារការវិនិយោគពេលវេលាដ៏សំខាន់ តម្រូវការនៃភាពសាមញ្ញនៃចំនួនលទ្ធផល ជារឿយៗត្រូវបានចុះខ្សោយទៅជាភាពសាមញ្ញដ៏រឹងមាំសម្រាប់ហេតុផលចៃដន្យផ្សេងៗគ្នា។ ក្បួនដោះស្រាយដែលមានស្រាប់សម្រាប់ការធ្វើតេស្ត pseudo-primality ខ្លាំងគឺជាលំដាប់នៃរ៉ិចទ័រលឿនជាងក្បួនដោះស្រាយការធ្វើតេស្តបឋមដែលគេស្គាល់ល្អបំផុត។ ក្នុងពេលជាមួយគ្នានេះ លេខដែលឆ្លងកាត់ការសាកល្បង pseudo-prime ដោយជោគជ័យដោយប្រើមូលដ្ឋានចៃដន្យជាច្រើនទំនងជាមានកម្រិតខ្ពស់ ហើយប្រូបាប៊ីលីតេនេះកើនឡើងជាមួយនឹងចំនួនមូលដ្ឋានដែលបានសាកល្បង។

តម្រូវការសម្រាប់ក្បួនដោះស្រាយ និងការអនុវត្តរបស់វា។

តម្រូវការសម្រាប់ក្បួនដោះស្រាយសម្រាប់បង្កើតលេខបឋមចៃដន្យចុះមកពីរខាងក្រោម៖

• ការចែកចាយនៃលេខបឋមលទ្ធផលគួរតែនៅជិតឯកសណ្ឋាននៅលើសំណុំទាំងអស់។ k- លេខបឋមប៊ីត។ មានវិធីជាច្រើនដើម្បីធានាថាតម្រូវការនេះត្រូវបានបំពេញ។
• ដំណើរការជំនាន់ ជាក់លាក់លេខបឋមចៃដន្យមិនអាចបង្កើតឡើងវិញបានទេ ទោះបីជាយើងដឹងពីព័ត៌មានលម្អិតនៃក្បួនដោះស្រាយ និងការអនុវត្តរបស់វាក៏ដោយ។ ជាធម្មតា តម្រូវការនេះត្រូវបានបំពេញដោយការប្រើ PRNG សុវត្ថិភាពដែលបានចាប់ផ្តើមជាមួយនឹងគន្លឹះមួយចំនួនដែលទទួលបានពីខាងក្រៅ (ឧ. មិនមែនជាផ្នែកនៃក្បួនដោះស្រាយ ឬការអនុវត្តរបស់វា)។ ឧទាហរណ៍ គន្លឹះអាចជាតម្លៃនៃមុខងារ cryptographic hash ពីឃ្លាសម្ងាត់ដែលបានស្នើសុំពីអ្នកប្រើប្រាស់។

ក្បួនដោះស្រាយធម្មតាសម្រាប់បង្កើតលេខបឋមចៃដន្យ

គ្រប់ទីកន្លែងខាងក្រោមយើងសន្មត់ថាការប្រើប្រាស់ PRNG ខ្លាំងខាងគ្រីបគ្រីប ដែលបានចាប់ផ្តើមប្រើប្រាស់ សោសម្ងាត់(ព័ត៌មានលម្អិតអាស្រ័យលើ PRNG ដែលបានប្រើ និងរបៀបដែលសោត្រូវបានទទួល និងបង្ហាញ)។

ការធ្វើតេស្តភាពសាមញ្ញ

ពិនិត្យមើល (ប្រហែលជា) បឋមនៃលេខ ទំមាន kប៊ីត អ្នកអាចធ្វើដូចនេះបាន៖

1. ត្រូវប្រាកដថា ទំមិនត្រូវបានបែងចែកដោយលេខបឋមតូចៗ 3, 5, 7, 11 ។ល។ រហូតដល់ដែនកំណត់តូចមួយចំនួន (ឧទាហរណ៍ 256) ។ ការត្រួតពិនិត្យនេះធ្វើឱ្យវាអាចកាត់បន្ថយយ៉ាងមានប្រសិទ្ធភាពនូវសំណុំជាក់ស្តែង លេខផ្សំមុននឹងពិនិត្យមើលពួកវាតាមរយៈក្បួនដោះស្រាយដែលប្រើពេលច្រើន។ ដូច្នេះ ការធ្វើតេស្តបែងចែក ទំសម្រាប់លេខបឋម 2, 3, 5 និង 7 លុបបំបាត់លេខគូទាំងអស់ និង 54% នៃលេខសេស ការធ្វើតេស្តបែងចែក ទំសម្រាប់លេខបឋមទាំងអស់រហូតដល់ 100 លុបបំបាត់ 76% នៃចំនួនសេស ហើយការធ្វើតេស្តបែងចែក ទំសម្រាប់លេខបឋមទាំងអស់រហូតដល់ 256 វាលុបបំបាត់ 80% នៃចំនួនសេស។
2. អនុវត្តការធ្វើតេស្ត Miller-Rabin យ៉ាងហោចណាស់ចំនួនជុំ k.

ប្រសិនបើលេខ ទំមិនឆ្លងកាត់ការត្រួតពិនិត្យយ៉ាងហោចណាស់មួយ - វាមិនសាមញ្ញទេ។ បើមិនដូច្នោះទេជាមួយនឹងប្រូបាបខ្ពស់ (អាស្រ័យលើចំនួនជុំ) ចំនួន ទំគឺសាមញ្ញ។

សំណង់ផ្ទាល់

ជំហាន​ទីពីរ​អាច​ត្រូវ​បាន​បង្កើន​ល្បឿន​ដោយ​គិត​តែ​លេខ​សេស ឬ​លេខ​ដែល​អាច​ប្រៀបធៀប​នឹង 1 និង 5 mod 6 ជាដើម។

(ន 1) វិធីសាស្រ្ត

(ន-1) -វិធីសាស្រ្តសម្រាប់បង្កើតលេខបឋម ប្រើចំណេះដឹងអំពីការបែងចែកបឋមនៃចំនួនមួយ។ ន-1 សម្រាប់ការធ្វើតេស្តភាពសាមញ្ញ នដោយប្រើ

Lecture_4_part_2.

ក្បួនដោះស្រាយនព្វន្ធ និងកម្មវិធីរបស់ពួកគេក្នុងការគ្រីបគ្រីប។

លេខធម្មជាតិ p ធំជាងមួយត្រូវបានគេហៅថាបឋមប្រសិនបើវាត្រូវបានបែងចែកដោយ 1 និងខ្លួនវាប៉ុណ្ណោះ។

ទ្រឹស្តីបទ (អ៊ីក្លីដ) ។ សំណុំនៃលេខបឋមគឺគ្មានកំណត់។

អនុញ្ញាតឱ្យយើងសម្គាល់ដោយ p(x) អនុគមន៍ដែលស្មើនឹងចំនួនលេខបឋម p ក្នុងចន្លោះពេល 1< x

x/lnx< p(x) < 1,106 x / ln x .

លេខបឋមគឺជាគោលគំនិតសំខាន់មួយក្នុងការគ្រីបគ្រីប។ ប្រព័ន្ធគ្រីបគ្រីបទំនើបជាច្រើនគឺផ្អែកលើលេខបឋម។ ដូច្នេះ ក្បួនដោះស្រាយសម្រាប់បង្កើតលេខបឋម និងពិនិត្យមើលភាពសំខាន់នៃលេខដែលបានបង្កើត គឺជាឧបករណ៍សំខាន់នៅពេលបង្កើតប្រព័ន្ធគ្រីប។

លេខបឋមគឺជារឿងធម្មតាណាស់។

ចំណាំថាមានលេខបឋមប្រហែល 10151 ដែលមានប្រវែងពី 1 ដល់ 512 ប៊ីតរួមបញ្ចូល ហើយចំនួនលេខបឋមតិចជាង 2512 គឺប្រហែលស្មើនឹង 2503/ សម្រាប់លេខដែលនៅជិត n ប្រូបាប៊ីលីតេនៃលេខដែលបានជ្រើសរើសដោយបំពានជាលេខបឋម។ គឺ 1/ln(n)។ ប្រសិនបើអ្នកជ្រើសរើសលេខបឋមពីរដោយចៃដន្យក្នុងចន្លោះពី 1 ដល់ 151 ប៊ីត ប្រូបាប៊ីលីតេនៃការផ្គូផ្គងលេខទាំងនេះគឺមានភាពធ្វេសប្រហែស។ លេខសំខាន់លេង

តួនាទីសំខាន់នៅក្នុង គ្រីបគ្រីបទំនើប. ប្រព័ន្ធគ្រីបលេខសាធារណៈទំនើបៗជាច្រើន (ឬមិនស៊ីមេទ្រី) ត្រូវបានបង្កើតឡើងដោយប្រើលេខសំខាន់ៗ។

សម្រាប់លេខបឋម យើងនឹងពិចារណាបញ្ហាបី៖

·ការសាងសង់លេខបឋម;

·ពិនិត្យលេខសម្រាប់ភាពសាមញ្ញ;

· កត្តាបំបែក (បំបែក) នៃលេខទៅជាកត្តាសំខាន់។

តាមពិតទៅ បញ្ហាទាំងបីនេះពិតជាឆ្លើយសំណួរមួយ៖ ថាតើលេខក្នុងសំណួរគឺសំខាន់ឬអត់។ ប៉ុន្តែសម្រាប់កិច្ចការនីមួយៗ វិធីសាស្ត្រផ្សេងៗត្រូវបានប្រើប្រាស់។ សម្រាប់បញ្ហាទីមួយ ដោយប្រើលក្ខខណ្ឌចាំបាច់នៃភាពសាមញ្ញ អ្នកអាចផ្តល់ចម្លើយដូចជា៖

· សម្រាប់ លេខដែលបានផ្តល់ឱ្យ n មិនមែនជាបឋម;

· ប្រូបាប៊ីលីតេដែលលេខដែលបានផ្តល់ឱ្យ n មិនមែនជាបឋមគឺតិចជាង លេខដែលបានផ្តល់ឱ្យអ៊ី

សម្រាប់បញ្ហាទីពីរ អ្នកអាចបង្កើតលំដាប់ជាក់លាក់នៃលេខនៃប្រភេទពិសេសមួយ។ ហើយ​សម្រាប់​លេខ​នៃ​លំដាប់​ដែល​បាន​ផ្តល់​ឲ្យ សូម​អនុវត្ត​ការ​ធ្វើ​តេស្ត​មួយ​ចំនួន​រហូត​ដល់​យើង​រក​ឃើញ​លេខ​សំខាន់​ក្នុង​ចំណោម​លេខ​ទាំង​នោះ។

ចូរយើងបង្ហាញពីនិយមន័យ ទ្រឹស្តីបទ ក្បួនដោះស្រាយមួយចំនួន ដែលទាក់ទងនឹងបញ្ហាដំណោះស្រាយ

ភារកិច្ចដែលបានកំណត់

និយមន័យ ១.លេខ Fk = 2a + 1, a = 2k, k = 0, 1, 2, … ត្រូវបានគេហៅថាលេខ Fermat ។

ទ្រឹស្តីបទ ១.លេខ Fermat n = Fk សម្រាប់ k > 0 គឺ

សាមញ្ញប្រសិនបើនិងប្រសិនបើ

និយមន័យ ២.ទុក p ជាលេខដំបូង។ លេខនៃទម្រង់ Mp = ត្រូវបានគេហៅថាលេខ Mersenne ។

ចំណាប់អារម្មណ៍លើលេខ Mersenne គឺបណ្តាលមកពីការភ្ជាប់របស់ពួកគេជាមួយនឹងលេខដ៏ល្អឥតខ្ចោះ - លេខដែលស្មើនឹងផលបូកនៃការបែងចែករបស់ពួកគេទាំងអស់ ខុសគ្នាពីលេខខ្លួនឯង។ Euclid ក៏បានបង្ហាញផងដែរ (អ្នកអាចបញ្ជាក់វាផងដែរ) ថាប្រសិនបើលេខបឋម p មានទម្រង់ Mp នោះលេខ p (p + 1) / 2 គឺល្អឥតខ្ចោះ។ ឧ.

3 = 2 2 – 1, 7 = 2 3 – 1

លេខបឋម និងតាម

កន្លែងដែល Mp គឺជាលេខ Mersenne ។ ចូរយើងចាំថាចំនួនល្អឥតខ្ចោះគឺជាចំនួនដែលស្មើនឹងផលបូកនៃផ្នែកទាំងអស់របស់វាដែលតូចជាងខ្លួនវា។

លេខ Mersenne គឺកម្រណាស់។ ក្នុងឆ្នាំ 2001 លេខ Mersenne ទីសាមសិបប្រាំបួនត្រូវបានរកឃើញសម្រាប់ p = 1,3466,917 ។

ដើម្បីពិនិត្យមើលភាពបឋមនៃលេខ Mersenne ទ្រឹស្តីបទខាងក្រោមត្រូវបានប្រើ។

ទ្រឹស្តីបទ 2. ចូរ p ជាចំនួនបឋម, p > 2, Mp =

1. ពិចារណាពីលំដាប់ L0, L1, …, ដែល

ត្រូវបានកំណត់ដោយទំនាក់ទំនង

L0 = 4, mod p, 0 ≤ j< p.

លេខ Mn គឺសំខាន់ប្រសិនបើ Lq-2 = 0 mod p ។

កំពុងពិនិត្យមើលភាពសាមញ្ញ

លេខសំខាន់គឺចាំបាច់សម្រាប់ភាគច្រើន ប្រព័ន្ធគ្រីបជាមួយនឹងសោសាធារណៈ។

សម្ភារៈទ្រឹស្តីលើបញ្ហានៃការសាងសង់លេខបឋមធំអាចត្រូវបានរកឃើញនៅក្នុងនិង។ នេះគ្រាន់តែជាការអនុវត្តជាក់ស្តែងមួយចំនួនប៉ុណ្ណោះ។

វិធីសាស្រ្តក្នុងការបង្កើតចំនួនបឋមធំ។ វិធីសាស្រ្តពីរខាងក្រោមអាចត្រូវបានប្រើដើម្បីបង្កើតចំនួនបឋមធំ:

· លេខចៃដន្យនៃការបញ្ជាទិញដែលបានផ្តល់ឱ្យត្រូវបានបង្កើត និងប្រើប្រាស់ការធ្វើតេស្តដែលមានស្រាប់

ពិនិត្យ​មើល​ថា​តើ​ពួក​គេ​ជា​មនុស្ស​សំខាន់​ឬ​អត់។

· លេខបឋមត្រូវបានបង្កើតដោយប្រើក្បួនដោះស្រាយជាក់លាក់មួយ ហើយដោយមានជំនួយពីការធ្វើតេស្តមួយចំនួន លេខត្រូវបានពិនិត្យសម្រាប់ភាពសាមញ្ញ។

ជាដំបូងសូមក្រឡេកមើលការធ្វើតេស្តដែលត្រូវបានប្រើដើម្បីអនុវត្តវិធីសាស្រ្តដំបូង។

បង្កើតលេខបឋម។

ផ្នែកសាកល្បង

មួយក្នុងចំណោមច្រើនបំផុត វិធីសាមញ្ញការពិនិត្យមើលលេខ p សម្រាប់ primality មានការបែងចែកជាលំដាប់លេខ p ដោយលេខសេសទាំងអស់ដែលមាននៅក្នុង

ចន្លោះពេល ប្រសិនបើនៅក្នុងដំណើរការនៃការបែងចែកយើងទទួលបាន លទ្ធផលទាំងមូលបន្ទាប់មកលេខ p គឺជាសមាសធាតុ។ ប្រសិនបើនៅពេលស្វែងរកលេខសេសទាំងអស់ពីចន្លោះពេល

វាមិនអាចទៅរួចទេក្នុងការបែងចែកលេខ p ទៅជាលេខទាំងនេះទាំងស្រុង បន្ទាប់មកលេខ p គឺជាលេខបឋម។ វិធីសាស្រ្តនេះ។ហៅថាផ្នែកសាកល្បង។ វិធីសាស្រ្តនេះគឺពឹងផ្អែកលើកម្លាំងពលកម្មក្នុងចំនួន ប្រតិបត្តិការនព្វន្ធហើយវាត្រូវបានប្រើជាចម្បងដើម្បីសាកល្បងលេខបឋមតូចៗ។

Sieve នៃ Eratosthenes

ប្រសិនបើយើងចង់បង្កើតតារាងនៃចំនួនបឋមទាំងអស់ក្នុងចំណោមលេខ

2, 3,…, N បន្ទាប់មកអ្នកត្រូវកាត់តាមលំដាប់លេខទាំងអស់ដែលអាចបែងចែកបាន។

·នៅថ្ងៃទី 2 លើកលែងតែ 2;

·នៅថ្ងៃទី 3 លើកលែងតែ 3;

·នៅលើ 5 លើកលែងតែ 5;

· ទៅលេខបន្ទាប់ដែលមិនត្រូវបានកាត់ចេញ

ក្រៅពីលេខនេះ;

ល. ជាលទ្ធផល ក្នុងចំណោមលេខពី 1 ដល់ N មានតែលេខបឋមប៉ុណ្ណោះនឹងនៅដដែល។ ដើម្បីអនុវត្តវិធីសាស្ត្រនេះ ត្រូវការអង្គចងចាំកុំព្យូទ័រច្រើន ប៉ុន្តែវាល្អបំផុតសម្រាប់ការចងក្រងតារាងនៃលេខបឋម។ លើសពីនេះទៅទៀត ដំណើរការពិសេសកំពុងត្រូវបានបង្កើតឡើង ដែលប្រតិបត្តិការរុះរើត្រូវបានអនុវត្តយ៉ាងមានប្រសិទ្ធភាព។

មតិយោបល់។ ការបែងចែកសាកល្បង និង Sieve នៃ Eratosthenes អាចត្រូវបានប្រើដើម្បីដោះស្រាយបញ្ហានៃកត្តាចំនួនគត់។

Sieve នៃ Eratosthenes ។

ដើម្បីស្វែងរកលេខបឋមទាំងអស់មិនធំជាងលេខដែលបានផ្តល់ឱ្យ n ដោយធ្វើតាមវិធីសាស្ត្រ Eratosthenes អ្នកត្រូវអនុវត្តជំហានដូចខាងក្រោមៈ

សរសេរចំនួនគត់ទាំងអស់ពីពីរទៅ n (2, 3, 4, ..., n) ជាប់គ្នា។

អនុញ្ញាតឱ្យអថេរ p ដំបូងស្មើនឹងពីរ - លេខបឋមទីមួយ។

កាត់ចេញពីបញ្ជីលេខទាំងអស់ពី 2p ទៅ n ដែលបែងចែកដោយ p (នោះគឺលេខ 2p, 3p, 4p, ... )

ស្វែងរកលេខដែលមិនបានឆ្លងកាត់ដំបូងធំជាង p ហើយកំណត់តម្លៃនៃអថេរ p ទៅលេខនេះ។

ធ្វើជំហានទី 3 និងទី 4 ម្តងទៀតរហូតដល់ p ធំជាង n

លេខដែលមិនឆ្លងកាត់ទាំងអស់នៅក្នុងបញ្ជីគឺជាលេខបឋម។

នៅក្នុងការអនុវត្ត, ក្បួនដោះស្រាយអាចត្រូវបានធ្វើឱ្យប្រសើរឡើងបន្តិចដូចខាងក្រោម។ នៅជំហានទី 3 លេខអាចត្រូវបានកាត់ចេញដោយចាប់ផ្តើមភ្លាមៗជាមួយលេខ p2 ពីព្រោះចំនួនសមាសធាតុទាំងអស់តិចជាងវានឹងត្រូវបានកាត់រួចហើយនៅពេលនេះ។ ហើយតាមនោះ ក្បួនដោះស្រាយអាចត្រូវបានបញ្ឈប់នៅពេលណា ទំ 2 នឹងច្រើនជាង ន.

ឧទាហរណ៍សម្រាប់ n = 20

តោះសរសេរលេខធម្មជាតិពី 2 ដល់ 20 ជាប់គ្នា៖

លេខ​ដំបូង​ក្នុង​បញ្ជី​ទី 2 គឺ​សំខាន់។ ចូរឆ្លងកាត់ស៊េរីនៃលេខ ដោយកាត់ចេញនូវលេខទាំងអស់ដែលមានគុណនឹង 2 (រៀងរាល់វិនាទី ដោយចាប់ផ្តើមដោយ 2^2 = 4)៖

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

លេខ 3 ដែលមិនឆ្លងបន្ទាប់គឺបឋម។ ចូរឆ្លងកាត់ស៊េរីនៃលេខ ដោយកាត់ចេញនូវលេខទាំងអស់ដែលមានគុណនឹង 3 (រៀងរាល់ទីបី ដោយចាប់ផ្តើមដោយ 3^2 = 9)៖

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

លេខ 5 ដែលមិនឆ្លងបន្ទាប់គឺបឋម។ ចូរឆ្លងកាត់ស៊េរីនៃលេខ ដោយកាត់ចេញនូវលេខទាំងអស់ដែលមានគុណនឹង 5 (រៀងរាល់ទីប្រាំ ចាប់ផ្តើមដោយ 5^2 = 25)។ ល។

វាចាំបាច់ក្នុងការកាត់ចេញពហុគុណនៃលេខបឋមទាំងអស់ p ដែល . ជាលទ្ធផល លេខសមាសធាតុទាំងអស់នឹងត្រូវបានកាត់ចេញ ហើយលេខបឋមទាំងអស់នឹងនៅតែមិនអាចកាត់ចេញបាន។ សម្រាប់ ន= 20 បន្ទាប់ពីកាត់ចេញគុណនៃ 3 លេខសមាសធាតុទាំងអស់ត្រូវបានកាត់ចេញ។

ទ្រឹស្តីបទរបស់វីលសុន

សម្រាប់ P ណាមួយ លក្ខខណ្ឌខាងក្រោមគឺសមមូល៖

១). P - សាមញ្ញ;

២). (P-1)!=-1 (mod P)

មិនមានប្រសិទ្ធភាពដោយសារអាំងតង់ស៊ីតេពលកម្មខ្ពស់។

Fermat's Little Theorem ចែងថា if នសាមញ្ញ, បន្ទាប់មកលក្ខខណ្ឌគឺពេញចិត្ត: សម្រាប់ទាំងអស់គ្នា កពី (1, 2, …, ន−១) ការប្រៀបធៀបកើតឡើង

មួយ−1 ≡ 1 (mod ន) (1)

ពីទ្រឹស្តីបទនេះ វាធ្វើតាមថា ប្រសិនបើការប្រៀបធៀប (1) មិនពេញចិត្តសម្រាប់ចំនួនយ៉ាងហោចណាស់មួយ។ កនៅចន្លោះពេល (1, 2, ..., ន−1) បន្ទាប់មក ន- សមាសធាតុ។ ដូច្នេះ យើងអាចស្នើការធ្វើតេស្តបឋមប្រូបាប៊ីលីស្ត ដូចខាងក្រោម៖

ជ្រើសរើសលេខចៃដន្យ កពី (1, 2, …, នក, ន) = 1;

ន- សមាសធាតុ";

ពិនិត្យមើលលទ្ធភាពនៃការប្រៀបធៀប (1);

ប្រសិនបើការប្រៀបធៀបមិនត្រូវបានអនុវត្ត នោះចម្លើយគឺ " ន- សមាសធាតុ";

ប្រសិនបើការប្រៀបធៀបត្រូវបានធ្វើឡើង នោះចម្លើយគឺមិនស្គាល់ ប៉ុន្តែអ្នកអាចធ្វើតេស្តម្តងទៀត។

លេខ Carmichael

អ្វីដែលហៅថាលេខ Carmichael គឺអាក្រក់ជាពិសេសសម្រាប់ការធ្វើតេស្ត Fermat ។ ពួកគេមានទ្រព្យសម្បត្តិដូចខាងក្រោម: សម្រាប់ណាមួយ។ កបែបនោះ ( ក, ន) = 1 ត្រឹមត្រូវ។

លេខ Carmichael បីដំបូងគឺ: 561, 1105, 1729។ ក្នុងចំណោមលេខ 100,000,000 ដំបូងមានត្រឹមតែ 255 ប៉ុណ្ណោះ។ ថ្មីៗនេះ (1994) វាត្រូវបានបង្ហាញថាមានចំនួនគ្មានកំណត់នៃលេខបែបនេះ។

ការធ្វើតេស្តប្រូបាប៊ីលីតេរបស់ Miller-Rabin

អនុញ្ញាតឱ្យ ន- សេសនិង ន − 1 = 2ស្ត, t- សេស។

ប្រសិនបើលេខ នគឺសាមញ្ញ បន្ទាប់មកសម្រាប់ទាំងអស់គ្នា ក> 1 ការប្រៀបធៀបត្រូវបានអនុវត្ត

មួយ−1 ≡ 1 (mod ន)

ដូច្នេះការពិចារណាលើធាតុ ( នៅ, ក 2t, …, ក 2ស−1t) គេ​អាច​សម្គាល់​ឃើញ​ថា​ក្នុង​ចំណោម​ពួក​គេ​មាន​ចំនួន​ស្មើ​នឹង −1 (mod ន) ឬ នៅ≡ 1 (mod ន).

ការធ្វើតេស្តបឋម probabilistic ខាងក្រោមគឺផ្អែកលើការកត់សម្គាល់នេះ៖

ជ្រើសរើសលេខចៃដន្យ កពីចន្លោះពេល (1, 2, ..., ន−1) និងដោយប្រើក្បួនដោះស្រាយ Euclidean យើងពិនិត្យមើលលក្ខខណ្ឌ ( ក, ន) = 1;

ប្រសិនបើវាមិនត្រូវបានបំពេញ នោះចម្លើយគឺ " ន- សមាសធាតុ";

គណនា នៅ(ម៉ូដ ន);

ប្រសិនបើ នៅ≡ ± 1 (mod ន) បន្ទាប់មកទៅកាន់ជំហានទី 1;

គណនា ក 2t, …, ក 2ស−1tរហូតដល់ −1 លេចឡើង;

ប្រសិនបើគ្មានលេខទាំងនេះស្មើនឹង −1 នោះចម្លើយគឺ " ន- សមាសធាតុ";

ប្រសិនបើយើងបានឈានដល់ −1 នោះចម្លើយគឺមិនស្គាល់ (ហើយការធ្វើតេស្តអាចត្រូវបានធ្វើម្តងទៀតម្តងទៀត) ។

ចំនួនសមាសធាតុនឹងមិនត្រូវបានកំណត់ថាជាសមាសធាតុដែលមានប្រូបាប៊ីលីតេ 1 ⁄ 4. (សូមមើល)។

ទ្រឹស្តីបទ

ប្រសិនបើសម្មតិកម្ម Riemann ដែលបានពង្រីកគឺជាការពិត នោះវាគ្រប់គ្រាន់ដើម្បីពិនិត្យមើលអ្វីៗទាំងអស់។ កពី (2, 3, ..., +1) (សូមមើល) ។

ការសាងសង់លេខបឋមធំ ៗ ។

ការធ្វើតេស្តផ្អែកលើទ្រឹស្តីបទតិចតួចរបស់ Fermat

ទ្រឹស្ដីតូចរបស់ Fermat ចែងថា ប្រសិនបើ n ជាលេខបឋម នោះលក្ខខណ្ឌគឺពេញចិត្ត៖ សម្រាប់រាល់ О (2,3, …, n – 1) ការប្រៀបធៀប An - 1 º 1 mod n ទទួលបាន។

ដោយផ្អែកលើទ្រឹស្តីបទនេះ គេអាចបង្កើតក្បួនដោះស្រាយ probabilistic សម្រាប់ពិនិត្យភាពបឋមនៃចំនួន n ។

ប្រសិនបើចំនួនគត់ a ពីចន្លោះពេលទំនាក់ទំនង a - 1 º 1 mod n មិនជាប់ នោះលេខ n គឺជាសមាសធាតុ។ ប្រសិនបើទ្រឹស្តីបទគឺពិត នោះការសន្និដ្ឋានថាលេខ n ជាបឋមមិនអាចបង្កើតបានទេ ព្រោះទ្រឹស្តីបទផ្តល់តែ លក្ខខណ្ឌចាំបាច់. ដូច្នេះប្រសិនបើ

សម្រាប់ទំនាក់ទំនងមួយចំនួនដែល a - 1 º 1 mod n កាន់ បន្ទាប់មកលេខ n ត្រូវបានគេនិយាយថាជា pseudoprime ទៅមូលដ្ឋាន a ។ មាន​ចំនួន​គូ a និង n ជា​ច្រើន​ឥត​កំណត់ ដែល n ជា​សមាសធាតុ និង pseudoprime ។ ជាទូទៅសម្រាប់ a> 1 ណាមួយមាន pseudoprimes ជាច្រើនគ្មានកំណត់ដោយផ្អែកលើ a. ជាទូទៅ សេចក្តីថ្លែងការណ៍ពីរខាងក្រោមគឺពិត។ ប្រសិនបើគូ (2, n) ពេញចិត្តការប្រៀបធៀប an-1 º 1 mod n នោះគូនៃលេខ (2, 2n - 1) ក៏ពេញចិត្តវាដែរ។

· សម្រាប់លេខបឋមណាមួយ n និង a > 2 នោះ (a2 - 1, n) = 1 លេខ (a2n - 1)/(a2 - 1) គឺជា pseudoprime ទៅមូលដ្ឋាន a ។

និយមន័យ។ លេខសមាសធាតុ n ដែលការប្រៀបធៀបមួយ - 1 º 1 mod n ជាការពិតនៅក្នុងមូលដ្ឋានទាំងអស់ត្រូវបានគេហៅថាលេខ Carmichael ។

ផ្តល់លេខ n និងប៉ារ៉ាម៉ែត្រ g = 1 សម្រាប់កំណត់អត្តសញ្ញាណ

ពិនិត្យលទ្ធផល។

1) រួចរាល់ ការជ្រើសរើសដោយចៃដន្យចំនួនគត់ a ពីចន្លោះពេល;

2) ដោយប្រើក្បួនដោះស្រាយ Euclidean GCD សម្រាប់លេខ a និង n ត្រូវបានគណនា។

3) ប្រសិនបើ gcd ធំជាង 1 នោះជំហានទី 7 ត្រូវបានអនុវត្ត។

4) សម្រាប់លេខ a ការប្រៀបធៀប a - 1 º 1 mod n ត្រូវបានគូសធីក។

5) ប្រសិនបើការប្រៀបធៀបមិនត្រូវបានអនុវត្តទេនោះប៉ារ៉ាម៉ែត្រ g = 0 (ចំនួនសមាសធាតុ) ត្រូវបានកំណត់សូមចូលទៅកាន់ជំហានទី 7 ។

6) ប្រសិនបើការប្រៀបធៀបត្រូវបានបញ្ចប់ នោះការធ្វើតេស្តអាចត្រូវបានធ្វើម្តងទៀត។

7) បង្ហាញលទ្ធផលនៃការត្រួតពិនិត្យ (g = 0 - លេខផ្សំ) ។

នៅពេលដែលក្បួនដោះស្រាយត្រូវបានបញ្ចប់វាអាចទៅរួច ការសន្និដ្ឋានដូចខាងក្រោម:

· លេខ n - សមាសធាតុ (g = 0);

· ប្រសិនបើ g = 1 នោះលេខ n ជាបឋម ឬសមាសធាតុ និងជាលេខ Carmichael ។

វាជាការសមរម្យក្នុងការកត់សម្គាល់នៅទីនេះថាលេខ Carmichael គឺកម្រណាស់។ ដូច្នេះមានតែ 2,163 លេខ Carmichael ដែលមិនលើសពី 25,000,000,000 ហើយមានតែ 16 លេខដែលមិនលើសពី 100,000 ។

ដ្យាក្រាមក្បួនដោះស្រាយដោយផ្អែកលើទ្រឹស្តីបទតិចតួចរបស់ Fermat

សូមឱ្យ p ជាលេខសេស។ យើងត្រូវពិនិត្យមើលថាតើលេខ p ជាបឋមឬអត់។

1. លេខចៃដន្យ a តិចជាង p ត្រូវបានជ្រើសរើស។

2. ប្រសិនបើ GCD (a, p) ¹ 1 នោះ p គឺជាលេខផ្សំ។

3. ការប្រៀបធៀប L(a, p) º a(p - 1)/2 mod p ត្រូវបានគណនា។

4. និមិត្តសញ្ញា Jacobi J(a, p) ត្រូវបានគណនា។

5. ប្រសិនបើ L(a, p) ¹ J(a, p) នោះ p គឺជាលេខផ្សំ។

6. ប្រសិនបើ L(a, p) = J(a, p) នោះប្រូបាប៊ីលីតេនោះ។

លេខ p - សមាសធាតុមិនលើសពី 50% ។

ប្រសិនបើការធ្វើតេស្តត្រូវបានធ្វើម្តងទៀត k ដង នោះប្រូបាប៊ីលីតេ

ការពិតដែលថា p គឺជាចំនួនសមាសធាតុមិនលើសពី 1/2k ។

ការធ្វើតេស្ត Rabin-Miller

ហេតុផលសម្រាប់ក្បួនដោះស្រាយ Rabin-Miller អាចជា

ស្វែងរកក្នុង។ នៅទីនេះយើងនឹងផ្តល់ឱ្យតែទូទៅបំផុត

ការពិចារណា។ វាត្រូវបានគេដឹងថាប្រសិនបើលេខ p ជាបឋមបន្ទាប់មក

សមីការ x2 º 1 mod p មានដំណោះស្រាយតែពីរប៉ុណ្ណោះ៖ x º ± 1

ម៉ូដទំ។ ដូច្នេះ សូមឲ្យ p ជាចំនួនគត់សេសនោះ។

ត្រូវការពិនិត្យមើលភាពសាមញ្ញ។ ប្រសិនបើ p គឺជាបឋមបន្ទាប់មកដោយ

ទ្រឹស្តីបទរបស់ Fermat សម្រាប់ចំនួនគត់ណាមួយ a coprime ជាមួយ

p ការប្រៀបធៀប am - 1 º 1 mod p ត្រូវបានអនុវត្ត។ ចាប់តាំងពីទំ - ១ -

គឺស្មើ បន្ទាប់មកយើងទទួលបាន a(m - 1)/2 º ±1 mod ទំ។ ប្រសិនបើវាប្រែចេញ

នោះ (m - 1)/2 គឺស្មើ បន្ទាប់មកយើងអាចនិយាយឡើងវិញនូវហេតុផល

ដែលយើងទទួលបាននោះ a(m - 1)/4 º ±1 mod p ។ល។

ដូច្នេះ​ដើម្បី​ពិនិត្យ​មើល​ភាព​ដើម​នៃ​សេស

លេខ p ជ្រើសរើសលេខ a ដោយចៃដន្យ

ចន្លោះពេល ហើយគណនា a t (mod p), a 2 t (mod p0, ..., a bt (mod p) ដែល t ជាសេស និងលេខ b = 2s ។ ប្រសិនបើលេខមួយក្នុងចំណោមលេខទាំងនេះមិនស្របគ្នាជាមួយ +1 ឬ -1 បន្ទាប់មក​យើង​អាច​សន្និដ្ឋាន​បាន​ថា​លេខ p គឺជា​លេខ​ផ្សំ​ប្រសិនបើ​តម្លៃ​នៃ​លេខ​ត្រូវគ្នា​នឹង +1 ឬ -1 នោះ​យើង​ធ្វើ​តេស្ត​នេះ​ម្តងទៀត k ដង​ លេខសមាសធាតុ p នឹងមិនត្រូវបានកំណត់មិនលើសពី 1/ .

គ្រោងការណ៍នៃក្បួនដោះស្រាយ Rabin-Miller

សូមឱ្យ p ជាលេខសេស។ យើងត្រូវពិនិត្យមើលថាតើលេខ p ជាបឋមឬអត់។ បន្ទាប់មក សន្មត់ថា p − 1 = 2st ។

1. ជ្រើសរើសលេខចៃដន្យ a តិចជាង p និង

យើងកំណត់ k = 0 ។

2. ដោយប្រើក្បួនដោះស្រាយ Euclidean យើងគណនា gcd នៃចំនួនពីរ a និង p ។ ប្រសិនបើ GCD (a, p) ¹ 1 នោះ p គឺជាលេខផ្សំ។

3. គណនា b º នៅ mod p ។ ប្រសិនបើ b = 1 ឬ b = p − 1 នោះ p គឺប្រហែលជាបឋម។

4. ប្រសិនបើ b¹ 1 និង b ¹ p − 1 បន្ទាប់មកគណនា b º b2 mod p និង k = k + 1 ។

5. ប្រសិនបើលេខ b = p − 1 នោះលេខ p ប្រហែលជាបឋម។

ទៅកាន់ជំហានទី 7 ។

6. ខណៈពេលដែល k< s выполнять пункт 4.

7. បំពេញក្បួនដោះស្រាយ។

សូមក្រឡេកមើលឧទាហរណ៍។

ឧទាហរណ៍។

ចូរ p = 181. យើងមាន p − 1 = 45 ´ 22. ដោយ

យើងកំណត់តម្លៃនៃការរលួយដែលបានបង្ហាញ

ប៉ារ៉ាម៉ែត្រ t = 45 ។

1. ជ្រើសរើសលេខចៃដន្យ a = 52< p, и

យើងកំណត់ k = 0 ។

2. យើងប្រើក្បួនដោះស្រាយ Euclidean ដើម្បីគណនា

GCD នៃលេខពីរ 52 និង 181៖

ចែកលេខ 181 ដោយលេខ 52 យើងទទួលបាន 181 = 52 ·

ចែកលេខ 52 ដោយលេខ 25 យើងទទួលបាន 52 = 25 2

ចែកលេខ 25 ដោយលេខ 2 យើងទទួលបាន 25 = 12 2 +

ចែកលេខ 2 ដោយលេខ 1 យើងទទួលបាន 2 = 1 · 2 + 0; យើងឃើញថា gcd នៃលេខពីរ 181 និង 52 គឺស្មើនឹង 1 ។

ដោយសារ GCD មិនអនុញ្ញាតឱ្យយើងកំណត់ថាតើលេខ 181 ជាសមាសធាតុទេ យើងបន្តអនុវត្តក្បួនដោះស្រាយ Rabin-Miller ។

3. យើងគណនាតាមលំដាប់លំដោយ

b º 52t mod 181 º 5245 mod 181៖

522 mod 181º 2704 mod 181º 170 mod 181,

524 mod 181º 1702 mod 181º 28900 mod 181º

528 mod 181º 1212 mod 181º 14641 mod 181º

5216 mod 181º 1612 mod 181º 25921 mod 181º

5232 mod 181º 382` mod 181º 1444 mod 181º

5240 mod 181º (5232 mod 181)(528 mod 181)º

º (177 ´ 161) mod 181 º 28497 mod 181 º 80 mod

5241 mod 181º (5240 mod 181)(52 mod 181)º (80 ´

º 4160 mod 181 º 178 mod 181,

5245 mod 181º (5241 mod 181)(524 mod 181)º (178´

º 21538 mod 181 = 180 mod 181 ។

ដូច្នេះយើងទទួលបាន b = 180 = p − 1. វាធ្វើតាមនោះ។

លេខ p = 181 ប្រហែលជាបឋម។

មតិយោបល់។

ដើម្បីបង្កើតលេខបឋមតូចៗ ការគណនាគឺពិបាកណាស់។ ដូច្នេះសម្រាប់ចំនួនពិតប្រាកដ ដោយមិនសង្ស័យ ការត្រួតពិនិត្យស្រដៀងគ្នា

លេខសម្រាប់ភាពសាមញ្ញត្រូវធ្វើដោយប្រើកម្មវិធីនៅលើកុំព្យូទ័រ។

ការណែនាំខ្លះត្រូវបានផ្តល់ឱ្យលើការបង្កើតលេខបឋមសម្រាប់ការអនុវត្តជាក់ស្តែង។ មគ្គុទ្ទេសក៍នេះពុះចុះទៅពីរបីជំហាន

1. បង្កើតលេខចៃដន្យ n-bit p ។

2. កំណត់ប៊ីតសំខាន់ៗ និងតិចបំផុតទៅ 1 ។

ប៊ីតដ៏សំខាន់បំផុតក្នុងករណីនេះធានានូវប្រវែងដែលត្រូវការនៃចំនួនបឋម ហើយការធានាប៊ីតដ៏សំខាន់តិចបំផុត។

ភាពចម្លែករបស់វា។

3. ត្រូវប្រាកដថាលេខ p មិនត្រូវបានបែងចែកដោយលេខបឋមតូចៗ 3, 5, 7, 11 ។ល។

ការធ្វើតេស្តសម្រាប់ការបែងចែកនៃលេខបឋមទាំងអស់តិចជាង 2000 គឺអាចទុកចិត្តបាន។

4. អនុវត្តការធ្វើតេស្ត Rabin-Miller សម្រាប់លេខចៃដន្យមួយចំនួន a ។ ប្រសិនបើ p ឆ្លងកាត់ការសាកល្បង បន្ទាប់មកបង្កើតលេខចៃដន្យមួយទៀត a ហើយធ្វើតេស្តម្តងទៀត។ សម្រាប់ការអនុវត្តជាក់ស្តែង វាគ្រប់គ្រាន់ក្នុងការធ្វើការធ្វើតេស្ត Rabin-Miller ម្តងទៀតចំនួនប្រាំដង។

5. ប្រសិនបើ p មិនឆ្លងកាត់ការធ្វើតេស្តណាមួយទេ អ្នកត្រូវបង្កើតលេខ p មួយទៀត ហើយធ្វើម្តងទៀត

សៀវភៅណែនាំនេះម្តងទៀត។

លេខ p មួយទៀត ប្រសិនបើវាមិនមែនជាបឋម អាចទទួលបានដោយមិនចាំបាច់បង្កើតលេខថ្មី ប៉ុន្តែតាមលំដាប់លំដោយឆ្លងកាត់ចំនួនគត់ទាំងអស់ ដោយចាប់ផ្តើមពី p + 1 p + 2 ។ល។ រហូតដល់លេខបឋមត្រូវបានរកឃើញ។ .

ឥឡូវនេះ ចូរយើងបន្តទៅសំណួរនៃការបង្កើតលេខសំខាន់ៗ។

ការសាងសង់លេខបឋមធំ និងក្បួនដោះស្រាយកំណត់សម្រាប់ពិនិត្យលេខ

ភាពសាមញ្ញ/

សូមក្រឡេកមើលវិធីមួយផ្សេងទៀតដើម្បីបង្កើតលេខបឋម។ វិធីសាស្រ្តនេះគឺផ្អែកលើនីតិវិធីជាក់លាក់មួយសម្រាប់បង្កើតលេខបឋម ដែលត្រូវបានផ្ទៀងផ្ទាត់ដោយប្រើការធ្វើតេស្តបឋម។

វិធីសាស្រ្តនេះត្រូវបានគេប្រើឧទាហរណ៍នៅក្នុងស្តង់ដារ

អេឡិចត្រូនិក ហត្ថលេខាឌីជីថល(EDS) GOST R 34.10–94 និង

គឺផ្អែកលើទ្រឹស្តីបទខាងក្រោម។

ទ្រឹស្តីបទ ៥.

សូម p = qN + 1 ដែល q ជាសេស

លេខបឋម N - លេខគូ និងទំ< (2q + 1)2. Число p

វាសាមញ្ញប្រសិនបើលក្ខខណ្ឌពីរត្រូវបានបំពេញ:

1) 2qN = 1 mod ទំ;

2) 2N ≠ 1 mod ទំ។

ការបង្កើតលេខបឋមដោយប្រើទ្រឹស្តីបទ 5 ត្រូវបានអនុវត្តក្នុងលក្ខណៈសាមញ្ញបន្តិច ស្តង់ដារទទួលយកគ្រោងការណ៍ អនុញ្ញាតឱ្យវាត្រូវបានទាមទារ

បង្កើតជាលេខបឋម p នៃប្រវែង t ≥ 17 ប៊ីត។ ចំពោះគោលបំណងនេះ លំដាប់ថយចុះនៃលេខ (ti) ត្រូវបានសាងសង់ ដែល i = 0, 1, …, s, ដែល t0 = t, ti = ។

រូបមន្ត pi - 1 = piN + 1 ដែលលេខ N បំពេញលក្ខខណ្ឌដូចខាងក្រោមៈ

· N - គូ;

N - ដូចជាប្រវែងនៃលេខ pi - 1 = piN + 1 in

ភាពត្រឹមត្រូវគួរតែស្មើនឹង ti - 1 ។

ស្តង់ដារ GOST ផ្តល់នូវក្បួនដោះស្រាយជាក់លាក់សម្រាប់ការគណនាលេខ N. សម្រាប់កំណែអប់រំ N -

លេខគូចៃដន្យដែលទទួលបានដោយប្រើឧបករណ៍ចាប់សញ្ញា លេខចៃដន្យ(ប្រសិនបើ N ជាសេស នោះ N = N + 1) ។

លេខ pi - 1 ត្រូវបានគេចាត់ទុកថាទទួលបានប្រសិនបើលក្ខខណ្ឌទាំងពីរខាងក្រោមត្រូវបានបំពេញក្នុងពេលដំណាលគ្នា:

1) 2b = 1 mod pi, b = pi − 1N;

2) 2N ≠ 1 mod pi ។

ប្រសិនបើយ៉ាងហោចណាស់លក្ខខណ្ឌមួយមិនត្រូវបានបំពេញនោះតម្លៃនៃលេខ N ត្រូវបានកើនឡើងដោយ 2 ហើយត្រូវបានគណនា

តម្លៃថ្មីនៃ pi គឺ 1 ដែលត្រូវបានសាកល្បងម្តងទៀតសម្រាប់ភាពបឋមក្រោមលក្ខខណ្ឌពីរ។ ដំណើរការនេះបន្តរហូតដល់ទទួលបានលេខបឋម pi - 1 (ឧ. លក្ខខណ្ឌ 1 និង 2 នៃក្បួនដោះស្រាយការបង្កើតលេខបឋមត្រូវបានពេញចិត្ត)។

ចំណាំថាចាប់តាំងពីឆ្នាំ 2002 ស្តង់ដារហត្ថលេខាឌីជីថលក្នុងស្រុកដែលបានរៀបរាប់ខាងលើត្រូវបានជំនួសដោយ GOST R 34.10-2001 ថ្មី។

ប្រតិចារិក

1 LECTURE 15 លេខបឋម លេខធម្មជាតិ p ធំជាងមួយត្រូវបានគេហៅថាបឋមប្រសិនបើវាត្រូវបានបែងចែកដោយ 1 និងខ្លួនវាប៉ុណ្ណោះ។ ទ្រឹស្តីបទ (អ៊ីក្លីដ) ។ សំណុំនៃលេខបឋមគឺគ្មានកំណត់។ អនុញ្ញាតឱ្យយើងសម្គាល់ដោយ π(x) អនុគមន៍ដែលស្មើនឹងចំនួនលេខបឋម p ក្នុងចន្លោះ 1< x p. Российский математик П. Л. Чебышев в 1850г. показал , что 0,921 x / ln x < π(x) < 1,106 x / ln x. Простые числа являются важным понятием в криптографии. Многие современные криптографические системы строятся на базе простого числа. Поэтому алгоритмы генерации простых чисел и проверки на простоту сформированного числа являются важными инструментами при создании криптографической системы. Простые числа встречаются довольно часто. Заметим, что существует около простых чисел длиной от 1 до 512 бит включительно , а количество простых чисел меньших приблизительно равно . Для чисел близких n вероятность произвольно выбранному числу оказаться простым числом, равна 1/ln n. При случайном выборе двух простых чисел в диапазоне от 1 до 151 бита вероятность совпадения этих чисел ничтожно мала. Простые числа играют តួនាទីសំខាន់នៅក្នុងការគ្រីបទំនើប។ ប្រព័ន្ធគ្រីបលេខសាធារណៈទំនើបៗជាច្រើន (ឬមិនស៊ីមេទ្រី) ត្រូវបានបង្កើតឡើងដោយប្រើលេខសំខាន់ៗ។ សម្រាប់លេខបឋម យើងនឹងពិចារណាបញ្ហាចំនួនបី៖ ការបង្កើតលេខបឋម; ពិនិត្យលេខសម្រាប់ភាពសាមញ្ញ; កត្តាបំបែក (បំបែក) នៃលេខទៅជាកត្តាសំខាន់។ តាមពិត កិច្ចការទាំងបីនេះពិតជាផ្តល់ឱ្យ

2 ចម្លើយចំពោះសំណួរមួយ៖ តើលេខនៅក្នុងសំណួរសំខាន់ទេ? ប៉ុន្តែសម្រាប់កិច្ចការនីមួយៗ វិធីសាស្ត្រផ្សេងៗត្រូវបានប្រើប្រាស់។ សម្រាប់បញ្ហាទីមួយ ដោយប្រើលក្ខខណ្ឌចាំបាច់នៃភាពសាមញ្ញ អ្នកអាចផ្តល់ចម្លើយដូចជា៖ លេខដែលបានផ្តល់ឱ្យ n មិនមែនជាបឋមទេ។ ប្រូបាប៊ីលីតេដែលលេខដែលបានផ្តល់ឱ្យ n មិនមែនជាបឋមគឺតិចជាងលេខដែលបានផ្តល់ឱ្យ ε ។ សម្រាប់បញ្ហាទីពីរ អ្នកអាចបង្កើតលំដាប់លេខជាក់លាក់មួយ។ ប្រភេទពិសេស. ហើយ​សម្រាប់​លេខ​នៃ​លំដាប់​ដែល​បាន​ផ្ដល់ សូម​អនុវត្ត​ការ​ធ្វើ​តេស្ត​មួយ​ចំនួន​រហូត​ដល់​យើង​រក​ឃើញ​លេខ​សំខាន់​ក្នុង​ចំណោម​លេខ​ទាំង​នោះ។ អនុញ្ញាតឱ្យយើងបង្ហាញនិយមន័យ ទ្រឹស្តីបទ និងក្បួនដោះស្រាយមួយចំនួនដែលទាក់ទងនឹងបញ្ហានៃការដោះស្រាយបញ្ហាដែលបានដាក់ (សូមមើលឧទាហរណ៍ ; ; )។ និយមន័យ 1. លេខ F k = 2 α + 1, α = 2 k, k = 0, 1, 2 ត្រូវបានគេហៅថាលេខ Fermat ។ ទ្រឹស្តីបទ 1. លេខ Fermat n = F k សម្រាប់ k > 0 គឺសាមញ្ញប្រសិនបើ 3 (n 1)/2 1 mod n ។ និយមន័យ 2. ចូរ p ជាលេខបឋម។ លេខនៃទម្រង់ M p = 2 p 1 ត្រូវបានគេហៅថាលេខ Mersenne ។ និយាយអីញ្ចឹង លេខល្អឥតខ្ចោះទាំងអស់មានទម្រង់ 2 p 1 M p ដែល M p គឺជាលេខ Mersenne ។ សូមចាំថាចំនួនល្អឥតខ្ចោះគឺជាលេខដែលស្មើនឹងផលបូកនៃផ្នែកទាំងអស់របស់វាដែលតូចជាងខ្លួនវា។ ឧទាហរណ៍ 28 = លេខ Mersenne គឺកម្រណាស់។ ក្នុងឆ្នាំ 2001 លេខ Mersenne ទីសាមសិបប្រាំបួនត្រូវបានរកឃើញសម្រាប់ p = ដើម្បីពិនិត្យមើលភាពដើមនៃលេខ Mersenne ទ្រឹស្តីបទខាងក្រោមត្រូវបានប្រើ។ ទ្រឹស្តីបទ 2. ចូរ n ជាចំនួនបឋម, n > 2, M n = 2 n 1. ពិចារណាពីលំដាប់ L 0, L 1 ដែលត្រូវបានកំណត់ដោយទំនាក់ទំនង L 0 = 4, L 2 j+1 = L 2 j 2 mod n, 0 j< n. Число M n простое тогда и только тогда, когда L q 2 0

លេខ 3 ម៉ូដ ពិនិត្យសាមញ្ញ លេខបឋមត្រូវបានទាមទារសម្រាប់ប្រព័ន្ធគ្រីបគ្រីបភាគច្រើនជាមួយ សោសាធារណៈ. សម្ភារៈទ្រឹស្តីលើបញ្ហានៃការសាងសង់លេខបឋមធំអាចត្រូវបានរកឃើញនៅក្នុងនិង។ មានតែវិធីសាស្រ្តជាក់ស្តែងមួយចំនួនប៉ុណ្ណោះក្នុងការបង្កើតលេខសំខាន់ៗដែលនឹងត្រូវបានបង្កើតនៅទីនេះ។ ដើម្បីបង្កើតលេខបឋមធំ វិធីសាស្រ្តពីរខាងក្រោមអាចត្រូវបានប្រើ៖ លេខចៃដន្យនៃលំដាប់ដែលបានផ្តល់ឱ្យត្រូវបានបង្កើត ហើយដោយប្រើការធ្វើតេស្តដែលមានស្រាប់ វាត្រូវបានពិនិត្យថាតើពួកវាជាលេខសំខាន់ឬអត់។ លេខបឋមត្រូវបានបង្កើតដោយប្រើក្បួនដោះស្រាយជាក់លាក់មួយ ហើយការប្រើតេស្តជាក់លាក់ លេខត្រូវបានពិនិត្យសម្រាប់ភាពសំខាន់។ ជាដំបូង សូមក្រឡេកមើលការធ្វើតេស្តដែលប្រើដើម្បីអនុវត្តវិធីសាស្រ្តដំបូងក្នុងការបង្កើតលេខបឋម។ ការបែងចែកសាកល្បង វិធីសាមញ្ញបំផុតមួយដើម្បីសាកល្បងលេខ p សម្រាប់បឋមគឺត្រូវបែងចែកលេខ p ជាលំដាប់ដោយលេខសេសទាំងអស់ដែលមានក្នុងចន្លោះពេល។ ប្រសិនបើនៅក្នុងដំណើរការនៃការបែងចែកយើងទទួលបានលទ្ធផលចំនួនគត់ នោះលេខ p គឺជាសមាសធាតុ។ ប្រសិនបើនៅពេលស្វែងរកលេខសេសទាំងអស់ពីចន្លោះពេលមួយ វាមិនអាចបែងចែកលេខ p ទៅជាលេខទាំងនេះបានទាំងស្រុងទេ នោះលេខ p គឺសំខាន់។ វិធីសាស្រ្តនេះត្រូវបានគេហៅថាការបែងចែកសាកល្បង។ វិធីសាស្រ្តនេះគឺផ្អែកលើនព្វន្ធ និងត្រូវបានប្រើជាចម្បងដើម្បីសាកល្បងលេខបឋមតូចៗ។

4 Sieve of Eratosthenes ប្រសិនបើយើងចង់បង្កើតតារាងនៃលេខបឋមទាំងអស់ក្នុងចំណោមលេខ 2, 3, N បន្ទាប់មកយើងត្រូវកាត់តាមលំដាប់លេខទាំងអស់ដែលបែងចែកដោយ 2 លើកលែងតែ 2 ។ នៅថ្ងៃទី 3 លើកលែងតែ 3; នៅលើ 5 លើកលែងតែ 5; ទៅលេខបន្ទាប់ដែលមិនត្រូវបានកាត់ចេញលើកលែងតែលេខនេះ; ល. ជាលទ្ធផល ក្នុងចំណោមលេខពី 1 ដល់ N មានតែលេខបឋមប៉ុណ្ណោះនឹងនៅដដែល។ ដើម្បីអនុវត្តវិធីសាស្ត្រនេះ ត្រូវការអង្គចងចាំកុំព្យូទ័រច្រើន ប៉ុន្តែវាល្អបំផុតសម្រាប់ការចងក្រងតារាងនៃលេខបឋម។ លើសពីនេះទៅទៀតពួកគេកំពុងអភិវឌ្ឍ ឧបករណ៍ដំណើរការពិសេសដែលប្រតិបត្តិការរុះរើត្រូវបានអនុវត្តយ៉ាងមានប្រសិទ្ធភាព។ មតិយោបល់។ ការបែងចែកសាកល្បង និង Sieve នៃ Eratosthenes អាចត្រូវបានប្រើដើម្បីដោះស្រាយបញ្ហានៃកត្តាចំនួនគត់។ ការសាកល្បងដោយផ្អែកលើទ្រឹស្តីបទតិចតួចរបស់ Fermat ទ្រឹស្តីបទតិចតួចរបស់ Fermat ចែងថាប្រសិនបើ n ជាចំនួនបឋម នោះលក្ខខណ្ឌខាងក្រោមមាន៖ សម្រាប់ a (2, 3, n 1) ការប្រៀបធៀប A n 1 1 mod n រក្សា។ ដោយផ្អែកលើទ្រឹស្តីបទនេះ គេអាចបង្កើតក្បួនដោះស្រាយ probabilistic សម្រាប់ពិនិត្យភាពបឋមនៃចំនួន n ។ ប្រសិនបើចំនួនគត់ a ពីចន្លោះពេលទំនាក់ទំនង n 1 1 mod n មិនជាប់ នោះលេខ n គឺជាសមាសធាតុ។ ប្រសិនបើទ្រឹស្តីបទគឺពិត នោះការសន្និដ្ឋានថាលេខ n ជាបឋមមិនអាចធ្វើបានទេ ចាប់តាំងពី

ទ្រឹស្តីបទ ៥ ផ្តល់តែលក្ខខណ្ឌចាំបាច់ប៉ុណ្ណោះ។ ដូច្នេះ ប្រសិនបើទំនាក់ទំនងមួយចំនួន n 1 1 mod n ជាប់ នោះលេខ n ត្រូវបានគេនិយាយថាជា pseudoprime ទៅមូលដ្ឋាន a ។ មាន​ចំនួន​គូ a និង n ជា​ច្រើន​ឥត​កំណត់ ដែល n ជា​សមាសធាតុ និង pseudoprime ។ ជាទូទៅសម្រាប់ a> 1 ណាមួយមាន pseudoprimes ជាច្រើនគ្មានកំណត់ដោយផ្អែកលើ a. ជាទូទៅ សេចក្តីថ្លែងការណ៍ពីរខាងក្រោមគឺពិត។ ប្រសិនបើគូ (2, n) ពេញចិត្តការប្រៀបធៀប a n 1 1 mod n នោះគូនៃលេខ (2, 2 n 1) ក៏ពេញចិត្តវាដែរ។ សម្រាប់លេខបឋមណាមួយ n និង a > 2 នោះ (a 2 1, n) = 1 លេខ (a 2n 1)/(a 2 1) គឺ pseudoprime ទៅមូលដ្ឋាន a ។ និយមន័យ។ លេខសមាសធាតុ n ដែលការប្រៀបធៀប n 1 1 mod n ជាការពិតនៅក្នុងមូលដ្ឋានទាំងអស់ត្រូវបានគេហៅថាលេខ Carmichael ។ គ្រោងការណ៍នៃក្បួនដោះស្រាយដោយផ្អែកលើទ្រឹស្តីបទតិចតួចរបស់ Fermat លេខ n និងប៉ារ៉ាម៉ែត្រ γ = 1 ត្រូវបានផ្តល់ឱ្យដើម្បីកំណត់លទ្ធផលតេស្ត។ 1) ការជ្រើសរើសចៃដន្យនៃចំនួនគត់ a ត្រូវបានធ្វើឡើងពីចន្លោះពេល ; 2) ដោយប្រើក្បួនដោះស្រាយ Euclidean GCD សម្រាប់លេខ a និង n ត្រូវបានគណនា។ 3) ប្រសិនបើ gcd ធំជាង 1 នោះជំហានទី 7 ត្រូវបានអនុវត្ត។ 4) សម្រាប់លេខ a ការប្រៀបធៀប a n 1 1 mod n ត្រូវបានគូសធីក។ 5) ប្រសិនបើការប្រៀបធៀបមិនត្រូវបានអនុវត្ត នោះប៉ារ៉ាម៉ែត្រ γ = 0 (ចំនួនសមាសធាតុ) ត្រូវបានកំណត់ សូមចូលទៅកាន់ជំហាន 7. 6) ប្រសិនបើការប្រៀបធៀបត្រូវបានអនុវត្ត នោះការធ្វើតេស្តអាចត្រូវបានធ្វើម្តងទៀត។ 7) បង្ហាញលទ្ធផលនៃការត្រួតពិនិត្យ (γ = 0 គឺជាចំនួនសមាសធាតុ) ។

6 នៅពេលបញ្ចប់ក្បួនដោះស្រាយការសន្និដ្ឋានខាងក្រោមអាចធ្វើទៅបាន: លេខ n គឺជាសមាសធាតុ (γ = 0); ប្រសិនបើ γ = 1 នោះ n ជាបឋម ឬសមាសធាតុ និងជាលេខ Carmichael ។ វាជាការសមរម្យក្នុងការកត់សម្គាល់នៅទីនេះថាលេខ Carmichael គឺកម្រណាស់។ ដូច្នេះមានលេខ Carmichael សរុបដែលមិនលើសពី ហើយចំនួនសរុបចំនួន 16 ដែលមិនលើសពីចំនួន Solove Strassen's Test ការធ្វើតេស្ត Solove Strassen សម្រាប់ពិនិត្យមើលភាពបឋមនៃចំនួន p គឺផ្អែកលើទ្រឹស្តីបទទី 4 ។ ទ្រឹស្តីបទទី 4 ។ សម្រាប់សេស n ណាមួយ លក្ខខណ្ឌខាងក្រោមគឺសមមូល៖ n ជាបឋម; សម្រាប់ Z * n ណាមួយ ការប្រៀបធៀបត្រូវបានធ្វើឡើង a (n 1)/2 mod n L(a, n) ដែល Z * n គឺជាក្រុមពហុគុណដែលធាតុរបស់វាជាធាតុនៃ Z n (Z n គឺជាចិញ្ចៀនសំណល់ ម៉ូឌុល ន) ។ ដើម្បីពិនិត្យមើលភាពសំខាន់នៃលេខ p ក្បួនដោះស្រាយសម្រាប់គណនានិមិត្តសញ្ញា Jacobi ត្រូវបានប្រើ។ គ្រោងការណ៍នៃក្បួនដោះស្រាយផ្អែកលើទ្រឹស្តីបទតិចតួចរបស់ Fermat អនុញ្ញាតឱ្យលេខសេស p ត្រូវបានផ្តល់ឱ្យ។ យើងត្រូវពិនិត្យមើលថាតើលេខ p ជាបឋមឬអត់។ 1. លេខចៃដន្យ a តិចជាង p ត្រូវបានជ្រើសរើស។ 2. ប្រសិនបើ gcd (a, p) 1 នោះ p គឺជាលេខផ្សំ។ 3. ការប្រៀបធៀប L(a, p) a (p 1)/2 mod p ត្រូវបានគណនា។ 4. និមិត្តសញ្ញា Jacobi J(a, p) ត្រូវបានគណនា។ 5. ប្រសិនបើ L(a, p) J(a, p) នោះ p គឺជាលេខផ្សំ។ 6. ប្រសិនបើ L(a, p) = J(a, p) នោះប្រូបាប៊ីលីតេដែល p ជាចំនួនសមាសធាតុមិនលើសពី 50% ។

7 ប្រសិនបើការធ្វើតេស្តត្រូវបានធ្វើម្តងទៀត k ដង នោះប្រូបាប៊ីលីតេដែលលេខ p គឺជាសមាសធាតុមិនលើសពី 1/2 k ។ ការធ្វើតេស្ត Rabin Miller ហេតុផលសម្រាប់ក្បួនដោះស្រាយរបស់ Rabin Miller អាចត្រូវបានរកឃើញនៅក្នុង។ នៅទីនេះយើងនឹងផ្តល់ឱ្យតែច្រើនបំផុត ការពិចារណាទូទៅ. គេដឹងថា ប្រសិនបើលេខ p ជាបឋម នោះសមីការ x 2 1 mod p មានដំណោះស្រាយតែពីរប៉ុណ្ណោះ៖ x ± 1 mod p ។ ដូច្នេះ សូមឱ្យ p ជាចំនួនគត់សេស ដែលចាំបាច់ត្រូវពិនិត្យរកភាពបឋម។ ប្រសិនបើ p ជាបឋម នោះតាមទ្រឹស្តីបទរបស់ Fermat សម្រាប់ចំនួនគត់ coprime ទៅ p ការប្រៀបធៀប m 1 1 mod p គឺពេញចិត្ត។ ចាប់តាំងពីទំ 1 គឺស្មើ យើងទទួលបាន (m 1) / 2 ± 1 mod ទំ។ ប្រសិនបើវាប្រែថា (m 1)/2 គឺស្មើ នោះយើងអាចនិយាយឡើងវិញនូវហេតុផលដែលយើងទទួលបាននោះ a (m 1)/4 ±1 mod p ។ល។ ដូច្នេះ ដើម្បីពិនិត្យមើលភាពសាមញ្ញនៃចំនួនសេស p យើងជ្រើសរើសលេខ a ដោយចៃដន្យពីចន្លោះពេល ហើយគណនា t mod p, 2t mod p, a βt mod p ដែល t ជាសេស និងលេខ β = 2 s ។ ប្រសិនបើលេខមួយក្នុងចំណោមលេខទាំងនេះមិនត្រូវគ្នានឹង +1 ឬ 1 នោះយើងអាចសន្និដ្ឋានថាលេខ p គឺជាលេខផ្សំ។ ប្រសិនបើតម្លៃនៃលេខស្របគ្នាជាមួយ +1 ឬ 1 នោះយើងធ្វើតេស្ដនេះម្តងទៀត k ដង។ បន្ទាប់ពីការធ្វើតេស្តនេះម្តងទៀត k ដង ប្រូបាប៊ីលីតេដែលលេខសមាសធាតុ p នឹងមិនត្រូវបានកំណត់អត្តសញ្ញាណមិនលើសពី 1/4 k ។ បន្ទាប់ពីការពិចារណាខាងលើយើងបន្តទៅការបង្កើតក្បួនដោះស្រាយ Rabin Miller ។ នៅក្នុងអក្សរសិល្ប៍មួយចំនួន ក្បួនដោះស្រាយនេះ។ហៅថាការធ្វើតេស្ត Miller Rabin ។ គ្រោងការណ៍នៃក្បួនដោះស្រាយ Rabin Miller អនុញ្ញាតឱ្យលេខសេស p ត្រូវបានផ្តល់ឱ្យ។ ត្រូវការពិនិត្យ

8 គឺជាលេខដំបូង? បន្ទាប់មកសន្មតថា p 1 = 2 s t ។ 1. ជ្រើសរើសចំនួនចៃដន្យ a តិចជាង p ហើយកំណត់ k = គណនាចំនួនពីរ a និង p ដោយប្រើក្បួនដោះស្រាយ Euclidean GCD ។ ប្រសិនបើ GCD (a, p) 1 នោះ p គឺជាលេខផ្សំ។ 3. គណនា b a t mod p ។ ប្រសិនបើ b = 1 ឬ b = p 1 នោះ p គឺប្រហែលជាបឋម។ 4. ប្រសិនបើ b 1 និង b p 1 បន្ទាប់មកគណនា b b 2 mod p និង k = k ប្រសិនបើលេខ b = p 1 នោះលេខ p ប្រហែលជាបឋម។ ទៅកាន់ជំហាន Bye k< s выполнять пункт Завершить работу алгоритма. Рассмотрим примеры. Пример. Пусть p = 181. Имеем p 1 = По представленному разложению определяем значение параметра t = Выбираем случайное число a = 52 < p, и определяем k = Используем алгоритм Эвклида для вычисления НОД двух чисел 52 и 181: делим число 181 на число 52, получаем 181 = ; делим число 52 на число 25, получаем 52 = ; делим число 25 на число 2, получаем 25 = ; делим число 2 на число 1, получаем 2 = ; получаем, что НОД двух чисел 181 и 52 равен 1. Так как НОД не позволяет установить является ли число 181 составным, то продолжаем выполнять алгоритм Рабина Миллера. 3. Последовательно вычисляем

9 b 52 t mod mod 181:52 2 mod mod mod 181, 52 4 mod mod mod mod mod 181, 52 8 mod mod mod mod 181, mod mod mod mod 181, mod ` mod mod mod 181, mod 181 (52 32 mod 181)(52 8 mod 181) () mod mod 181, mod 181 (52 40 mod 181)(52 mod 181) (80 52) mod mod 181, mod 181 (52 41 mod 181)(52 4 mod 181) ) ( ) mod mod 181 = 180 mod 181. ដូច្នេះយើងទទួលបាន b = 180 = p 1. ដែលមានន័យថាលេខ p = 181 ប្រហែលជាបឋម។ មតិយោបល់។ ដើម្បីបង្កើតលេខបឋមតូចៗ ការគណនាគឺពិបាកណាស់។ ដូច្នេះសម្រាប់ចំនួនពិត ដោយមិនសង្ស័យ ការធ្វើតេស្តលេខបែបនេះសម្រាប់បឋមគួរតែត្រូវបានធ្វើដោយប្រើកម្មវិធីនៅលើកុំព្យូទ័រ។ ការណែនាំខ្លះត្រូវបានផ្តល់ឱ្យលើការបង្កើតលេខបឋមសម្រាប់ការអនុវត្តជាក់ស្តែង។ មគ្គុទ្ទេសក៍នេះចាប់ផ្តើមអនុវត្តដំណាក់កាលជាច្រើន (ជំហាន) ។ 1. បង្កើតលេខចៃដន្យ n-bit p ។ 2. កំណត់ប៊ីតខ្ពស់ និងទាបស្មើ 1. ប៊ីតខ្ពស់ក្នុងករណីនេះធានានូវប្រវែងដែលត្រូវការនៃលេខបឋម ហើយប៊ីតទាបធានាភាពចម្លែករបស់វា។

10 3. ត្រូវប្រាកដថាលេខ p មិនត្រូវបានបែងចែកដោយលេខបឋមតូចៗ 3, 5, 7, 11 ។ល។ ការធ្វើតេស្តដែលអាចទុកចិត្តបំផុតសម្រាប់ការបែងចែកដោយលេខបឋមទាំងអស់តិចជាង អនុវត្តការធ្វើតេស្ត Rabin Miller សម្រាប់លេខចៃដន្យមួយចំនួន a ។ ប្រសិនបើ p ឆ្លងកាត់ការសាកល្បង បន្ទាប់មកបង្កើតលេខចៃដន្យមួយទៀត a ហើយធ្វើតេស្តម្តងទៀត។ សម្រាប់ការអនុវត្តជាក់ស្តែង វាគ្រប់គ្រាន់ក្នុងការធ្វើការធ្វើតេស្ត Rabin Miller ម្តងទៀតចំនួនប្រាំដង។ 5. ប្រសិនបើ p មិនឆ្លងកាត់ការធ្វើតេស្តណាមួយទេ អ្នកត្រូវបង្កើតលេខ p មួយទៀត ហើយធ្វើម្តងទៀត សៀវភៅដៃនេះ។ម្តងទៀត។ លេខ p មួយទៀត ប្រសិនបើវាមិនមែនជាបឋម អាចទទួលបានដោយមិនចាំបាច់បង្កើតលេខថ្មី ប៉ុន្តែតាមលំដាប់លំដោយឆ្លងកាត់ចំនួនគត់ទាំងអស់ ដោយចាប់ផ្តើមពី p + 1 p + 2 ។ល។ រហូតដល់លេខបឋមត្រូវបានរកឃើញ។ . ឥឡូវនេះ ចូរយើងបន្តទៅសំណួរនៃការបង្កើតលេខសំខាន់ៗ។ ការសាងសង់លេខបឋមធំ និងក្បួនដោះស្រាយកំណត់សម្រាប់ពិនិត្យលេខសម្រាប់បឋម ចូរយើងពិចារណាវិធីមួយផ្សេងទៀតដើម្បីបង្កើតលេខបឋម។ វិធីសាស្រ្តនេះគឺផ្អែកលើនីតិវិធីជាក់លាក់មួយសម្រាប់បង្កើតលេខបឋម ដែលត្រូវបានផ្ទៀងផ្ទាត់ដោយប្រើការធ្វើតេស្តបឋម។ វិធីសាស្រ្តនេះត្រូវបានប្រើជាឧទាហរណ៍នៅក្នុងស្តង់ដារ GOST R electronic signature (EDS) និងផ្អែកលើទ្រឹស្តីបទខាងក្រោម។ ទ្រឹស្តីបទ 5. ចូរ p = qn + 1 ដែល q ជាចំនួនបឋមសេស N ជាលេខគូ និង p< (2q + 1) 2. Число p является простым, если выполняются два условия: 1) 2 qn = 1 mod p; 2) 2 N 1 mod p.

11 ការបង្កើតចំនួនបឋមដោយប្រើទ្រឹស្តីបទ 5 ត្រូវបានអនុវត្តតាមគ្រោងការណ៍សាមញ្ញមួយចំនួននៅក្នុងស្តង់ដារដែលទទួលយក។ អនុញ្ញាតឱ្យអ្នកត្រូវការបង្កើតចំនួនបឋម p នៃប្រវែង t 17 ប៊ីត។ ចំពោះគោលបំណងនេះ លំដាប់ថយចុះនៃលេខ (t i) ត្រូវបានសាងសង់ ដែល i = 0, 1, s, ដែល t 0 = t, t i = ។ បន្ទាប់មក លំដាប់នៃលេខបឋម p s, p s 1, p 0 ត្រូវបានបង្កើតជាបន្តបន្ទាប់ សម្រាប់ទាំងអស់ i = 1, s ។ ការបង្កើតលេខបឋម p i 1 ត្រូវបានអនុវត្តដោយប្រើរូបមន្តខាងក្រោម p i 1 = p i N + 1 ដែលលេខ N បំពេញលក្ខខណ្ឌដូចខាងក្រោម: N គឺសូម្បីតែ; N ដូចជាប្រវែងនៃលេខ p i 1 = p i N + 1 ត្រូវតែស្មើនឹង t i 1 ។ ស្តង់ដារ GOST ផ្តល់នូវក្បួនដោះស្រាយមួយចំនួនសម្រាប់ការគណនាលេខ N ។ សម្រាប់កំណែបណ្តុះបណ្តាល N គឺជាលេខគូចៃដន្យ ដែលត្រូវបានទទួល ដោយប្រើឧបករណ៍ចាប់សញ្ញាលេខចៃដន្យ (ប្រសិនបើ N ជាសេស បន្ទាប់មក N = N + 1) ។ លេខ p i 1 ត្រូវបានចាត់ទុកថាទទួលបានប្រសិនបើលក្ខខណ្ឌទាំងពីរខាងក្រោមត្រូវបានបំពេញក្នុងពេលដំណាលគ្នា: 1) 2 β = 1 mod p i, β = p i 1 N; 2) 2 N 1 mod p i ។ ប្រសិនបើយ៉ាងហោចណាស់លក្ខខណ្ឌមួយមិនត្រូវបានបំពេញ នោះតម្លៃនៃលេខ N ត្រូវបានកើនឡើង 2 ហើយតម្លៃថ្មី p i 1 ត្រូវបានគណនា ដែលត្រូវបានពិនិត្យម្តងទៀតសម្រាប់ភាពសាមញ្ញដោយប្រើលក្ខខណ្ឌពីរ។ ដំណើរការនេះ។បន្តរហូតដល់លេខបឋម p i 1 ត្រូវបានទទួល (ឧ. លក្ខខណ្ឌ 1 និង 2 នៃក្បួនដោះស្រាយការបង្កើតលេខបឋមត្រូវបានពេញចិត្ត)។ ចំណាំថាចាប់តាំងពីឆ្នាំ 2002 ស្តង់ដារហត្ថលេខាឌីជីថលក្នុងស្រុកដែលបានរៀបរាប់ខាងលើត្រូវបានជំនួសដោយ GOST R ថ្មី។

12 ការពិនិត្យមើលលេខ Mersenne សម្រាប់ភាពសាមញ្ញ សូមចាំថាលេខ M s = 2 s 1 (s 2 prime) ត្រូវបានគេហៅថាលេខ Mersenne ។ លក្ខណៈវិនិច្ឆ័យសម្រាប់ភាពសំខាន់នៃលេខ Mersenne គឺជាសេចក្តីថ្លែងការណ៍ខាងក្រោម។ ទ្រឹស្តីបទ។ លេខ Mersenne M s = 2 s 1 ដែល s 3 ជាលេខសេសគឺបឋមប្រសិនបើលេខ s ជាបឋម។ ការប្រៀបធៀបត្រូវបានអនុវត្ត L n 2 0 mod M s ដែលលំដាប់ (L k ) ត្រូវបានបង្កើតឡើងយោងទៅតាមច្បាប់ខាងក្រោម: L 0 = 4, L k + 1 = (L 2 k 2) mod M s នៅ k 0 ។

ក្រសួងអប់រំ និងវិទ្យាសាស្ត្រ ក្រសួងអប់រំ និងវិទ្យាសាស្ត្រនៃសហព័ន្ធរុស្ស៊ី ការស្រាវជ្រាវជាតិ TomSK សាកលវិទ្យាល័យរដ្ឋ ដំណើរការបន្តនៃសន្និសីទនិស្សិតរុស្ស៊ីទាំងអស់

មេរៀនទី ១៤ ការគណនា ឫសការ៉េដោយ ម៉ូឌុលសមាសធាតុតាមទ្រឹស្ដីខាងលើ វាធ្វើតាមថា ប្រសិនបើ = កន្លែងណា និងជាលេខបឋម ក្រុម Z គឺអ៊ីសូម៉ូហ្វីកទៅលំហ Z Z។ ដោយសារអ៊ីសូម៉ូហ្វីសរក្សាលក្ខណៈសម្បត្តិ

ផ្នែកទី 2. វិធីសាស្រ្តលេខ - ទ្រឹស្តីនៅក្នុងកិច្ចការគ្រីបគ្រីប ការងារឯករាជ្យសិក្សាក្បួនដោះស្រាយដែលត្រូវបានគេប្រើយ៉ាងទូលំទូលាយក្នុងការគ្រីបគ្រីប។ ធាតុនៃទ្រឹស្ដីលេខ៖ ក្បួនដោះស្រាយ Euclidean ពង្រីក;

សទ្ទានុក្រមនៃពាក្យមូលដ្ឋាន ក្រុម Abelian (ក្រុមផ្លាស់ប្តូរ) ក្រុមបន្ថែមដែលក្នុងនោះ ប្រតិបត្តិការក្រុម commutative: a + b = b + a ។ ការអនុញ្ញាតគឺជានីតិវិធីសម្រាប់បែងចែកអ្នកប្រើប្រាស់ជាក្រុម

សេចក្តីផ្តើមសង្ខេបដល់ការចាប់ផ្តើមនៃទ្រឹស្តីលេខបឋម Denis Kirienko Letnyaya សាលាកុំព្យូទ័រ, ថ្ងៃទី 1 ខែមករា ឆ្នាំ 2009 ការបែងចែកចំនួនគត់អនុញ្ញាតឱ្យចំនួនគត់ពីរ a និង b ត្រូវបានផ្តល់ឱ្យ b 0 ។ កូតាចំនួនគត់នៃការបែងចែក

មេរៀនទី 6 POWER REMEDIA អនុញ្ញាតឱ្យយើងផ្តល់ម៉ូឌុល n និងលេខមួយចំនួន coprime ទៅ modulus n ។ ពិចារណាពីលំដាប់នៃអំណាច a, a 2, a t រកលេខតូចបំផុត k ដែល a k 1 mod n ។ និយមន័យ។

ក្បួនដោះស្រាយដែលមិនធ្លាប់ស្គាល់សម្រាប់ការស្វែងរកលេខបឋមក្នុងចំណោមលេខសេស O.A. Cherepanov នៅក្នុងទ្រឹស្ដីលេខបុរាណមានទ្រឹស្តីបទពីរដែលដាក់ឈ្មោះតាម Pierre Fermat: ធំ x n + y n = z n និងតូច a 1 (mod p) ។ ប៉ុន្តែប្រសិនបើពួកគេដឹងអំពីដំបូង

មេរៀនទី 2 ការគណនាក្បួនដោះស្រាយរបស់ DIVISOR Euclid ទូទៅដ៏អស្ចារ្យបំផុត នៅពេលធ្វើការជាមួយចំនួនសមាសធាតុធំ ការបំបែកកត្តារបស់ពួកគេទៅជាកត្តាចម្បងជាធម្មតាមិនស្គាល់។ ប៉ុន្តែសម្រាប់បញ្ហាជាច្រើនដែលបានអនុវត្តទ្រឹស្តី

ក្រសួងអប់រំ និងវិទ្យាសាស្ត្រ សហព័ន្ធរុស្ស៊ី FSBEI HE "Tver" សាកលវិទ្យាល័យរដ្ឋ» បានយល់ព្រមជាប្រធាន PLO Tsvetkov VP 2015 កម្មវិធីការងារវិន័យ (មានចំណារពន្យល់) ទ្រឹស្តីលេខ

មេរៀនទី 8 លំដាប់ PSEUDO-RANDOM និងនីតិវិធីសម្រាប់ការបង្កើតម៉ាស៊ីនរបស់ពួកគេ នៅក្នុងការធ្វើគំរូស្ថិតិនៃប្រព័ន្ធ បញ្ហាចម្បងមួយគឺការគិតគូរពីឥទ្ធិពល stochastic ។ ចំនួនចៃដន្យ

ក្បួនដោះស្រាយនព្វន្ធ លេខបឋម Sieve នៃ Eratosthenes ការស្វែងរកអ្នកចែក (តិចបំផុត និងធំបំផុត) បង្រួបបង្រួមលេខទៅក្នុង GCD និង LCM ការបំប្លែងទៅប្រព័ន្ធលេខផ្សេង លេខនព្វន្ធដែលនៅសល់

ក្រសួងអប់រំនៃសហព័ន្ធរុស្ស៊ី Ural State Pedagogical University A.P. ទ្រឹស្តីលេខ Ilinykh ការបង្រៀន Ekaterinburg 2003 UDC 511 និង 45 អ្នកមើល៖ សមាជិកដែលត្រូវគ្នា

ក្បួនដោះស្រាយសម្រាប់ការស្វែងរកខ្សែកោង hyperelliptic អំពីអ្នកនិពន្ធ Yu.F. Boltnev st. សាស្ត្រាចារ្យ សាកលវិទ្យាល័យរដ្ឋរុស្សី បានដាក់ឈ្មោះតាម។ I. Kant ។ UDC 511 K.G. ការវិភាគប្រៀបធៀប Mkrtchyan នៃ 105 algorithms នៃវិធីសាស្រ្ត quadratic LATTICE 105 សម្រាប់ FactorIZATION នៃទំហំធំ

ការងារមន្ទីរពិសោធន៍ 11 បង្កើតកម្មវិធីសម្រាប់គណនានិមិត្តសញ្ញា Legendre គោលបំណងនៃការងារគឺប្រើក្បួនដោះស្រាយសម្រាប់គណនានិមិត្តសញ្ញា Legendre ដើម្បីបង្កើតកម្មវិធីសម្រាប់គណនានិមិត្តសញ្ញា Legendre ។ ភារកិច្ចសម្រាប់ការងារ

អនុវត្តពិជគណិត។ ផ្នែកទី ១៖ វាលកំណត់ (វាល Galois) ។ II 1/78 Part I Finite fields (វាល Galois). II អនុវត្តពិជគណិត។ ផ្នែកទី ១៖ វាលកំណត់ (វាល Galois) ។ II 2 / 78 វាលនៃសំណល់ modulo prime

សៀវភៅណែនាំគណិតវិទ្យាទី៥ ថ្នាក់ទី៩ MOSCOW "VAKO" 201 UDC 32.851 BBK 4.262.22 C4 6+ ការបោះពុម្ពត្រូវបានអនុម័តសម្រាប់ប្រើប្រាស់ក្នុង ដំណើរការអប់រំផ្អែកលើបទបញ្ជារបស់ក្រសួងអប់រំ និងវិទ្យាសាស្ត្រនៃសហព័ន្ធរុស្ស៊ី

បាឋកថា 3 4. វិធីសាស្រ្តជាលេខនៃការស្វែងរកដោយឥតលក្ខខណ្ឌ គោលការណ៍នៃការសាងសង់វិធីសាស្រ្តលេខ។ ការអនុវត្តលក្ខខណ្ឌចាំបាច់ និងគ្រប់គ្រាន់សម្រាប់ភាពជ្រុលនិយមដោយគ្មានល័ក្ខខ័ណ្ឌគឺមានប្រសិទ្ធភាពសម្រាប់ដំណោះស្រាយដែលមានកម្រិត

2008 3 ដំណើរការបន្ត ការបកស្រាយក្រាហ្វិកនៃលេខសាមញ្ញ និងសមាសធាតុ សាកលវិទ្យាល័យ Kuban State, Krasnodar ការងារនេះត្រូវបានឧទ្ទិសដល់ភស្តុតាងនៃទ្រឹស្តីបទតិចតួចរបស់ Fermat ។ វាផ្តល់នូវភាពសាមញ្ញមួយ។

ប្រធានបទ។ មូលដ្ឋានគ្រឹះនៃទ្រឹស្តីលេខបឋម និងកម្មវិធី។ ឫសដើម, សន្ទស្សន៍។ សម្ភារៈទ្រឹស្តី អនុញ្ញាតឱ្យ a, m ជាលេខ coprime ធម្មជាតិ និង m បន្ទាប់មកយោងទៅតាមទ្រឹស្តីបទរបស់ អយល័រ a m)

1 - ប្រធានបទទី 1 ធាតុនៃទ្រឹស្តីនៃកំហុស 11 ប្រភព និងការចាត់ថ្នាក់នៃកំហុស ដំណោះស្រាយជាលេខនៃបញ្ហាណាមួយ ជាក្បួនត្រូវបានអនុវត្តប្រមាណ ប៉ុន្តែជាមួយនឹងភាពត្រឹមត្រូវមួយចំនួន នេះអាចបណ្តាលមកពី

លំហាត់គណិតវិទ្យាដាច់ពីគ្នា 22 (revision), ដំណោះស្រាយ 1 Find បរិមាណអតិបរមាគែមនៅក្នុងក្រាហ្វដែលដឹកនាំនៅលើកំពូល n ដែលមិនមានវដ្តដឹកនាំ ដំណោះស្រាយរវាង

1 សូចនាករ។ ឫសបឋម។ 1.1 គំនិតនៃសូចនាករ។ លក្ខណៈសម្បត្តិសាមញ្ញបំផុត។ និយមន័យ។ យើងនឹងនិយាយថាលេខ a, (a, n) = 1 ជាកម្មសិទ្ធិរបស់និទស្សន្ត N modulo n ប្រសិនបើជាចំនួនអប្បបរមាដូចជា

អនុវត្តពិជគណិត។ ផ្នែកទី 1: វាលកំណត់ឬវាល Galois ។ II 1/78 ផ្នែកទី I Finite fields ឬ Galois fields ។ II អនុវត្តពិជគណិត។ ផ្នែកទី ១៖ វាលកំណត់ ឬវាល Galois ។ II 2/78 វាលនៃការកាត់ម៉ូឌុល

បាឋកថា 4. AES STANDARD ។ RIJNDAEL ALGORITHM។ ស្តង់ដារ AES (Advnced Encrypton Stndrd) គឺ ស្តង់ដារថ្មី។ការអ៊ិនគ្រីបកូនសោតែមួយ ដែលបានជំនួសស្តង់ដារ DES ។ ក្បួនដោះស្រាយ Rjndel (Rhein Dal)

ថ្ងៃទី 20 ខែមករា ឆ្នាំ 2017 កិច្ចការមូលដ្ឋានប្រឡងបង្រួបបង្រួមរដ្ឋ 19 ដំណោះស្រាយនៃគំរូទាំងអស់នៃកិច្ចការទី 19 (មូលដ្ឋានប្រឡងរដ្ឋបង្រួបបង្រួម) ។ បញ្ហា 1366. ស្វែងរកលេខធម្មជាតិប្រាំមួយខ្ទង់ ដែលសរសេរត្រឹមតែ 2 និង 0 ហើយចែកដោយ 24។ ចង្អុលបង្ហាញនៅក្នុងចម្លើយរបស់អ្នក

វិធីសាស្រ្តសាមញ្ញក្នុងការដោះស្រាយបញ្ហា កម្មវិធីលីនេអ៊ែរវិធីសាស្រ្តលេខសំខាន់សម្រាប់ការដោះស្រាយបញ្ហាសរសេរកម្មវិធីលីនេអ៊ែរគឺអ្វីដែលគេហៅថាវិធីសាស្ត្រសាមញ្ញ។ ពាក្យ "វិធីសាស្រ្តសាមញ្ញ" ត្រូវបានផ្សារភ្ជាប់ជាមួយនឹងការពិត

V.M. សៀវភៅទ្រឹស្តីលេខ Sitnikov Chelyabinsk 204 0 ក្រសួងអប់រំ និងវិទ្យាសាស្ត្រនៃសហព័ន្ធរុស្ស៊ី ថវិការដ្ឋសហព័ន្ធ ស្ថាប័នអប់រំខ្ពស់ជាង ការអប់រំវិជ្ជាជីវៈ"ទីក្រុង Chelyabinsk

វិទ្យាស្ថានបើកទូលាយនៃការដឹកជញ្ជូនរបស់រុស្ស៊ី សាកលវិទ្យាល័យទំនាក់ទំនងរដ្ឋ ទីក្រុងម៉ូស្គូ អនុម័តដោយនាយកដ្ឋាន "ស្វ័យប្រវត្តិកម្មផ្លូវដែក ទូរគមនាគមន៍ និងទំនាក់ទំនង" ព័ត៌មានមូលដ្ឋាន

ស្តង់ដារអប់រំរបស់រដ្ឋសហព័ន្ធ សៀវភៅការងារសាលាច្នៃប្រឌិតសម្រាប់សៀវភៅសិក្សា “គណិតវិទ្យា។ ថ្នាក់ទី ៦” កែសម្រួលដោយអ្នកសិក្សានៃបណ្ឌិត្យសភាវិទ្យាសាស្ត្ររុស្ស៊ី V.V. Kozlov និងអ្នកសិក្សានៃបណ្ឌិត្យសភាអប់រំរុស្ស៊ី A.A. Nikitina ជាបួនផ្នែក ភាគ 1 ទីក្រុងម៉ូស្គូ " ពាក្យរុស្ស៊ី» ទិសដៅឆ្នាំ 2013

UDC 511. ចំនួនគត់នៃវាលរាងបួនជ្រុង Zhuravlev E.V., Tokarev V.N. សាកលវិទ្យាល័យរដ្ឋ Altai, សាកលវិទ្យាល័យបច្ចេកទេសរដ្ឋ Altai [អ៊ីមែលការពារ], [អ៊ីមែលការពារ]

រដ្ឋាភិបាលនៃសហព័ន្ធរុស្ស៊ី ស្ថាប័នអប់រំស្វយ័តរដ្ឋសហព័ន្ធនៃការអប់រំវិជ្ជាជីវៈកម្រិតខ្ពស់ជាតិ សាកលវិទ្យាល័យស្រាវជ្រាវ"វិទ្យាល័យសេដ្ឋកិច្ច"

ការងារមន្ទីរពិសោធន៍ វិធីសាស្រ្តសម្រាប់កាត់បន្ថយមុខងារនៃអថេរមួយដោយប្រើព័ត៌មានអំពីនិស្សន្ទវត្ថុ មុខងារគោលបំណងសេចក្តីថ្លែងការណ៍បញ្ហា៖ វាត្រូវបានទាមទារដើម្បីស្វែងរកអប្បបរមាដោយគ្មានលក្ខខណ្ឌនៃមុខងារនៃអថេរមួយ (

ផ្នែកទី 3 លំដាប់នៃការធ្វើតេស្តឯករាជ្យ ការបង្រៀន 4 ការធ្វើតេស្តឯករាជ្យ។ រូបមន្ត ប៊ែននូលី។ ទម្រង់ asymptotic នៃ MOIVRE LAPLACE និង POISSON គោលបំណងនៃការបង្រៀន៖ ដើម្បីណែនាំគំនិតនៃការធ្វើតេស្តឯករាជ្យ និង

~ 1 ~ "សញ្ញានៃភាពឯកតានៃអនុគមន៍" ទ្រឹស្តីបទ៖ ដើម្បីឱ្យអនុគមន៍ f(x) ខុសគ្នានៅលើ a,b ដើម្បីបង្កើន (បន្ថយ) លើ a,b វាចាំបាច់ និងគ្រប់គ្រាន់ដែល x a,b វិសមភាព f (x ) 0 (f ( x)

សាកលវិទ្យាល័យសហព័ន្ធ KAZAN N.A. Koreshkov, M.F. Nasrutdinov ការប្រមូលបញ្ហាលើទ្រឹស្តីលេខ Kazan 2016 Kazan (Volga Region) Federal University N.A. Koreshkov, M.F. Nasrutdinov ការប្រមូលបញ្ហា

A.P. Ivanov ការណែនាំប្រធានបទទី៤៖ វិធីសាស្ត្ររបស់ញូតុនមិនដោះស្រាយទេ។ សមីការលីនេអ៊ែរនិងប្រព័ន្ធសមីការ មហាវិទ្យាល័យវិស្វកម្មមេកានិក PU St. Petersburg State University 2007 ខ្លឹមសារ 1. ការដោះស្រាយសមីការមាត្រដ្ឋាន…………………….

Math-Net.Ru All-Russian mathematical portal V. M. Zhuravlev, P. I. Samovol, សមីការ Diophantine អិចស្ប៉ូណង់ស្យែល និងផលបូកនៃខ្ទង់នៃចំនួនមួយ, Mat. Prosv., 2016, លេខ 20, 167 199 ការប្រើប្រាស់ភាសារុស្សីទាំងអស់

1. តម្រូវការសម្រាប់កម្រិតនៃការរៀបចំរបស់សិស្ស។ សិស្សដែលបានបញ្ចប់ថ្នាក់ទី 9 ត្រូវតែអាច: ធ្វើប្រតិបត្តិការនព្វន្ធ, រួមបញ្ចូលគ្នារវាងបច្ចេកទេសផ្ទាល់មាត់និងសរសេរ; ស្វែងរកតម្លៃនៃឫសនៃសញ្ញាបត្រធម្មជាតិ,

99 UDC 004.94 ប្រសិទ្ធភាពនៃការប្រើប្រាស់ម៉ាស៊ីនភ្លើងលេខ PSEUDO-RANDOM នៅក្នុងប្រព័ន្ធគ្រីបតូក្រាហ្វិច Gubenko N.E., Nazarov E.A. សាកលវិទ្យាល័យបច្ចេកទេសជាតិ Donetsk នាយកដ្ឋានកុំព្យូទ័រ Donetsk

11 Stream cryptosystems 11.1 Stream cryptosystems អនុញ្ញាតឱ្យយើងរំលឹកឡើងវិញនូវនិយមន័យរបស់យើងអំពីប្រព័ន្ធគ្រីបតូស្ទ្រីម។ សូមឱ្យមានពាក្យ X A នៃប្រវែង X = T ។ ដើម្បីអ៊ិនគ្រីបពាក្យនេះនៅលើសោ θ Θ ខាងក្រោមត្រូវបានអនុវត្ត៖

ប្រព័ន្ធនៃសមីការលីនេអ៊ែរ បន្ទាប់ពីសិក្សាប្រធានបទនេះ អ្នកនឹងអាច៖ អនុវត្តដំណោះស្រាយជាលេខចំពោះបញ្ហាពិជគណិតលីនេអ៊ែរ។ បញ្ហាជាច្រើនត្រូវបានកាត់បន្ថយទៅជាប្រព័ន្ធនៃសមីការលីនេអ៊ែរ។ បញ្ហាជាក់ស្តែង, ដំណោះស្រាយ

9., 9. grade Module 5 “Sequences. ដឺក្រេនិងឫស" ការធ្វើតេស្តសាកល្បងផ្នែកទ្រឹស្តីនិងការអនុវត្ត។ លំដាប់លេខ លំដាប់។ វិធីសាស្ត្រកំណត់លេខរៀង៖

ផ្នែកទី 2 ទ្រឹស្ដីនៃដែនកំណត់ ប្រធានបទ លំដាប់លេខ និយមន័យនៃលំដាប់លេខ 2 លំដាប់ដែលមានព្រំដែន និងគ្មានព្រំដែន 3 លំដាប់ម៉ូណូតូន 4 គ្មានកំណត់ និង

Math-Net.Ru វិបផតថលគណិតវិទ្យារុស្ស៊ីទាំងអស់ V. M. Zhuravlev, P. I. Samovol, សមីការ Diophantine អិចស្ប៉ូណង់ស្យែល និងផលបូកនៃខ្ទង់នៃចំនួនមួយ, Mat. Pros., 2016, Issue 20, 167 199 ការប្រើប្រាស់គណិតវិទ្យារុស្ស៊ីទាំងអស់

ត្រូវបានគេពិចារណានៅក្នុងកិច្ចប្រជុំរបស់គ្រូគណិតវិទ្យា និងរូបវិទ្យានៃតំបន់មូស្គូក្នុងឆ្នាំ 2013 ។ ប្រធានតំបន់ម៉ូស្គូ A.M. Bobkova ខ្ញុំយល់ព្រមលើ 2013 នាយកនៃ MAOU Lyceum 29 A.I

គំរូស្ថិតិ។ លក្ខណៈទូទៅវិធីសាស្រ្តនៃគំរូស្ថិតិ នៅដំណាក់កាលនៃការស្រាវជ្រាវ និងការរចនាប្រព័ន្ធ នៅពេលសាងសង់ និងអនុវត្តគំរូម៉ាស៊ីន វិធីសាស្ត្រ

មេរៀនទី 3 កិច្ចការ 1. ក) ស្វែងរកឫសប្រឆាំងដេរីវេទាំងអស់ 27. ចំណាំថា ϕ(27) = 27 9 = 18 = 2 3 2. ចូរយើងប្រើលក្ខណៈវិនិច្ឆ័យ ហើយពិនិត្យមើលថាតើ 2 ឫសដើមម៉ូឌុល ២៧:២ ៦ ៦៤ ១០

កំណត់ចំណាំការបង្រៀន។ (Kazan, ថ្ងៃទី 4 ខែមេសា ឆ្នាំ 207) កំណត់ចំណាំបានប្រើ សម្រាប់ក្រាហ្វដែលមិនមានការដឹកនាំ យើងប្រើសញ្ញាសម្គាល់ G pv, Eq ដែល V គឺជាសំណុំនៃចំនុចកំពូល ហើយ E គឺជាសំណុំនៃគែម។ ក្នុងពេលជាមួយគ្នានេះយើងសារភាព

ស្ថាប័នថវិការដ្ឋសហព័ន្ធនៃនាយកដ្ឋានអប់រំវិជ្ជាជីវៈខ្ពស់ "SibGUTI" ប្រព័ន្ធកុំព្យូទ័រការសរសេរកម្មវិធីភាសា ដំណើរការនៃអារេទិន្នន័យមួយវិមាត្រ ( មេរៀនជាក់ស្តែង) គ្រូ៖ សាស្ត្រាចារ្យរងនៃនាយកដ្ឋានកងកម្លាំងប្រដាប់អាវុធ, បណ្ឌិត។ Polyakov Artem

កំណត់ទ្រឹស្តីបទសម្រាប់ការចែកចាយដោយឯករាជ្យ អថេរចៃដន្យ. ការបញ្ចូលគ្នានៅក្នុងប្រូបាប៊ីលីតេ ការបញ្ចូលគ្នាជាមួយនឹងប្រូបាប៊ីលីតេមួយ។ វិសមភាពរបស់ P.L.Chebyshev ។ ច្បាប់នៃលេខធំសម្រាប់លំដាប់

ក្រសួងអប់រំនិងវិទ្យាសាស្ត្រនៃសហព័ន្ធរុស្ស៊ីថវិការដ្ឋសហព័ន្ធវិទ្យាស្ថានអប់រំនៃឧត្តមសិក្សា "សាកលវិទ្យាល័យស្រាវជ្រាវជាតិសារ៉ាតូវ"

LECTURE 7 ELITIC CURVES ខ្សែកោងរាងអេលីបទិកគឺជាឧបករណ៍គណិតវិទ្យាដែលត្រូវបានគេប្រើជាញឹកញាប់នៅក្នុង ក្បួនដោះស្រាយផ្សេងៗការអ៊ិនគ្រីប។ វាមានគុណសម្បត្តិមួយចំនួន: នៅពេលប្រើខ្សែកោងរាងអេលីប

ជំពូកទី VIII ។ ទ្រឹស្តីទូទៅការបែងចែក 1. ធាតុសាមញ្ញ និងមិនអាចកាត់ថ្លៃបាននៃដែននៃសុចរិតភាព 1. គោលគំនិតជាមូលដ្ឋាននៃទ្រឹស្តីនៃការបែងចែកនៅក្នុងដែននៃសុចរិតភាព។ រំលឹកឡើងវិញថា ដែននៃភាពសុចរិតត្រូវបានគេហៅថា ការផ្លាស់ប្តូរ

ផ្នែកទី 1. កំណត់ចំណាំពន្យល់ 1.1 ។ តម្រូវការសម្រាប់និស្សិត៖ ទាមទារ ចំណេះដឹងមូលដ្ឋានដោយ ការវិភាគគណិតវិទ្យា, ពិជគណិត៖ OK-8 PC-3 សមត្ថភាព និងការត្រៀមខ្លួនជាប្រចាំ ដើម្បីកែលម្អ និងធ្វើឲ្យស៊ីជម្រៅ

ថវិកាក្រុង ស្ថាប័នអប់រំ"សាលាមធ្យមសិក្សាមូលដ្ឋាន Dobrinskaya ដាក់ឈ្មោះតាម Nikolay Semenovich Spiridonov" កម្មវិធីការងារក្នុងគណិតវិទ្យាសម្រាប់សិស្សថ្នាក់ទី 6B ជាមួយនឹងការពន្យារពេល

ក្នុងគណិតវិទ្យាថ្នាក់ទី៦ (UMK A.G. Merzlyak) ឆ្នាំសិក្សា ២០១៦-២០១៧ ផែនការប្រធានបទប្រហាក់ប្រហែល។ គណិតវិទ្យា។ ថ្នាក់ទី 6 (ជម្រើស I ។ 5 ម៉ោងក្នុងមួយសប្តាហ៍សរុប 175 ម៉ោង; ជម្រើសទី II ។ 6 ម៉ោងក្នុងមួយសប្តាហ៍។

ឧបសម្ព័ន្ធទី ៥ ដល់ កម្មវិធីអប់រំ MBOU SSH 2 ដែលត្រូវបានអនុម័តដោយបញ្ជារបស់នាយកចុះថ្ងៃទី 27 ខែមិថុនា ឆ្នាំ 2013 275P (កែប្រែដោយលំដាប់ចុះថ្ងៃទី 4 ខែមីនា ឆ្នាំ 2016 69P) កម្មវិធីការងារនៃមុខវិជ្ជាសិក្សា "ALGEBRA" FKGOS: ថ្នាក់ទី 8-9

“យល់ព្រម” នាយករងផ្នែកធនធានទឹក គ្រឹះស្ថានអប់រំក្រុង អនុវិទ្យាល័យភូមិប៉ាឌី /_Zakharova M.V./ ចុះថ្ងៃទី 1 ខែកញ្ញា ឆ្នាំ 2016 “ខ្ញុំយល់ព្រម” នាយកសាលាមធ្យមសិក្សារបស់គ្រឹះស្ថានអប់រំក្រុង ភូមិប៉ាឌី / Pochtarev A.G./ ដីកាលេខ ៩៥ ចុះថ្ងៃទី ១ ខែកញ្ញា ឆ្នាំ ២០១៦។ កម្មវិធីការងារ

សំណុំនៃចំនួនធម្មជាតិ និងសំណុំនៃចំនួនគត់។ ទំ.៨. ចំនុចប្រសព្វ និងការរួបរួមនៃសំណុំ។ ទំ.១០. Natural Integers MATERIALS for a website on គណិតវិទ្យា ថ្នាក់ទី៨ លោកគ្រូ៖ (Subach M.V.) TOPIC Know Be able to Know definition

លេខមេរៀន ប្រធានបទមេរៀន ប្រតិទិន - THEMATIC PLANNING ថ្នាក់ទី 6 ចំនួនម៉ោង ជំពូក 1. ប្រភាគធម្មតា។ 1. ការបែងចែកលេខ 24 ម៉ោង 1-3 ចែកនិងគុណ 3 ចែក ពហុគុណ តូចបំផុតនៃធម្មជាតិ

ថ្នាក់ទី 8.3 គណិតវិទ្យា (សៀវភៅសិក្សា Makarychev) ឆ្នាំសិក្សា 2016-2017 ប្រធានបទនៃម៉ូឌុល 5 " ឫសការ៉េ. សញ្ញាប័ត្រដែលមានសូចនាករចំនួនគត់” ការធ្វើតេស្តសាកល្បងផ្នែកទ្រឹស្តី និងការអនុវត្ត។ TOPIC Know អាចដឹង

ប្រធានបទ 4. ដំណោះស្រាយជាលេខនៃសមីការក្រៅបណ្តាញ -1- ប្រធានបទ 4. ដំណោះស្រាយជាលេខនៃសមីការក្រៅបណ្តាញ 4.0. សេចក្តីថ្លែងការណ៍នៃបញ្ហា បញ្ហានៃការស្វែងរកឫសគល់នៃសមីការមិនមែនលីនេអ៊ែរនៃទម្រង់ y=f() ត្រូវបានជួបប្រទះជាញឹកញាប់នៅក្នុងវិទ្យាសាស្ត្រ

ការធ្វើតេស្ត Miller-Rabin៖

បញ្ចូល៖ n=2sr+1 – លេខសេស ពិនិត្យរកបឋម, s≥0, r – សេស។ t - ចំនួននៃការធ្វើម្តងទៀត ប៉ារ៉ាម៉ែត្រភាពជឿជាក់។

1. ធ្វើម្តងទៀតនូវជំហានខាងក្រោម t ដង:

១.១. ជ្រើសរើសដោយចៃដន្យ (2,…, n-2);

១.២. បង្កើតលំដាប់ b0, b1,…,bs យោងទៅតាមច្បាប់៖

b0=ar mod n, bj=(bj-1)2 mod n, j=1,2,…,s ។

១.៣. ប្រសិនបើវាមិនត្រូវបានរកឃើញនៅក្នុងលំដាប់ដែលបានសាងសង់

“1” បន្ទាប់មកចូលទៅកាន់ Exit ជាមួយនឹងសារ “n - composite”។

១.៤. ប្រសិនបើឯកតាទីមួយនៅក្នុងលំដាប់គឺនាំមុខដោយមិនមែន

“-1” បន្ទាប់មកចូលទៅកាន់ Exit ជាមួយនឹងសារ “ ន- សមាសធាតុ "។

2. ទៅកាន់ច្រកចេញដែលមានសារ “ ន- បឋមជាមួយប្រូបាប៊ីលីតេε t».

ចូរយើងយកចិត្តទុកដាក់ចំពោះការពិតដែលថានៅក្នុងលំដាប់ ខ 0,ខ 1,…,bsពាក្យបន្តបន្ទាប់នីមួយៗគឺជាការ៉េនៃម៉ូឌុលមុនមួយ។ នហើយពាក្យចុងក្រោយគឺគ្មានអ្វីលើសពីនេះទេ។ មួយ-1 ម៉ូដ ន.

ប្រូបាប៊ីលីតេនៃកំហុសតេស្តនៅពេលធ្វើម្តងទៀតគឺε≤φ( ន)/4ននោះគឺដែនកំណត់ខាងលើនៃកំហុសនៅពេលធ្វើម្តងទៀតសម្រាប់ការធ្វើតេស្ត Miller-Rabin គឺតិចជាង 2 ដងសម្រាប់ការធ្វើតេស្ត Solove-Strassen និង 4 ដងតិចជាងសម្រាប់ការធ្វើតេស្ត Fermat ។

ឧទាហរណ៍នៃការប្រើប្រាស់ការធ្វើតេស្ត Miller-Rabin៖

ន=65=64+1=26+1. r=1, ស=6. t=5.

1. ការធ្វើឡើងវិញលើកទី 1:

1.1. ក=8.

១.២. យើងបង្កើតលំដាប់៖ b0=8, b1=64=-1, b2=1,

b3=1, b4=1, b5=1, b6=1 ។

១.៣. "1" ត្រូវបានជួបប្រទះនៅក្នុងលំដាប់។

១.៤. ឯកតាទីមួយគឺនាំមុខដោយ "-1" ។

1. លើកទី 2:

1.1. ក=11.

១.២. យើងបង្កើតលំដាប់៖ b0=11, b1=56, b2=16,

b3=61, b4=16, b5=61, b6=16 ។

១.៣. មិនមាន "1" នៅក្នុងលំដាប់។

ចេញ៖ " ន- លេខផ្សំ។

កិច្ចការសម្រាប់ផ្នែកទី 2

1) អនុវត្តនីតិវិធីសម្រាប់ការបង្កើតលេខបឋមដោយប្រើវិធីសាស្ត្រស្វែងរកចៃដន្យក្នុងចំណោមលេខ 128 ប៊ីត ដែលជាប៊ីតដ៏សំខាន់បំផុតគឺ 1 និងពិនិត្យមើល

ក) ការធ្វើតេស្ត Fermat

ខ) ការធ្វើតេស្ត Solovey-Strassen

គ) ការធ្វើតេស្ត Miller-Rabin ។

ចំនួននៃការធ្វើម្តងទៀតនៃការធ្វើតេស្តប្រូបាប៊ីលីតេគួរតែដូចដែលប្រូបាប៊ីលីតេនៃកំហុសមិនលើសពី 0.1 ។ ប្រូបាប៊ីលីតេនៃកំហុសត្រូវបានកំណត់ដោយផ្អែកលើការប៉ាន់ប្រមាណεសម្រាប់ការធ្វើតេស្ត។ កំណត់ចំនួននៃការធ្វើម្តងទៀតសម្រាប់ការធ្វើតេស្ត Fermat ទៅ 50 ។

2) ប្រើនីតិវិធីនេះដើម្បីទទួលបាន 10 លេខបឋម។ សម្រាប់ការពិសោធន៍នីមួយៗ ស្វែងរកចំនួនលេខដែលបានព្យាយាមរហូតដល់ទទួលបានលេខសំខាន់។ បង្ហាញលទ្ធផលក្នុងទម្រង់តារាង។

លេខនេះគឺជាលេខពិសោធន៍ ទំ – បានរកឃើញលេខបឋម, ន – ចំនួន​លេខ​ដែល​បាន​ព្យាយាម​រហូត​ដល់​ទទួល​បាន​លេខ​សំខាន់។

ទិន្នន័យតេស្តដោយខ្លួនឯងសម្រាប់ផ្នែកទី 2

ទិន្នន័យគួរតែត្រូវបានប្រើដូចខាងក្រោមៈ

·កំណត់តម្លៃប៉ារ៉ាម៉ែត្រភាពជឿជាក់នៃការធ្វើតេស្ត t=1.

· ជំនួស​ជា​ប៉ារ៉ាម៉ែត្រ​បញ្ចូល នលេខពីជួរឈរ "លេខដែលត្រូវពិនិត្យ" ។

· ដំណើរការកម្មវិធីជាមួយនឹងប៉ារ៉ាម៉ែត្របញ្ចូលដែលបានផ្តល់ឱ្យជាច្រើន (10-20) ដង។

· ការសន្និដ្ឋានអំពីភាពត្រឹមត្រូវនៃការធ្វើតេស្តដែលបានអនុវត្តគួរតែត្រូវបានធ្វើឡើងដោយផ្អែកលើការប្រៀបធៀបនៃលទ្ធផលតេស្តជាមួយនឹងទិន្នន័យពីតារាង (ជួរឈរ "លទ្ធផលតេស្ត")។

ប្រភេទលេខ	លេខដែលត្រូវពិនិត្យ	លទ្ធផលតេស្ត
លេខបឋម			តែងតែ "សាមញ្ញ"
លេខ Carmichael			សម្រាប់ការធ្វើតេស្ត Fermat វាតែងតែ "សាមញ្ញ" សម្រាប់ការធ្វើតេស្ត Miller-Rabin និង Solovey-Strassen - ជាញឹកញាប់ "សមាសធាតុ" ជាង "សាមញ្ញ"
លេខផ្សំ, សេស, មិនមែន Carmichael			ជាញឹកញាប់ "សមាសធាតុ" ជាង "សាមញ្ញ"

ផ្នែកទី 3. បឋមដែលអាចបញ្ជាក់បាន។

ក្នុងករណីខ្លះចាំបាច់ត្រូវសាងសង់ សាមញ្ញលេខ ពោលគឺលេខដែលភាពសាមញ្ញត្រូវបានបញ្ជាក់។ ចំពោះគោលបំណងនេះមានថ្នាក់នៃការធ្វើតេស្តបឋមដែលអាចទទួលយកលេខបឋមជាលេខផ្សំ ប៉ុន្តែមិនមែនផ្ទុយមកវិញទេ។

វិធីសាស្រ្តដើម្បីទទួលបានលេខបឋមដែលបង្ហាញឱ្យឃើញគឺខុសពីវិធីសាស្រ្តដែលបានពិភាក្សាពីមុន។ គ្មានការស្វែងរកចៃដន្យត្រូវបានប្រើដើម្បីបង្កើតលេខបែបនេះទេ។ ដោយប្រើតារាងនៃលេខបឋម ទំហំតូចសាងសង់ជាមុនចំនួនត្រូវបានសាងសង់ ម(ស្មើនឹងផលគុណនៃលេខបឋមជាច្រើន ឬផលនៃលេខបឋម និងលេខចៃដន្យ) បន្ទាប់មកលេខ ន=2ម+1 ត្រូវបានពិនិត្យសម្រាប់ភាពសាមញ្ញដោយការសាកល្បងមួយក្នុងចំណោមការធ្វើតេស្តខាងក្រោម។ អត្ថប្រយោជន៍នៃវិធីសាស្រ្តនេះគឺមិនត្រឹមតែដើម្បីទទួលបានលេខសំខាន់ដែលមានការធានានោះទេ។ នប៉ុន្តែក៏ទទួលបានធាតុបង្កើតនៃក្រុមផងដែរ។ Z ន*. ដូច្នេះ លេខសំខាន់ៗដែលទំនងជាត្រូវបានប្រើប្រាស់ជាធម្មតាជាម៉ូឌុលនៃប្រព័ន្ធគ្រីបតូ ដោយផ្អែកលើបញ្ហាលោការីតដាច់ដោយឡែក ដូចជា Shamir cipher, El-Gamal cryptosystem និងស្តង់ដារហត្ថលេខាឌីជីថលដែលពាក់ព័ន្ធ GOST R 34.11-94, GOST R 34.11-2001, DSA និង ECDSA ។

៣.១. ការធ្វើតេស្តបឋមរបស់ Miller

ការធ្វើតេស្តរបស់ Miller គឺផ្អែកលើទ្រឹស្តីបទរបស់ Selfridge ។

ក្បួនដោះស្រាយសម្រាប់បង្កើតលេខបឋមដោយប្រើការធ្វើតេស្ត Miller មានដូចខាងក្រោម៖

qខ្ញុំ

2. លេខកំពុងត្រូវបានសាងសង់ ម=(ដែល qi ជាលេខបឋមចៃដន្យខុសគ្នាពីតារាង αi គឺជាចំនួនគត់ចៃដន្យ) ទំហំដែលតិចជាងទំហំដែលត្រូវការសម្រាប់លេខបឋម 1 ប៊ីត។

3. តម្លៃត្រូវបានគណនា ន=2ម+1;

4. លេខសាងសង់ នសាកល្បងដោយ Miller test ជាមួយ ប៉ារ៉ាម៉ែត្រដែលបានផ្តល់ឱ្យភាពជឿជាក់។ ប្រសិនបើលទ្ធផលតេស្តគឺអវិជ្ជមាន នោះអ្នកគួរតែត្រលប់ទៅជំហានទី 2 ហើយបង្កើតលេខថ្មី។ ម.

ការធ្វើតេស្ត Miller៖

ច្រកចូល៖ ន- លេខដែលត្រូវពិនិត្យ ន-1=https://pandia.ru/text/78/045/images/image051_14.gif" width="44" height="43">ម៉ូដ ន. ប្រសិនបើលទ្ធផលណាមួយមិនស្មើនឹងមួយនោះ សូមចូលទៅកាន់ជំហានទី 3 យកដូចខាងក្រោម ឈី. ប្រសិនបើលទ្ធផលទាំងអស់ស្មើនឹង "1" បន្ទាប់មកចូលទៅកាន់ ចាកចេញ ជាមួយនឹងសារ "ប្រហែលជា ន- លេខផ្សំ។

4. ទៅកាន់ច្រកចេញដែលមានសារ “ ន- លេខសំខាន់។

ប្រសិនបើលេខ នពីមុនត្រូវបានពិនិត្យសម្រាប់ភាពសាមញ្ញដោយការធ្វើតេស្ត Miller-Rabin probabilistic បន្ទាប់មកនៅក្នុងការធ្វើតេស្ត Miller វាគ្រប់គ្រាន់ដើម្បីឆ្លងកាត់តម្លៃ 4-6 ។ aj.

ប្រសិនបើ នគឺជាចំនួនបឋមសេស បន្ទាប់មកប្រូបាប៊ីលីតេនោះ។ នដោយ​ការ​ជ្រើសរើស​ដោយ​ចៃដន្យ​មូលដ្ឋាន 1 < ក< ន នឹងត្រូវបានសាកល្បងនៅជំហាន 3.1 មាន j(n-1)/(n-1)។

៣.២. ការធ្វើតេស្ត Pocklington

ការធ្វើតេស្ត Pocklington គឺផ្អែកលើទ្រឹស្តីបទរបស់ Pocklington និងអនុញ្ញាតឱ្យអ្នកពិនិត្យមើលភាពសំខាន់នៃលេខ។ នប្រសិនបើការពង្រីក Canonical នៃចំនួន ( ន-១) ដឹងតែផ្នែកខ្លះប៉ុណ្ណោះ។

ក្បួនដោះស្រាយសម្រាប់បង្កើតលេខបឋមដោយប្រើតេស្ត Pocklingtonបន្ទាប់៖

1. សង់តារាងនៃលេខបឋមតូចៗ qខ្ញុំ(ឬតារាងដែលត្រៀមរួចជាស្រេចត្រូវបានប្រើ);

2..gif" width="104" height="32"> - ការ​ខូច​ទ្រង់ទ្រាយ Canonical; t- ប៉ារ៉ាម៉ែត្រភាពជឿជាក់។

1. ជ្រើសរើស tចំនួនគត់ចៃដន្យផ្សេងៗ aj: 1< aj< ន.

2. សម្រាប់មនុស្សគ្រប់គ្នា ajគណនា ( ajn-1 ម៉ូដ ន. ប្រសិនបើលទ្ធផលណាមួយមិនស្មើនឹង “1” នោះសូមចូលទៅកាន់ Exit ជាមួយនឹងសារ “n គឺជាលេខផ្សំ”។

3. សម្រាប់គ្នា a ខ្ញុំប្រតិបត្តិ៖

៣.១. សម្រាប់ qj នីមួយៗគណនា () mod ន. ប្រសិនបើលទ្ធផលណាមួយស្មើនឹងមួយ បន្ទាប់មកទៅកាន់ជំហានទី 3 យក a បន្ទាប់ ខ្ញុំ. ប្រសិនបើលទ្ធផលទាំងអស់មិនស្មើនឹង “1” នោះសូមចូលទៅកាន់ Exit ជាមួយនឹងសារ “ ន- លេខសំខាន់។

4. ទៅកាន់ច្រកចេញដែលមានសារ “ប្រហែល ន- លេខផ្សំ។

ប្រសិនបើ ន= RF+1 – លេខ​ដំបូង​សេស, F>https://pandia.ru/text/78/045/images/image055_12.gif" width="99" height="29">, GCD(R, F)=1 បន្ទាប់មកប្រូបាប៊ីលីតេដែលជ្រើសរើសដោយចៃដន្យ 1 < ក< ននឹងបំពេញលក្ខខណ្ឌនៃទ្រឹស្តីបទរបស់ Pocklington មាន https://pandia.ru/text/78/045/images/image057_10.gif" width="28" height="27 src=">-1<63.

ន- 1=4020=22·3·5·67។ F=67, R=22·3·5=60។

លក្ខខណ្ឌត្រួតពិនិត្យ៖

ក= 2.

1) 24020 mod 4021=1 ។

2) 24020/67 mod 4021 = 260 mod 4021=1452 ។

ចេញ៖ ន= 4021 គឺជាលេខដំបូង។

(ចំណាំថាប្រូបាប៊ីលីតេដែលជ្រើសរើសដោយចៃដន្យ កនឹងបំពេញលក្ខខណ្ឌនៃទ្រឹស្តីបទរបស់ Pocklington សម្រាប់ឧទាហរណ៍នេះគឺ (1-1/67)≈0.985)។

៣.៣. នីតិវិធីសម្រាប់ការបង្កើតលេខបឋម GOST R 34.10-94

ស្ដង់ដារហត្ថលេខាឌីជីថលក្នុងស្រុក GOST R34.10-94 ណែនាំពីនីតិវិធីសម្រាប់ការបង្កើតលេខសំខាន់ៗនៃទំហំដែលបានផ្តល់ឱ្យ។ GOST R 34.10-2001 ក៏ចេញវេជ្ជបញ្ជាអំពីការប្រើប្រាស់នីតិវិធីនេះផងដែរ។ នីតិវិធីនេះគឺផ្អែកលើទ្រឹស្តីបទរបស់ Diemitko ។

ទ្រឹស្តីបទ Diemitko

អនុញ្ញាតឱ្យ ន= qR+ 1, កន្លែងណា q- លេខបឋម រ- សូម្បីតែ, រ<4(q+1).

ប្រសិនបើមាន ក< ន: 1) មួយ-1≡1(mod ន); 2) 1 (ម៉ូដ ន), នោះ។ ន- លេខបឋម។

ដូច្នេះប្រសិនបើយើងមានលេខសំខាន់ qបន្ទាប់មក ឆ្លងកាត់លេខគូ រ, បង្កើតលេខ ន= qR+ 1 និងសាកល្បងពួកវាសម្រាប់ភាពសាមញ្ញយោងទៅតាមទ្រឹស្តីបទរបស់ Diemitko រហូតដល់យើងទទួលបានលេខសំខាន់។ ដោយប្រើលេខលទ្ធផល អ្នកអាចបង្កើតលេខសំខាន់ផ្សេងទៀត ហើយបន្តរហូតដល់ទំហំលេខដែលត្រូវការ។

នេះគឺជាក្បួនដោះស្រាយសម្រាប់ផ្លាស់ទីពីលេខបឋមតូចជាង q: |q|= ច្រើនទៀត ទំ: |ទំ|=tប្រើក្នុង GOST ។ ξ លេចឡើងក្នុងនីតិវិធីគឺជាអថេរចៃដន្យដែលចែកចាយស្មើៗគ្នានៅលើ (0,1) ដែលទទួលបានដោយប្រើម៉ាស៊ីនភ្លើងស្របគ្នាលីនេអ៊ែរ។ រាល់ពេលដែលនៅជំហានទី 1 តម្លៃថ្មីនៃξត្រូវបានទទួល។

ក្បួនដោះស្រាយសម្រាប់ផ្លាស់ទីពីលេខបឋមតូចទៅលេខធំជាង៖

ច្រកចូល៖ t- វិមាត្រដែលត្រូវការនៃលេខបឋម q- លេខបឋម៖ | q|=.

1..gif" width="15 height=20" height="20">1(mod ទំ) បន្ទាប់មកយើងទៅច្រកចេញ។

6. គណនា យូ= យូ+2. ចូរយើងត្រលប់ទៅជំហានទី 3 ។

ចេញ៖ ទំ- លេខបឋម។

ពាក្យទីមួយក្នុងការសាងសង់លេខ N ក្នុងជំហានទី 1 ផ្តល់នូវទំហំលេខដែលត្រូវការអប្បបរមា ទំហើយទីពីរណែនាំធាតុចាំបាច់នៃភាពចៃដន្យទៅក្នុងនីតិវិធីសម្រាប់ការស្វែងរកលេខបឋមថ្មី។

ការត្រួតពិនិត្យនៅក្នុងជំហានទី 4 គឺចាំបាច់ដើម្បីធានាថាលេខ ទំមិនបានលើសពីដែនកំណត់ខាងលើរបស់វាទេ ហើយការត្រួតពិនិត្យនៅជំហានទី 5 គឺជាការត្រួតពិនិត្យលក្ខខណ្ឌនៃទ្រឹស្តីបទ Diemitko សម្រាប់ ក=2.

ឧទាហរណ៍

ច្រកចូល៖ t = 4, q= 3=2

1. N=0 " style="margin-left:-101.3pt;border-collapse:collapse;border:none">

លទ្ធផលតេស្តប្រូបាប៊ីលីតេ

នៅទីនេះ № គឺជាលេខនៃការពិសោធន៍ p គឺជាលេខបឋមដែលបានសាងសង់ ហើយនៅក្នុងជួរទីបីគឺជាលទ្ធផលនៃការពិនិត្យលេខដែលបានសាងសង់ជាមួយនឹងការធ្វើតេស្តប្រូបាប៊ីលីតេ (+ ឬ -) k គឺជាចំនួនលេខបដិសេធដែលត្រូវបានកំណត់ថាជាលេខបឋមដោយ ការធ្វើតេស្តប្រូបាប៊ីលីតេ។

ចំនួននៃការធ្វើម្តងទៀតនៃការធ្វើតេស្តប្រូបាប៊ីលីតេគួរតែដូចដែលប្រូបាប៊ីលីតេនៃកំហុសមិនលើសពី 0.1 ។

ទិន្នន័យតេស្តដោយខ្លួនឯងសម្រាប់ផ្នែកទី 3

សម្រាប់ការធ្វើតេស្ត Miller និង Pocklington

1) ការធ្វើតេស្តដែលបានអនុវត្តគួរតែត្រូវបានពិនិត្យជាមួយនឹងតារាងនៃលេខសមាសធាតុ។ ជា ប៉ារ៉ាម៉ែត្របញ្ចូលនៃការធ្វើតេស្តដែលបានអនុវត្ត អ្នកគួរតែជំនួសលេខពីជួរឈរ "លេខដែលត្រូវពិនិត្យ" ប្រសិនបើលទ្ធផលតេស្តបង្ហាញសារថាលេខនេះត្រូវបានបដិសេធ នោះអ្នកគួរតែបន្តទៅដំណាក់កាលបន្ទាប់នៃការផ្ទៀងផ្ទាត់។ ប្រសិនបើយ៉ាងហោចណាស់មួយក្នុងចំណោមលេខទាំងនេះត្រូវបានទទួលស្គាល់ដោយការធ្វើតេស្តថាជាបឋម នោះការធ្វើតេស្តត្រូវបានអនុវត្តដោយមានកំហុស។

2) បន្ទាប់មកអ្នកគួរតែប្រើតារាងយោងទៅតាមការធ្វើតេស្តដែលបានអនុវត្ត។ ដើម្បីពិនិត្យមើលតារាងទាំងនេះ អ្នកគួរតែជំនួសទិន្នន័យពីតារាងជាប៉ារ៉ាម៉ែត្របញ្ចូល (សម្រាប់ការធ្វើតេស្ត Miller លេខសំខាន់ដែលត្រូវបានសាកល្បងគឺ ទំនិងការពង្រីក Canonical នៃចំនួន ( ទំ-1) សម្រាប់ការធ្វើតេស្ត Pocklington - លេខសំខាន់កំពុងត្រូវបានសាកល្បង ទំលេខ R និងការពង្រីក Canonical នៃលេខ F) ។ កំណត់ចំនួននៃការធ្វើតេស្តម្តងទៀត t=1. ពិនិត្យលេខ ទំការធ្វើតេស្តនេះច្រើនដង (30-100) ។ បន្ទាប់មកគណនាប្រេកង់នៃព្រឹត្តិការណ៍ នៅពេលដែលលេខបឋមដែលកំពុងត្រូវបានសាកល្បងត្រូវបានទទួលយកជាលេខផ្សំ ហើយប្រៀបធៀបតម្លៃនេះជាមួយនឹងទិន្នន័យពីជួរឈរ "ប្រូបាប៊ីលីតេនៃកំហុស" ។ ប្រសិនបើទិន្នន័យទាំងនេះមានចំនួនប្រហាក់ប្រហែលនឹងតម្លៃប្រេកង់ដែលបានគណនា នោះការធ្វើតេស្តត្រូវបានអនុវត្តយ៉ាងត្រឹមត្រូវ។

សម្រាប់នីតិវិធីបង្កើតលេខ GOST 31.10-94

ដើម្បីពិនិត្យ ការងារមន្ទីរពិសោធន៍អ្នកគួរតែកំណត់ប៉ារ៉ាម៉ែត្រ ξ = 0 (នោះគឺកម្ចាត់ចៃដន្យ) ។ បន្ទាប់មកអ្នកគួរតែជំនួសទិន្នន័យពីតារាងជាប៉ារ៉ាម៉ែត្របញ្ចូល ( qនិង t) លទ្ធផលត្រូវតែផ្គូផ្គងតម្លៃពីជួរឈរ "លេខដែលបានសាងសង់" ។

តារាងនៃចំនួនសមាសធាតុ

លេខដែលត្រូវពិនិត្យ (ទំ)	ការរលួយ ទំ-1	ការរលួយច		លទ្ធផលតេស្ត
				តែងតែបដិសេធ