numlib
::proveprime
Простота чисел, доказывающая использующий эллиптические кривые
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
numlib::proveprime(n
)
numlib::proveprime(n)
тесты, ли n
начало. В отличие от isprime
, numlib::proveprime
всегда дает правильный ответ.
numlib::proveprime
возвращает следующие значения:
TRUE
когда может оказаться, что номер является началом.
FALSE
когда может оказаться, что номер не является началом.
FAIL
когда не может оказаться, что номер является началом и не может доказать в противном случае. В таких случаях вход, скорее всего, является началом.
Сертификат простоты чисел, который является списком или последовательностью списков, содержащих доказательство для простоты чисел номера. Как правило, numlib::proveprime
возвращает сертификаты простоты чисел для очень больших количеств.
Сертификат простоты чисел является последовательностью списков формы [N, D, l m, a, b, x, y, l s], где
N является псевдоначалом
D является целым числом (основной дискриминант)
l m является списком простых множителей
a, b, x, y является целыми числами N по модулю
l s является другим списком простых множителей (подмножество факторов в l m)
numlib::checkPrimalityCertificate
сертификаты простоты чисел проверок производятся numlib::proveprime
.
Доказательство, которое 1159523 является главным, может уменьшаться до доказательства, которое 10343 является главным:
certificate := numlib::proveprime(1159523)
Как правило, простота чисел входа уменьшается до простоты чисел меньшего целого числа, простота чисел того целого числа уменьшается до простоты чисел еще меньшего целого числа и так далее.
numlib::proveprime(179424673)
Используйте numlib::checkPrimalityCertificate
проверять результат:
numlib::checkPrimalityCertificate(%)
|
Положительное целое число. |
TRUE
ложь
, FAIL
, или список или последовательность списков.
numlib::proveprime
реализует алгоритм Аткина Голдвассера Килиана Морайна для доказательства простоты чисел. Для получения информации о простоте чисел, доказывающей и этом конкретном алгоритме, см.:
Atkin, A. O. и Ф. Морен. “Эллиптические кривые и доказательство простоты чисел”. Математика Расчета. Издание 61, Номер 203, 1993.
Goldwasser, S. и Дж. Килиан. “Почти все начала могут быстро сертифицироваться”. Продолжения 18-го ежегодного симпозиума ACM по теории вычисления. Беркли, CA, США, 1986, стр 316–329.