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

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

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

(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. Тестирование простоты чисел в полиномиальное время: от рандомизированных алгоритмов до "PRIMES находится в P". Спрингер, 2004.

Смотрите также

| |

Введенный в R2020a

Для просмотра документации необходимо авторизоваться на сайте