Вычисление символа Якоби
Не получается написать правильную реализацию алгоритма вычисления символа Якоби J(Q/P). Сначала сам алгоритм: Вход: Q , P — целые числа. Выход: значение символа Якоби. 1) s = 0, u = Q, v = P. 2) Вычисляем r — наименьший положительный остаток при делении u на v . Вычисляем целое k >= 0 и нечетное t , такие, что r = t * 2^k . Вычисляем `s = s + k * (v^2 — 1)/8 + (t — 1)*(v — 1)/4 (mod 2) 3) Если t = 1 , то символ Якоби равен (-1)^s . Конец. 4) Если t >= 3 , то u = v , v = t , переходим на шаг 2. Реализация:
#include int jacobi(int q, int p) < int s = 0, u = q, v = p; int r, k, t; do< // Вычисляем r - наименьший положительный остаток при делении u на v r = u % v; // Вычисляем целое k >= 0 и нечетное t: r = t * 2^k k = t = 0; while(r % 2 == 0) < k++; // Показатель степени двойки в числе r r >>= 1; // Делим r на 2 > t = r; // В t находится результат деления r на 2^k s = (s + k * (v*v - 1)/8 + (t - 1)*(v - 1)/4) % 2; if(t == 1) return (s) ? 1 : -1; // Новая итерация u = v; v = t; >while(t >= 3); > int main()
Здесь J(-104, 997) должен быть равен -1, а моя реализация выдает 1. Еще тесты из хелпа Maple: jacobi(12, 3) = 0 , jacobi(28, 21) = 0 , jacobi(6, 11) = -1 , jacobi(226, 135) = 1 , jacobi(26, 35) = -1 , jacobi(-286, 4272943) = 1 , jacobi(888, 1999) = -1 . Дополнение: в тернарном выражении я ошибся. Если s == 1 (true), то надо возвращать -1, потому что показатель степени нечетный. Может быть, математики что-то дополнят?
Алгоритм Соловея-Штрассена
Роберт Соловей и Фолькер Штрассен разработали алгоритм вероятностного тестирования простоты числа, который использует символ Якоби. Определяет числа как составные или вероятно простые. Распознает числа Кармайкла как составные.
Итак, для начала необходимо ввести нужные понятия.
Квадратичный вычет. Если число p — простое и 0 < a < p, то число a является квадратичным вычетом по модулю p, если существуют значения x такие, что
x2 = a (mod p).
Для того, чтобы число a было квадратичным вычетом по модулю n, оно должно быть квадратичным вычетом по модулю всех простых делителей n. Например, если n = 7, то квадратичные вычеты равны 1, 2 и 4.
12 = 1 = 1 mod 7,
22 = 4 = 4 mod 7,
32 = 9 = 2 mod 7,
42 = 16 = 2 mod 7,
52 = 25 = 1 mod 7,
62 = 36 = 1 mod 7.
И наоборот, в следующих уравнениях не существует значений x, которые их удовлетворяют.
x2 = 3 mod 7,
x2 = 5 mod 7,
x2 = 6 mod 7.
Итак, числа 3, 5 и 6 являются квадратичными невычетами по модулю 7.
Если число p — нечетное, то существует ровно (p – 1)/2 квадратичных вычетов по модулю p и столько же квадратичных невычетов по модулю p. Если n — произведение двух простых чисел p и q, то существует ровно (p – 1)(q – 1)/4 квадратичных вычетов по модулю n.
Связь между простыми числами и квадратичными вычетами устанавливается с помощью символов Лежандра и Якоби.
Символ Лежандра, который обозначается как L(a, p) — это функция, определенная, если a — любое целое число, а p — простое число, превышающее 2. Символ Лежандра может принимать значения 0, 1 и –1.
L(a, p) = 0, если a делится на p.
L(a, p) = 1, если a — квадратичный вычет по модулю p,
L(a, p) = –1, если a — квадратичный невычет по модулю p.
Сжато, эти факты записываются так:
L(a, p) = a^((p – 1)/2) mod p.
Алгоритм вычисления символа Лежандра.
1. Если a = 1, то L(a, p) = 1.
2. Если число a четное, то L(a, p) = L(a/2, p)*((-1)^((p^2-1)/8)).
3. Если число a — нечетное и a != 1, то L(a, p) = L(p mod a, a)*((–1)^((a–1)*(p–1)/4)).
Символ Якоби, который обозначается как J(a, n) — это обощение символа Лежандра на составные модули. Это функция, определенная для всех целых чисел a и нечетных целых чисел n. Символ Якоби может принимать значения 0, 1 и –1.
Символ Якоби можно задать следующим образом.
1. Символ Якоби определен только для нечетных чисел n.
2. J(0, n) = 0.
3. Если n – простое число, то J(0, n) = 0, если a делится на n.
4. Если n – простое число, то J(0, n) = 1, если a — квадратичный вычет по модулю n.
5. Если n – простое число, то J(0, n) = –1, если a — квадратичный невычет по модулю n.
6. Если n – составное число, то J(a, n) = J(a, p1)*. *J(a, pm), где p1. pm — разложение n на простые множители.
Алгоритм вычисления символа Якоби.
1. J(1, n) = 1.
2. J(a*b, n) = J(a, n)*J(b, n).
3. J(2, n) = 1, если (n^2 – 1)/8 является четным, и –1 в противном случае.
4. J(a, n) = J((a mod m), n).
5. J(a, b1*b2) = J(a, b1)J(a, b2).
6. Если gcd(a, b) = 1 и, кроме того, числа a и b являются нечетными, то
6.1. J(a, b) = J(b, a), если (a – 1)*(b – 1)/4 является четным числом.
6.2. J(a, b) = –J(b, a), если (a – 1)*(b – 1)/4 является нечетным числом.
Если n — простое число, то символ Якоби эквивалентен символу Лежандра.
Символ Якоби нельзя использовать для проверки, является ли число a квадратичным вычетом по модулю n (кроме случая, когда число n — простое). Если J(a, n) = 1 и n — составное число, то число a не всегда является квадратичным вычетом:
J(7, 143) = J(7, 11) * J(7, 13) = (–1)*(–1) = 1,
хотя не существует целых чисел x таких, что x2 7 (mod 143).
Алгоритм Соловея–Штрассена
1. Выберите случайное число a, меньшее p.
2. Если gcd(a, p) != 1, то число p – составное и тест можно не продолжать.
3. Вычислите j = a^((p–1)/2) mod p.
4. Вычислите символ Якоби J(a, p).
5. Если j != J(a, p), то число p точно не является простым.
6. Если j = J(a, p), то вероятность того, що число p не является простым, не превышает 50%.
Число a, которое не указывает явно, что число p не простое, называется свидетелем. Если число p — составное, то вероятность того, що случайное число является свидетелем, составляет не менее 50%. Вероятность того, что составное число пройдет t испытаний, равняется 1/(2^t).
- простое число
- тест простоты
- составное число
- соловей
- штрассен
- символ якоби
- символ лежандра
Символ Якоби
» width=»» height=»» />
- Мультипликативность: ( a b P ) = ( a P ) ( b P ) \right) = \left(\frac\right) \left(\frac\right)>
- В частности, ( a 2 b P ) = ( b P ) \right) =\left(\frac\right)>
- Периодичность: если a ≡ b ( mod P ) <\displaystyle a \equiv b \pmod> , то ( a P ) = ( b P ) <\displaystyle \left(\frac\right) = \left(\frac\right) >
- ( 1 P ) = 1 \right) = 1>
- ( − 1 P ) = ( − 1 ) P − 1 2 \right) = (-1)^>>
- ( 2 P ) = ( − 1 ) P 2 − 1 8 <\displaystyle \left(\frac\right) = (-1)^>>
- Если Q — нечётное натуральное число, взаимно простое с P , то ( Q P ) ( P Q ) = ( − 1 ) P − 1 2 ⋅ Q − 1 2 \right) \left(\frac\right) = (-1)^\cdot\frac>> — аналог квадратичного закона взаимности.
- В частности, если P и Q взаимно простые и нечётные, то ( Q P ) = ( − 1 ) P − 1 2 ⋅ Q − 1 2 ( P Q ) \right) = (-1)^\cdot\frac>\left(\frac\right) >
- Символ Якоби ( a P ) <\displaystyle \left(\frac\right)> равен приведённой системы вычетов по модулю P , которая задается как умножение элементов этой группы на a (где a обязательно взаимно просто с P ).
Важные замечания [ ]
О вычислении [ ]
Символ Якоби практически никода не вычисляют по определению. Чаще всего для вычисления используют свойства символа Якоби, главным образом — квадратичный закон взаимности.
Более того, несмотря на то, что символ Якоби является обобщением символа Лежандра и определяется через него, чаще именно символ Лежандра вычисляют с помощью символа Якоби, а не наоборот. См. Пример
О связи с квадратичными сравнениями [ ]
В отличие от символа Лежандра, символ Якоби нельзя напрямую использовать для проверки разрешимости квадратичного сравнения. То есть, если задано сравнение
Особенность, используемая в тестах простоты [ ]
В общем случае неверно, что для символа Якоби выполняется то же условие, что и для символа Лежандра:
| ( a P ) ≡ a P − 1 2 mod P . \right) \equiv a^> \mod.> |
(2) |
| ( 7 15 ) = ( 7 5 ) ⋅ ( 7 3 ) = ( 2 5 ) ⋅ ( 1 5 ) = ( − 1 ) 25 − 1 8 ⋅ 1 = − 1 \right)= \left(\frac\right)\cdot \left(\frac\right)= \left(\frac\right)\cdot \left(\frac\right)=(-1)^>\cdot1=-1> |
При этом 7 15 − 1 2 ≡ 7 7 ≡ 13. mod 15 > \equiv 7^7\equiv13. \mod>
Числа a, взаимно простые с P, для которых не выполнено условие (2), называются Эйлеровыми свидетелями непростоты числа P (поскольку для простого P условие (2) выполнено). Если P — составное число, то такое число a, для которого условие (2) выполнено, называют лжецом для теста Эйлера. Доказано, что для любого составного P есть не более P/2 лжецов, различных по модулю P.
Данное свойство используется в вероятностном тесте Соловея-Штрассена на простоту. В этом алгоритме выбираются случайные числа a и для них проверяется условие (2). Если находится свидетель непростоты, то доказано, что число P – составное. В противном случае говорят, что P — простое с некоторой вероятностью.
Применение [ ]
Главным образом, символ Якоби используется для быстрого вычисления символа Лежандра. Символ Лежандра, в свою очередь, необходим для проверки разрешимости квадратичного сравнения по модулю простого числа. Но считать его по определению (то есть вычислять a p − 1 2 mod p >\mod
> ) — достаточно долгая по времени процедура. С помощью алгоритма O ( ( log p ) 3 ) )^3)> битовых операций (если не использовать быстрое умножение и деление). А вычисление символа Якоби требует только O ( ( log p ) 2 ) )^2)> битовых операций.
Символ Якоби используется в некоторых тестах на простоту, например, в (N+1) – методах и, как уже было сказано, в Алгоритм [ ]
Основная идея [ ]
Ключевое используемое при вычислении свойство символа Якоби — квадратичный закон взаимности. Благодаря нему алгоритм похож на алгоритм Евклида нахождения наибольшего общего делителя двух чисел, в котором тоже аргументы на каждом шаге меняются местами. Аналогично алгоритму Евклида, при перестановке аргументов больший заменяется на остаток от деления на меньший. Это возможно благодаря периодичности символа Якоби. Однако, поскольку символ Якоби определён только при условии нечётности второго аргумента, то до перестановки выделяется чётная часть первого аргумента.
Формальное описание [ ]
Входные данные: a — целое число, b — натуральное, нечётное, больше единицы..
Выходные данные: ( a b ) \right )> — символ Якоби
1 (проверка взаимной простоты). Если НОД (a, b) ≠1, выход из алгоритма с ответом 0. 2 (инициализация). r:=1 3 (переход к положительным числам). Если a то a:=-a Если b mod 4 = 3 то r:=-r Конец если 4 (избавление от чётности). t:=0 Цикл ПОКА a – чётное t:=t+1 a:=a/2 Конец цикла Если t – нечётное, то Если b mod 8 = 3 или 5, то r:=-r. конец если 5 (квадратичный закон взаимности). Если a mod 4 = b mod 4 = 3, то r:=-r. c:=a; a:=b mod c; b:=c. 6 (выход из алгоритма?). Если a≠0, то идти на шаг 4, иначе выйти из алгоритма с ответом r.
Комментарии к алгоритму [ ]
В алгоритме везде берётся наименьший положительный вычет (то есть остаток от деления).
На четвёртом шаге используется мультипликативность символа Якоби, а затем вычисляется символ Якоби ( 2 b ) = ( − 1 ) ( b 2 − 1 ) / 8 \right) =(-1)^> . Чтобы избежать лишнего возведения в степень, проверяется только остаток от деления b на 8.
На пятом шаге тоже вместо возведения в степень используется проверка остатков от деления.
Сложность алгоритма равна O ( log a ⋅ log b ) )> битовых операций.
Пример вычисления [ ]
Вычисление символа Лежандра с помощью символа Якоби:
| ( 219 383 ) = − ( 383 219 ) = − ( 164 219 ) = − ( 41 219 ) = − ( 219 41 ) = − ( 14 41 ) = \right) = -\left(\frac\right) = -\left(\frac\right) =-\left(\frac\right) = — \left(\frac\right) = — \left(\frac\right) = > |
| = − ( 2 41 ) ( 7 41 ) = − ( 7 41 ) = − ( 41 7 ) = − ( − 1 7 ) = 1 \right) \left(\frac\right) =- \left(\frac\right) = — \left(\frac\right) = — \left(\frac\right) = 1> |
См. также [ ]
- Символ Лежандра
- Символ Кронекера — Якоби
Список литературы [ ]
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦМНО, 2003. — С. 328. ISBN 5-94057-103-4
- Виноградов И. М. Основы теории чисел. — Москва: ГИТТЛ, 1952.
- Bach E., Shallit J. Algorithmic Number Theory.Vol. I.. — Massachusetts: MIT Press, 1996. ISBN 0-262-02405-5
1.3. Вычисление символа якоби
Символ Якоби -функция, определяемая длявсех целыхa, взаимнопростых, с заданным нечетным целым числомP > 1. Так, еслиP = p1 p2 . pr— разложение числа Pна простые сомножители не обязательно различные, то
,
где
—символы Лежандра[Виноградов,1953], т.е. арифметические функции чиселaирi , определенные для простых нечетныхрiи целыха, не делящихся наP, причем
= 1, если сравнениеx 2 º a(mod pi) разрешимо, а в противном случае
= -1. Часто символ Лежандра, а следовательно, и символ Якоби, который является его обобщением, доопределяют для чиселa, делящихся наpi(для символа Якоби соответственно наP), полагая, что в этом случае
= 0. Символ Якоби обладает свойствами, аналогичными свойствам символа Лежандра, а именно:
- если a ºb (modP), то
=
;
= 1;
;
=
.
;
, где P, Q— положительные нечетные взаимно простые числа (квадратичный закон взаимности, который впервые доказан для символа Лежандра Гауссом в 1876 г.);
;
.
Перечисленные свойства позволяют легко вычислять символ Якоби, не прибегая к решению сравнений. Заметим, что при фиксированном P символ Якоби является действительным характером мультипликативной группы классов вычетов по модулю P. Процедура syjac, построенная по алгоритму, учитывающему приведенные свойства, вычисляет значение символа Якоби
по квадратичному закону взаимности. При этом полагается следующее (табл. 1.4): Таблица 1.4
| Условие |
Значение символа Якоби . |
| P — четное |
Не определено |
| P — нечетное |
2 |
| P — простое и a является квадратичным невычетом числа m |
— 1 |
| Если a и P имеют нетривиальный общий множитель |
0 |
| Остальные случаи |
1 |
Формальные параметры процедуры. Входные:a, p(тип integer).Выходной:r(типinteger) — значение символа Якоби. procedure syjac (a, p : integer; var r : integer); var k : integer; z, q : boolean; label : start, cycle; Function parity (x:integer): boolean; < *** значение функции parity true, если х - четное, и false - в противном случае *** >begin if (x div 2 * 2) = x then parity := true else parity := false; еnd; <***parity***>begin start: if not parity (p) then begin r := 2: exit; end; z := true; cycle: repeat a:=a — a div p * p; q := false; if a > 1 then begin while not parity (a) do begin q:= not q; a:=a div 2; end; if q and parity ((sqr(p)-1) div 8) then Z := not Z; if a № 1 then begin if parity((p-1)*(a-1) div 4) then z:= not z; k:=p; p:=a; a:=k; end; until a ALGOL на языкPASCALи проверен на машине IBM PC/AT-286 для тех же значений входных параметров, что и в работе Агеева (1976). В результате тестирования было получено: 
= 1 (a = 5 — квадратичный вычет); 
= -1 (a = 3 — квадратичный невычет); 
= 2 (p = 12 — четное), что полностью соответствует результатам тестирования программы на языкеALGOL, приведенным в работе Агеева и др. (1976).