"Человек - самое уязвимое место в системе безопасности.."

Символы Лежандра и Якоби

Символ Лежандра

Символ Лежандра (a/p) определяется равенством a/p = 1, если разрешимо сравнение x2 ≡ a (mod p), и (a/p) = -1 в противном случае. В первом сравнении a является квадратичным вычетом по модулю p и квадратичным невычетом во втором. Исходя из этого:

  • (a/p) = ± 1

К примеру — квадратичные вычеты по mod 7 — 1,2,4; невычеты — 3,5,6.

Если g — первообразный корень по mod p, то каждое целое g2k — квадратичный вычет, а каждое целое g2k+1 — квадратичный невычет. Сравнение (gt)2 ± g2k+1 (mod p) влечёт g|2k +1 -2t| ± 1 (mod p), а это значит то, что 2k +1 -2t должно делиться на (p — 1). А это противоречие, так как первое число нечётно, а второе чётно. Значит есть (p — 1)/2 квадратичных вычетов и невычетов по mod p. Такие представления влекут за собой следующую важную характеристику «1»:

  • (ab/p) = (a/p) × (b/p), где (a,p) = (b,p) = 1

Критерий Эйлера

Если (a,p) = 1, то (a/p) ± = a (p-1)/2 (mod p).

Доказательство: ap-1 — 1 = (a(p-1)/2 — 1) × (a(p-1)/2 + 1) ± 0 (mod p). Множители a(p-1)/2 — 1 и a(p-1)/2 + 1 различаются на 2. Поэтому только один из них делится на p. Для a = g2k это будет первый множитель. Вытекает следующая характеристика (-1/p) = :

  • 1, p ± 1 (mod 4)
  • -1, p ± 3 (mod 4)

Символ Якоби

Символ Якоби является обобщением символа Лежандра и нужен для упрощения вычисления символа Лежандра. Пусть р — нечётное натуральное число, р = р1, p2 … ps — разложение на простые множители. Для любого целого а, (а, р) = 1, символ Якоби вычисляется по формуле:

  • (a/p) = (a/p1) × (a/p2) × … (a/ps)

Характеристика «2» символа Якоби: a ± b (mod p) ⇒ (a/p) = (b/p).

Доказательство: Если a ± b (mod p) ⇒ a ± b (mod pi), то (a/pi) = (b/pi), i = 1,2 … , s.

Характеристика «3» символа Якоби: ((a1,a2 … , ak)/p) = (a1/p) × (a2/p) … (ak/p).

Доказательство: По условию, левая часть равна:

  • (a1,a2 … , ak)/p1) × (a1,a2 … , ak)/p2) … (a1,a2 … , ak)/ps)

Первый множитель равен по характеристике (1):

  • (a1/p1) × (a2/p1) … (ak/p1)

Реализовывать эту характеристику можно ко всем множителям, после группирования получаем правую часть.

Характеристика «4» символа Якоби: (-1/p) = (-1)(p-1)/2.

Доказательство:

  • (-1/p) = (-1/p1) × (-1/p2) … (-1/ps) = (-1)(p1-1)/2 + (p2-1)/2 + … + (ps-1)/2

С другой стороны, можно воспользоваться легко проверяемым утверждением. Если a и b нечётные, то

  • ½ (ab — 1) ± ½(a — 1) + ½(b — 1) (mod 2)