●
Техникалық ғылымдар
ҚазҰТУ хабаршысы №2 2014
307
cалыстырмалар орынды. Бұл дегеніңіз, а
р-1
-дің р-ға бөліндінің қалдығы 1-ге тең деген сөз, сол
сияқты а
р
-ның p-ға бөліндісінің қалдығы a-ға тең. (Ферманың кіші теоремасы) [3].
Жай санның басқа да қажетті шарттары бар.
Сандардың жай сан екендігінің жеткілікті шарты жай сандарға және тек қана жай сандарға
берілген сандардың теориялық-сандық қасиеттері болып табылады. Төмендегі теоремаларға
негізделген осы шарттарды қанағаттандыратын негізгі мысалдарды да келтіреміз:
1. Вильсон теоремасы. Егер р- жай сан болса, онда төмендегі салыстырма орынды:
(р-1)!+1=0 (mod p) (1.6)
Кері тұжырымдама да орынды. [9].
2. Лейбниц теоремасы. Егер р- жай сан болса онда төмендегі салыстырма орынды:
(p-2)! -1 ≡ 0 (mod p) (1.7)
Бұған кері тұжырымдама да орынды [8].
3. Серпинский теоремасы. Егер p = 4k +1 түріндегі сан болып, төмендегі
салыстырма орындалса:
+1 ≡ 0 (mod p) (1.8)
онда р- саны жай сан болады [8].
Бұдан басқа да санның жай сан шарттарын беретін теоремалар бар.
Қазіргі таңда сандарды жай санға тексеру сандар теориясында ең өзекті мәселелердің бірі
болып табылыды, себебі жай сандарды криптографияда жалпы қолжетімді байланыс құралдары:
интернет, телефон, ұялы байланыс тағы басқалар арқылы ақпарат алмасуды шифрлауда
пайдаланумен байланысты. Сонда жай санға тексерудің тағы бір тәсілі бар. Ол - факторизация
жәрдемімен (сандарды жай көбейткіштерге жіктеу амалы) анықтау, бірақ бүгінгі таңда факторизация
әдісі қиындығы көп әдіс болып саналады.
Санды жай санға тексеру тесті екі категорияға бөлінеді: ықтималды және детерминирленген
яғни шартсыз.
Санның жай сан екендігін тексеру үшін бірнеше тесттер бар, мысалы, Соловей-Штрассен тесті,
Миллер-Рабин тесті, Адлеман алгоритмі, Померанс, Румель алгоритмі, Ленстр алгоритмі, Ферма
теоремасымен санды тексеру, Ленстр-Коен алгоритмі, Адлеман-Хуанг алгоритмі (1972) тағы
басқалар. Жоғарыда аталған барлық әдістер мен алгоритмдер ықтималды болып табылады. 2002
жылға дейін төмендегі детерминирленген шартсыз тесттер арнайы сандар үшін ғана мәлім болған:
Люк-Лемер тесті Мерсенн сандары үшін, Пепин тесті, Ферма сандары үшін, Люк-Лемер-Ризель тесті
Ризель сандары үшін, Прот теоремасы Прот сандары үшін.
2002 жылы ғана үнді математиктері Агравал, Кайала және Саксеналар сандарды жай санға
тексерудің детерминирленген алгоритмін ұсынды. Бұл алгоритм Ферманың кіші теоремасына
негізделген болып, оның кейбір кемшілік тұстарын жетілдірген. Бірақ практикада қолданысқа ие
емес, себебі ол көп операциялы, және бірнеше жетілдіруден кейін де O(
),
арифметикалық операция ретінде бағалануда [9], [10], [11].
Бүгінгі күнге дейін криптографияда RSA жүйесінде көп таңбалы сандарды ашық пайдалануда,
оларды 100 пайызға кепілдікпен жай санға тексеру мүмкін емес және жай көбейткіштерге жіктеудің
(факторизация) мүмкіншілігі жоқ. Бұл үлкен сандардың жай санға тексеруде
Достарыңызбен бөлісу: