Simvol Yakobi a n displaystyle left frac a n right funkciya v teoriyi chisel sho uzagalnyuye simvol Lezhandra dlya dovilnih neparnih naturalnih chisel n displaystyle n Yaksho n displaystyle n ye prostim chislom to simvol Yakobi dorivnyuye simvolu Lezhandra Yaksho rozklad n displaystyle n na prosti mnozhniki maye viglyad p 1 c 1 p 2 c 2 p k c k displaystyle p 1 c 1 p 2 c 2 cdots p k c k to simvol Yakobi rivnij a n a p 1 c 1 a p 2 c 2 a p k c k displaystyle left frac a n right left frac a p 1 right c 1 left frac a p 2 right c 2 cdots left frac a p k right c k de v pravij chastini stoyat simvoli Lezhandra Simvol zaprovadiv v 1837 roci Karl Yakobi Zmist 1 Vlastivosti 2 Priklad obchislen 3 Algoritm 4 Div takozh 5 Primitki 6 LiteraturaVlastivosti RedaguvatiYaksho a b mod n displaystyle a b mod n nbsp to a n b n displaystyle left frac a n right left frac b n right nbsp a n 0 displaystyle left frac a n right 0 nbsp todi i tilki todi koli a displaystyle a nbsp i n displaystyle n nbsp ne ye vzayemno prostimi a b n a n b n displaystyle left frac ab n right left frac a n right left frac b n right nbsp a m n a m a n displaystyle left frac a mn right left frac a m right left frac a n right nbsp 1 n 1 displaystyle left frac 1 n right 1 nbsp 1 n 1 displaystyle left frac 1 n right 1 nbsp yaksho n 1 mod 4 displaystyle n 1 mod 4 nbsp 1 n 1 displaystyle left frac 1 n right 1 nbsp yaksho n 3 mod 4 displaystyle n 3 mod 4 nbsp 2 n 1 displaystyle left frac 2 n right 1 nbsp yaksho n 1 mod 8 displaystyle n 1 mod 8 nbsp abo n 7 mod 8 displaystyle n 7 mod 8 nbsp 2 n 1 displaystyle left frac 2 n right 1 nbsp yaksho n 3 mod 8 displaystyle n 3 mod 8 nbsp abo n 5 mod 8 displaystyle n 5 mod 8 nbsp Uzagalnenij kvadratichnij zakon vzayemnosti m n n m 1 m 1 n 1 4 displaystyle left frac m n right left frac n m right 1 frac m 1 n 1 4 nbsp Priklad obchislen Redaguvati 1001 9907 9907 1001 898 1001 2 1001 449 1001 449 1001 displaystyle left frac 1001 9907 right left frac 9907 1001 right left frac 898 1001 right left frac 2 1001 right left frac 449 1001 right left frac 449 1001 right nbsp 1001 449 103 449 449 103 37 103 103 37 displaystyle left frac 1001 449 right left frac 103 449 right left frac 449 103 right left frac 37 103 right left frac 103 37 right nbsp dd 29 37 37 29 8 29 4 29 2 29 1 displaystyle left frac 29 37 right left frac 37 29 right left frac 8 29 right left frac 4 29 right left frac 2 29 right 1 nbsp dd Algoritm RedaguvatiYaKOBI a n 1 73Vhid neparne cile chislo n 3 displaystyle n geq 3 nbsp i cile a 0 a lt n displaystyle a 0 leq a lt n nbsp Vihid simvol Yakobi a n displaystyle left frac a n right nbsp vidpovidno simvol Lezhandra yaksho n displaystyle n nbsp proste Yaksho a 0 displaystyle a 0 nbsp todi povernuti 0 Yaksho a 1 displaystyle a 1 nbsp todi povernuti 1 Zapisati a 2 e a 1 displaystyle a 2 e a 1 nbsp de a 1 displaystyle a 1 nbsp neparne Yaksho e displaystyle e nbsp parne todi poklasti s 1 displaystyle s gets 1 nbsp Inakshe poklasti s 1 displaystyle s gets 1 nbsp yaksho n 1 mod 8 displaystyle n equiv pm 1 pmod 8 nbsp abo poklasti s 1 displaystyle s gets 1 nbsp yaksho n 3 mod 8 displaystyle n equiv pm 3 pmod 8 nbsp Yaksho n 3 mod 4 displaystyle n equiv 3 pmod 4 nbsp i a 1 3 mod 4 displaystyle a 1 equiv 3 pmod 4 nbsp todi poklasti s s displaystyle s gets s nbsp Poklasti n 1 n mod a 1 displaystyle n 1 gets n mod a 1 nbsp Yaksho a 1 1 displaystyle a 1 1 nbsp todi povernuti s inakshe povernuti s displaystyle s times nbsp YaKOBI n 1 a 1 displaystyle n 1 a 1 nbsp Div takozh RedaguvatiHarakter DirihlePrimitki Redaguvati Alfred J Menezes Paul C van Oorschot and Scott A Vanstone 1996 Handbook of Applied Cryptography CRC Press s 73 ISBN 0 8493 8523 7 Literatura RedaguvatiAjerlend K Rouzen M Klassicheskoe vvedenie v sovremennuyu teoriyu chisel Moskva Mir 1987 416 s ros Vinogradov I M 1952 Osnovy teorii chisel M GITTL Bogush V M Muhachov V A 2006 Kriptografichni zastosuvannya elementarnoyi teoriyi chisel K DUIKT s 176 ISBN 966 2970 06 1 Otrimano z https uk wikipedia org w index php title Simvol Yakobi amp oldid 40373095
