Кіріспе
Ферманың ықтимал біріншілік сынағынан өткен құрама сан. Сандар теориясында Ферма псевдожақ сандары Ферманың кіші теоремасынан туындаған псевдожақ сандардың ең маңызды класын құрайды.
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Әлсіз псевдопримдер
b негізінде қанағаттандыратын n құрама саны әлсіз псевдожақ сан деп аталады. a негізіндегі псевдожақ сан (әдеттегі анықтама бойынша) осы шартты қанағаттандырады. Керісінше, негізбен өзара жай әлсіз псевдожақ сан әдеттегі мағынада псевдожақ сан болып табылады, әйтпесе бұл мүмкін немесе мүмкін емес. b = 1, 2 негізіндегі ең кіші әлсіз псевдожақ сандар: 4, 341, 6, 4, 4, 6, 6, 4, 6, 10, 4, 14, 6, 4, 4, 6, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 6, 9, 4, 38, 6, 4, 6, 4, 6, 4, 6, 46, 4, 4, 10. Барлық мүшелер ең кіші Кармайкл санынан кем немесе тең, ол 561-ге тең. 561-ден басқа, жоғарыдағы тізбекте тек жартылай жай сандар ғана кездесе алады, бірақ 561-ден кіші барлық жартылай жай сандар кездеспейді. Жоғарыдағы тізбектерде 561-ден кіші pq (p ≤ q) жартылай жай саны тек қана p − 1 саны q − 1 санына бөлінсе ғана кездеседі. (Сілтеме) Сонымен қатар, n негізіндегі ең кіші псевдожақ сан (оны n-нен асыру міндетті емес) көбінесе жартылай жай болады, алғашқы қарсы мысал (648) = 385 = 5 × 7 × 11. Егер n > b болса, олар (b = 1, 2 үшін) 4, 341, 6, 6, 10, 14, 9, 12, 15, 22, 15, 21, 20, 34, 25, 38, 21, 28, 33, 25, 28, 27, 39, 36, 35, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51. Кармайкл сандары барлық негіздерге әлсіз псевдожақ сандар болып табылады. 2 негізіндегі ең кіші жұп әлсіз псевдожақ сан 161038 (қараңыз).
4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10,
All terms are less than or equal to the smallest Carmichael number, 561. Except for 561, only semiprimes can occur in the above sequence, but not all semiprimes less than 561 occur, a semiprime pq (p ≤ q) less than 561 occurs in the above sequences if and only if p − 1 divides q − 1. (see ) Besides, the smallest pseudoprime to base n (also not necessary exceeding n) is also usually semiprime, the first counterexample is (648) = 385 = 5 × 7 × 11. If we require n > b, they are (for b = 1, 2, )
4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51,
Carmichael numbers are weak pseudoprimes to all bases. The smallest even weak pseudoprime in base 2 is 161038 (see ).
Эйлер-Жакоби псевдопримдері
Тағы бір тәсіл – псевдопрималдылықтың күрделірек түсініктерін қолдану, мысалы, күшті псевдопрималар немесе Эйлер-Жакоби псевдопрималары, мұндай сандар үшін Кармайкл сандарына баламасы жоқ. Бұл Solovay-Strassen біріншілік тесті, Baillie-PSW біріншілік тесті және Miller-Rabin біріншілік тесті сияқты ықтималдық алгоритмдерге алып келеді, олар "кәсіптік деңгейдегі" жай сандар деп аталады. Кәсіптік деңгейдегі жай сандар – біріншілігі "расталмаған" (яғни, қатаң түрде дәлелденбеген), бірақ Миллер-Рэбин тесті сияқты сынақтан өткен, сәтсіздікке ұшыру ықтималдығы нөлден жоғары, бірақ кез келгендей төмен болатын бүтін сандар.
Қолданбалар
Мұндай псевдопримдердің сирек кездесуінің маңызды практикалық салдары бар. Мысалы, RSA сияқты ашық кілтті криптография алгоритмдеріне үлкен жай сандарды жылдам табу қажет. Жай сандарды жасаудың әдеттегі алгоритмі – кездейсоқ тақ сандарды жасап, оларды жайлыққа тексеру. Алайда, детерминистік жайлық тесттері баяу. Егер пайдаланушы табылған санның жай сан емес, псевдоприм болуына өте аз мүмкіндікке келісуге дайын болса, Ферматтың жайлық тестісін әлдеқайда жылдам және қарапайым пайдалануға болады.