1.3. Вычисление символа якоби

Символ Якоби -функция, определяемая длявсех це­­лыхa, взаимнопростых, с заданным не­четным це­лым чис­­ломP > 1. Так, еслиP = p₁ p₂ ...p_r- раз­ло­же­ние чис­ла Pна простые сомножите­ли не обязательно раз­­лич­ные, то

,

где-символы Лежандра[Виноградов,1953], т.е. ариф­­метические функции чиселaир_i , опре­де­ленные для прос­­тых нечетныхр_iи целыха, не де­лящихся наP, при­­чем= 1, если срав­не­ниеx²º a(mod p_i) раз­ре­ши­­мо, а в про­­тив­ном случае= -1. Часто символ Ле­­­жанд­ра, а сле­д­­о­ва­тельно, и символ Якоби, который яв­ля­ется его обоб­щением, доопределяют для чиселa, де­ля­­щих­­ся наp_i(для символа Якоби соответственно наP), по­­лагая, что в этом случае= 0. Символ Яко­би об­ладает свой­ст­ва­ми, ана­ло­гич­ны­ми свойствам сим­во­ла Ле­жанд­ра, а имен­но:

1. если a ºb (modP), то=;

2. = 1;

3. ;

4. =.;

5. ,

   где P, Q- по­­ло­­­жи­тель­ные нечетные взаимно простые чис­ла (квад­­­ра­тич­ный закон взаимности, который впервые до­ка­зан для сим­во­ла Лежандра Гауссом в 1876 г.);

6. ;

7. .

Перечисленные свойства позволяют легко вы­чис­­­лять символ Якоби, не прибегая к решению срав­­­­не­ний. За­­ме­тим, что при фиксирован­ном 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 <= 1;

if a=0 then

r:= 0

else

if z then

r := 1

else

r:= -1;

end.

Приведенный алгоритм был переведен ав­то­ра­­ми с язы­ка ALGOL на языкPASCALи проверен на ма­­ши­­не IBM PC/AT-286 для тех же значений вход­­ных па­ра­мет­ров, что и в работе Агеева (1976). В ре­зуль­тате тес­ти­ро­ва­ния было получено:

= 1 (a = 5 - квадратичный вычет);

= -1 (a = 3 - квадратичный невычет);

= 2 (p = 12 - четное), что полностью со­от­вет­с­т­­ву­­ет результатам тести­ро­­ва­ния программы на языкеALGOL, приведен­ным в работе Агеева и др. (1976).