Символ Якоби
возвращает значение символа Якоби для целочисленного J
= jacobiSymbol(a
,n
)a
и положительный нечетный целочисленный n
.
Найдите символ Якоби для и .
a = 1:9; n = 3; J = jacobiSymbol(a,n)
J = 1×9
1 -1 0 1 -1 0 1 -1 0
Символ Якоби является периодическим относительно своего первого аргумента, где если .
Найдите символ Якоби для и .
J = jacobiSymbol(28,9)
J = 1
Символ Якоби является абсолютно мультипликативной функцией, где символ Якоби удовлетворяет отношению для . Покажите, что символ Якоби следует за этим отношением для .
Ja = jacobiSymbol(2,9)*jacobiSymbol(2,9)*jacobiSymbol(7,9)
Ja = 1
Символ Якоби также удовлетворяет отношению для . Покажите, что символ Якоби следует за этим отношением для .
Jb = jacobiSymbol(28,3)*jacobiSymbol(28,3)
Jb = 1
Можно использовать символ Якоби для теста простоты чисел Solovay-Штрассена. Если нечетное целое число является главным, затем конгруэтность
должен содержать для всех целых чисел . Если существует целое число \in таким образом, что отношению конгруэтности не удовлетворяют, затем не является главным.
Проверяйте если является главным или нет. Выбрать и выполните тест простоты чисел. Сравните эти два значения в отношении конгруэтности.
Сначала вычислите левую сторону отношения конгруэтности с помощью символа Якоби.
n = 561; a = 14; J = jacobiSymbol(a,n)
J = 1
Вычислите правую сторону отношения конгруэтности.
m = powermod(a,(n-1)/2,n)
m = 67
Целое число не является главным, поскольку это не удовлетворяет отношению конгруэтности для .
checkPrime = mod(J,n) == m
checkPrime = logical
0
Затем проверяйте если является главным или нет. Выбрать и выполните тест простоты чисел.
n = 557; a = 19; J = jacobiSymbol(a,n); m = powermod(a,(n-1)/2,n);
Целое число является, вероятно, главным, поскольку это удовлетворяет отношению конгруэтности для .
checkPrime = mod(J,n) == m
checkPrime = logical
1
Выполните тест простоты чисел для всех \in подтвердить что целое число является действительно главным.
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
должны быть целые числа. a
и n
должен быть одного размера, или иначе один из них должен быть скаляром.
Типы данных: single
| double
| sym
n
входной параметрВведите в виде номера, вектора, матрицы, массива, символьного числа или символьного массива. Элементы n
должны быть положительные нечетные целые числа. a
и n
должен быть одного размера, или иначе один из них должен быть скаляром.
Типы данных: single
| double
| sym
J
— Выходное значение
| 0
| 1
Выходное значение, возвращенное как –1
, 0, или
1
.
Типы данных: single
| double
| sym
Символ Якоби задан как продукт символов Лежандра
для целочисленного a и положительного нечетного целочисленного n с главной факторизацией
Символ Лежандра поскольку целочисленный a и нечетный главный p заданы как
Когда n является нечетным началом, символ Якоби равен символу Лежандра.
[1] Dietzfelbinger, M. Тестирование простоты чисел в полиномиальное время: от рандомизированных алгоритмов до "PRIMES находится в P". Спрингер, 2004.
У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.