Доказательство (или опровержение) простоты заданного числа
Доказательство (или опровержение) простоты заданного числа
Иногда нужно не только знать, простое или составное данное число, но и иметь доказательство (или опровержение) его простоты. Конечно, система Mathematica не пишет развернутый текст такого доказательства (или опровержения), но она может выдать систему чисел, доказывающую (или опровергающую) простоту заданного числа. Такая система чисел называется свидетельством, или сертификатом. Что может быть сертификатом? В принципе это зависит от "внутренней кухни" той системы, которая генерирует сертификат. В случае составного числа можно указать, например, его нетривиальный делитель. При составном числе n можно также указать такое а, для которого не выполняется сравнение an-1 =1(modn). Система Mathematica для установления простоты числа использует теорию эллиптических кривых. Основанный на ней алгоритм, придуманный Аткином (Atkin), Голдвассером (Goldwasser) и Кильяном (Kilian), является в настоящее время наилучшим, если не принимать во внимание квантовых компьютеров, пока еще не реализованных. Этот алгоритм подробно описан в статье Atkin А. О. L. and Morain F. Elliptic Curves and Primality Proving (Mathematics of Computation, 1993, pp. 29-68). Однако он довольно сложен, и в настоящее время даже не все студенты-математики изучают его (как и теорию эллиптических кривых). Поэтому пользуются им чаще всего профессионалы. Тем не менее в отдельных случаях такой сертификат вполне понятен и для школьника. Вот пример. Вызвав функцию PrimeQCertificate[3837523], получим сертификат {2, 3837522, 3837523}, который показывает, что 238"522(mod3837523) не равно 1. (Сертификаты, опровергающие простоту, легко распознать: они всегда состоят из трех чисел.)
