Символ Якобі
Символ Якобі — функція в теорії чисел, що узагальнює символ Лежандра для довільних непарних натуральних чисел :
- Якщо є простим числом, то символ Якобі дорівнює символу Лежандра.
- Якщо розклад на прості множники має вигляд , то символ Якобі рівний:
- де в правій частині стоять символи Лежандра.
Символ запровадив в 1837 році Карл Якобі.
Властивості
ред.- Якщо , то
- тоді і тільки тоді, коли і не є взаємно простими
- якщо
- якщо
- якщо або
- якщо або
Узагальнений квадратичний закон взаємності:
Приклад обчислень
ред.Алгоритм
ред.ЯКОБІ(a, n)[1]
Вхід: непарне ціле число і ціле
Вихід: символ Якобі (відповідно символ Лежандра, якщо просте).
- Якщо тоді повернути(0).
- Якщо тоді повернути(1).
- Записати де непарне.
- Якщо парне, тоді покласти Інакше, покласти якщо або покласти якщо
- Якщо і тоді покласти
- Покласти
- Якщо тоді повернути(s); інакше повернути( ЯКОБІ ).
Див. також
ред.Примітки
ред.- ↑ Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. с. 73. ISBN 0-8493-8523-7.
Література
ред.- Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — Москва : Мир, 1987. — 416 с.(рос.)
- Виноградов И. М. (1952). Основы теории чисел. М.: ГИТТЛ.
- Богуш В. М., Мухачов В. А. (2006). Криптографічні застосування елементарної теорії чисел (PDF). К.: ДУІКТ. с. 176. ISBN 966-2970-06-1.