Символ Якобі
Символ Якобі — функція в теорії чисел, що узагальнює символ Лежандра для довільних непарних натуральних чисел :
- Якщо є простим числом, то символ Якобі дорівнює символу Лежандра.
- Якщо розклад на прості множники має вигляд , то символ Якобі рівний:
- де в правій частині стоять символи Лежандра.
Символ запровадив в 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.