jacobiSymbol

Синтаксис

Описание

пример

J = jacobiSymbol(a,n) возвращает значение символа Якоби для целого числа a и положительное нечетное целое число n.

Примеры

свернуть все

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

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

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

Символ Якоби является периодическим относительно его первого аргумента, где (an)=(bn) если ab(modn).

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

J = jacobiSymbol(28,9)
J = 1

Символ Якоби является полностью мультипликативной функцией, где символ Якоби удовлетворяет отношению (an)=(a1n)×(a2n)×(arn) для a=a1×a2×ar. Покажите, что символ Якоби следует этому отношению для a=28=2×2×7.

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

Символ Якоби также удовлетворяет отношению (an)=(an1)×(an2)×(anr) для n=n1×n2×nr. Покажите, что символ Якоби следует этому отношению для n=9=3×3.

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

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

(an)a(n-1)/2(modn)

необходимо удерживать для всех целых чисел a. Если существует целое число a в {1,2,,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,,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

Входные параметры

свернуть все

Вход, заданный как число, вектор, матрица, массив, символьное число или символьный массив. Элементы a должно быть целыми числами. a и n должен быть того же размера, или же один из них должен быть скаляром.

Типы данных: single | double | sym

Вход, заданный как число, вектор, матрица, массив, символьное число или символьный массив. Элементы n должно быть положительными нечетными целыми числами. a и n должен быть того же размера, или же один из них должен быть скаляром.

Типы данных: single | double | sym

Выходные аргументы

свернуть все

Выходное значение, возвращаемое как –1, 0, или 1.

Типы данных: single | double | sym

Подробнее о

свернуть все

Символ Якоби

Символ якоби (an) определяется как продукт символов Legendre

(an)=(ap1)k1(ap2)k2(apr)kr

для целого a и положительного нечетного целого числа с n простого факторизации

n=p1k1p2k2prkr.

Символ Легендры (ap) для целого a и нечетного простого p определяется как

(ap)={0если a0 (mod p)1если a является  квадратичным остатком по модулю p или x2a (mod p) имеет  ненулевое решение для x1если a является  квадратичным нерезидущим модулем по модулю p или x2a (mod p)  не имеет решений для x.

Когда n является нечетным простым числом, символ Якоби равен символу Лежандра.

Ссылки

[1] Dietzfelbinger, M. Primality Testing in Polynomial Time: From Randomized Algorithms to «PRIMES Is in P». Спрингер, 2004.

См. также

| |

Введенный в R2020a