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

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

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

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

Введена в 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. 

ЛітератураРедагувати