Кіріспе
Сан теориясында Лежандр символының жалпылауы
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 3 0 1 −1 5 0 1 −1 −1 1 7 0 1 1 −1 1 −1 −1 9 0 1 1 0 1 1 0 1 1 11 0 1 −1 1 1 1 −1 −1 −1 1 −1 13 0 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 15 0 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1 17 0 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1
Жоғарыдағы k (жоғарғы қатар бойынша) және n (сол жақ бағана бойынша) үшін Якоби символы. Тек 0 ≤ k < n көрсетіледі, өйткені (2) ережеге сәйкес кез келген басқа k-ны модуль n-ге дейін азайтуға болады. Квадраттық қалдықтар сары түспен белгіленген. Якоби символы -1-ге тең жазбалар квадраттық қалдықтар емес екенін ескеріңіз, ал егер k, n-ге өзімен бөлінбейтін жағдайда квадраттық қалдық болса, онда , бірақ Якоби символы 1-ге тең барлық жазбалар квадраттық қалдықтар емес (1=n = 9 және 1=n = 15 қатарларын қараңыз). Сондай-ақ, n немесе k квадрат болса, барлық мәндер теріс емес екенін ескеріңіз. Якоби символы Лежандр символының жалпылауы болып табылады. 1837 жылы Якоби ұсынған, ол модульдік арифметика және сан теориясының басқа салаларында теориялық қызығушылық тудырады, бірақ оның негізгі қолданылуы есептеулік сан теориясында, әсіресе жайлылықты тексеру және бүтін сандарды жіктеуде; бұлар өз кезегінде криптографияда маңызды.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 3 0 1 −1 5 0 1 −1 −1 1 7 0 1 1 −1 1 −1 −1 9 0 1 1 0 1 1 0 1 1 11 0 1 −1 1 1 1 −1 −1 −1 1 −1 13 0 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 15 0 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1 17 0 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1
Jacobi symbol for various k (along top) and n (along left side). Only 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if k is a quadratic residue modulo a coprime n, then , but not all entries with a Jacobi symbol of 1 (see the 1=n = 9 and 1=n = 15 rows) are quadratic residues. Notice also that when either n or k is a square, all values are nonnegative. The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.
Якоби символын есептеу
Жоғарыда келтірілген формулалар Якоби символын есептеу үшін тиімді [[Big O]] белгісіндегі алгоритмге әкеледі, бұл екі санның ең үлкен ортақ бөлшегін (gcd) табу үшін Евклид алгоритміне ұқсас. (Бұл 2-қағиданы ескере отырып, таңқаларлық емес.) 2-қағиданы қолданып, "бөлшектің жоғарғы бөлігін" "бөлшектің төменгі бөлігіне" қатысты қысқартыңыз. 9-қағиданы қолданып, кез келген жұп "бөлшектің жоғарғы бөлігін" шығарып алыңыз. Егер "бөлшектің жоғарғы бөлігі" 1-ге тең болса, 3 және 4-қағидалар 1 нәтижесін береді. Егер "бөлшектің жоғарғы бөлігі" мен "бөлшектің төменгі бөлігі" өзара жай болмаса, 3-қағида 0 нәтижесін береді. Әйтпесе, "бөлшектің жоғарғы бөлігі" және "бөлшектің төменгі бөлігі" енді тақ, оң, өзара жай бүтін сандар болады, сондықтан 6-қағиданы қолданып, символды ауыстырып, содан кейін 1-қадамға оралыңыз. Төмендегі кодтан басқа, Ризельде Паскаль тілінде де бар.
Есептеу үлгісі
Лежандр символы тек тақ алғашқы сандар үшін ғана анықталған. Ол Якоби символымен бірдей қағидаларды сақтайды (яғни, өзаралық заңдылық және және үшін қосымша формулалар, сондай-ақ "бөлшектің" көбейтілу қасиеті). Есеп: 9907 саны жай сан болған жағдайда, есептеңіз.
Якоби символын қолдану
Екі есептеудің айырмашылығы – Лежандр символы қолданылғанда, символдың мәнін өзгерту алдында "бөлшектің жоғарғы бөлігін" жай сандардың дәрежелеріне жіктеу қажет. Бұл Лежандр символын пайдалану арқылы есептеуді Якоби символын пайдаланудан едәуір баяу етеді, себебі бүтін сандарды жіктеуге арналған белгілі полиномиалдық уақыт алгоритмі жоқ. Шындығында, Якоби осы себепті осы символды енгізген.
Бастылық сынағы
Якоби және Легендре символдары тағы бір жағынан ерекшеленеді. Егер Эйлердің критерий формуласы құрама санның модулі ретінде қолданылса, нәтиже Якоби символының мәні болуы мүмкін немесе болмауы мүмкін, тіпті -1 немесе 1 болмауы да мүмкін. Мысалы,
Егер n санының жай немесе құрама екені белгісіз болса, біз кездейсоқ a санын таңдап, Якоби символын есептеп, оны Эйлер формуласымен салыстыра аламыз; егер олар n модулі бойынша өзгеше болса, онда n құрама сан; егер олар a-ның көптеген әртүрлі мәндері үшін n модулі бойынша бірдей қалдық болса, онда n "жақсы жай сан" болып саналады. Бұл Соловай-Штрассен жайлық тестінің және Бейли-ПСВ жайлық тестісі мен Миллер-Рабин жайлық тестісі сияқты оның жетілдірілген түрлерінің негізі болып табылады. Тікелей емес қолданыс ретінде, оны Лукас-Лехмер жайлық тестін орындау кезінде қателерді анықтау үшін пайдалануға болады, ол тіпті қазіргі заманғы компьютерлік жабдықта Мерсенн сандарын өңдеу кезінде бірнеше аптаға созылуы мүмкін (2018 жылдың желтоқсанына дейін белгілі ең үлкен Мерсенн жай саны). Аталған жағдайларда Якоби символы:
Бұл соңғы қалдық үшін де орындалады, сондықтан ықтимал жарамдылықты тексеру үшін қолданылуы мүмкін. Алайда, егер жабдықта қате пайда болса, нәтиже 0 немесе 1 болуының 50% ықтималдығы бар және келесі мүшелерде өзгермейді (басқа қате пайда болып, оны қайтадан 1-ге өзгермесе).