Найдите символ Якоби для $$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)$$ для теста простоты чисел Solovay-Штрассена. Если нечетное целое число $$n>1$$ является главным, затем конгруэтность

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

Проверяйте если $$n=561$$ является главным или нет. Выбрать $$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$$ является главным или нет. Выбрать $$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$$ \in $$\{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