Найдите символ Якоби для $$a=1,2,\dots ,9$$ и $$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}{n}\right)=\left(\frac{b}{n}\right)$$ если $$a\equiv b(modn)$$.

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

J = jacobiSymbol(28,9)

J = 1

Символ Якоби является полностью мультипликативной функцией, где символ Якоби удовлетворяет отношению $$\left(\frac{a}{n}\right)=\left(\frac{a_1}{n}\right)\times \left(\frac{a_2}{n}\right)\times \dots \left(\frac{a_r}{n}\right)$$ для $$a=a_1\times a_2\times \dots a_r$$. Покажите, что символ Якоби следует этому отношению для $$a=28=2\times 2\times 7$$.

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

Ja = 1

Символ Якоби также удовлетворяет отношению $$\left(\frac{a}{n}\right)=\left(\frac{a}{n_1}\right)\times \left(\frac{a}{n_2}\right)\times \dots \left(\frac{a}{n_r}\right)$$ для $$n=n_1\times n_2\times \dots n_r$$. Покажите, что символ Якоби следует этому отношению для $$n=9=3\times 3$$.

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

Jb = 1

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

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

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

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

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

J = 1

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

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

m = 67

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

checkPrime = mod(J,n) == m

checkPrime = logical
   0

Далее проверьте, $$n=557$$ является простым или not. выбрать $$a=19$$ и выполните тест примитива.

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

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

checkPrime = mod(J,n) == m

checkPrime = logical
   1

Выполните тест примитива для всех $$a$$ в $$\{1,2,\dots ,556\}$$ чтобы подтвердить, что целое число $$n=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