Найдите символ Якоби для $$a\mathrm{=}\mathrm{}1,2,\mathrm{.}$$.., 9 $$\mathrm{и}$$n = 3.

a = 1:9;
n = 3;
J = jacobiSymbol(a,n)

J = 1×9

     1    -1     0     1    -1     0     1    -1     0

Символ Якоби является периодическим по отношению к своему первому аргументу, где $$\left(\frac{}{a}\right)=\frac{}{(}$$bn), $$\mathrm{если}\mathrm{a\equiv b}($$modn).

Найдите символ Якоби для $$a\mathrm{=}\mathrm{}$$28 $$и\mathrm{n}$$= 9.

J = jacobiSymbol(28,9)

J = 1

Символ Якоби - полностью мультипликативная функция, где символ Якоби удовлетворяет соотношению $$\left(\frac{}{\mathrm{an}}\right)=\frac{{}_{\mathrm{(}}}{}a1n\left)\frac{{}_{\mathrm{\times }}}{}\right(a2n\frac{{)}_{}}{\times }.$$.. ($$arn{)}_{\mathrm{}}{}_{\mathrm{для}}a{}_{=}$$a1 × a2 ×... ar. Показать, что символ Якоби следует $$этому\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$соотношению для a = 28 = 2 × 2 × 7.

Ja = jacobiSymbol(2,9)*jacobiSymbol(2,9)*jacobiSymbol(7,9)

Ja = 1

Символ Якоби также удовлетворяет соотношению $$\left(\frac{}{\mathrm{an}}\right)=\frac{}{{(}_{\mathrm{}}}an1\left)\frac{}{{\times }_{\mathrm{}}}\right(an2\frac{)}{{}_{\times }}.$$.. ($$anr{)}_{\mathrm{}}{}_{\mathrm{для}}n{}_{=}$$n1 × n2 ×... nr. Показать, что символ Якоби следует $$этому\mathrm{}\mathrm{}\mathrm{}$$соотношению для n = 9 = 3 × 3.

Jb = jacobiSymbol(28,3)*jacobiSymbol(28,3)

Jb = 1

Для $$\frac{}{}$$теста примитивности Соловея-Штрассена можно использовать символ Якоби (an). Если нечётное целое число $$n\mathrm{>}$$ 1 является простым, то конгруэнтность

должен содержать для всех целых чисел $$$$a. Если существует целое число $$a$$ в $$\{\mathrm{}\mathrm{1,2},...,\mathrm{}$$n-1} так, что соотношение конгруэнтности не удовлетворяется, $$$$то n не является простым.

Проверьте, $$\mathrm{}\mathrm{}\mathrm{}$$является ли n = 561 простым или нет. $$\mathrm{Выберите}\mathrm{a}\mathrm{}$$= 19 и выполните тест примитивности. Сравните два значения в уравнении конгруэнтности.

Сначала вычислите левую сторону соотношения конгруэнтности с помощью символа Якоби.

n = 561;
a = 14;
J = jacobiSymbol(a,n)

J = 1

Вычислите правую сторону уравнения конгруэнтности.

m = powermod(a,(n-1)/2,n)

m = 67

Целое число $$n\mathrm{=}\mathrm{}\mathrm{}$$561 не является простым, поскольку оно не удовлетворяет соотношению конгруэнтности $$\mathrm{для}\mathrm{a}\mathrm{}$$= 19.

checkPrime = mod(J,n) == m

checkPrime = logical
   0

Затем проверьте, $$\mathrm{}\mathrm{}\mathrm{}$$является ли n = 557 простым или нет. $$\mathrm{Выберите}\mathrm{a}\mathrm{}$$= 19 и выполните тест примитивности.

n = 557;
a = 19;
J = jacobiSymbol(a,n);
m = powermod(a,(n-1)/2,n);

Целое число $$n\mathrm{=}\mathrm{}\mathrm{}$$557, вероятно, является простым, поскольку оно удовлетворяет соотношению конгруэнтности $$\mathrm{для}\mathrm{a}\mathrm{}$$= 19.

checkPrime = mod(J,n) == m

checkPrime = logical
   1

Выполните тест примитивности для всех $$a$$ в $$\{\mathrm{}\mathrm{1,2},..\mathrm{.}\mathrm{,}\mathrm{}$$556}, чтобы подтвердить, что $$целое\; число\mathrm{}\mathrm{n}\mathrm{}$$= 557 действительно является простым.

a = 1:n-1;
J = jacobiSymbol(a,n);
m = powermod(a,(n-1)/2,n);
checkPrime = all(mod(J,n) == m)

checkPrime = logical
   1

Проверьте результат с помощью isprime.

isprime(n)

ans = logical
   1