Символ Якобі

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Символ Якобі — в теорії чисел узагальнення символу Лежандра для довільних додатних непарних цілих чисел:

якщо розклад на прості множники має вигляд , то символ Якобі рівний:

де в правій частині є звичайні символи Лежандра.

Якщо є простим числом то символ Якобі дорівнює символу Лежандра.

Введена в 1837 році Карлом Якобі.

Властивості[ред. | ред. код]

Якщо , то
тоді і тільки тоді, коли і не є взаємно простими
якщо
якщо
якщо або
якщо або

Узагальнений квадратичний закон взаємності:

Приклад обчислень[ред. | ред. код]

Алгоритм[ред. | ред. код]

ЯКОБІ(a, n)[1]:73

Вхід: непарне ціле число і ціле

Вихід: символ Якобі (відповідно символ Лежандра, якщо просте).

  1. Якщо тоді повернути(0).
  2. Якщо тоді повернути(1).
  3. Записати де непарне.
  4. Якщо парне, тоді покласти Інакше, покласти якщо або покласти якщо
  5. Якщо і тоді покласти
  6. Покласти
  7. Якщо тоді повернути(s); інакше повернути(ЯКОБІ).

Примітки[ред. | ред. код]

  1. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. с. 73. ISBN 0-8493-8523-7. 

Література[ред. | ред. код]