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.
Примеры
Пример 1
Доказательство, которое 1159523 является главным, может уменьшаться до доказательства, которое 10343 является главным:
certificate := numlib::proveprime(1159523)
Пример 2
Как правило, простота чисел входа уменьшается до простоты чисел меньшего целого числа, простота чисел того целого числа уменьшается до простоты чисел еще меньшего целого числа и так далее.
numlib::proveprime(179424673)
Используйте numlib::checkPrimalityCertificate, чтобы проверять результат:
numlib::checkPrimalityCertificate(%)
Параметры
|
Положительное целое число. |
Возвращаемые значения
TRUE, FALSE, FAIL, или список или последовательность списков.
Ссылки
numlib::proveprime реализует алгоритм Аткина Голдвассера Килиана Морайна для доказательства простоты чисел. Для получения информации о простоте чисел, доказывающей и этом конкретном алгоритме, см.:
Atkin, A. O. и Ф. Морен. “Эллиптические кривые и доказательство простоты чисел”. Математика Вычисления. Издание 61, Номер 203, 1993.
Goldwasser, S. и Дж. Килиан. “Почти все начала могут быстро сертифицироваться”. Продолжения 18-го ежегодного симпозиума ACM по теории вычисления. Беркли, CA, США, 1986, стр 316–329.