Комментарии 24
В первой формуле у вас верхний предел суммирования неправильно записан.
Теорему Вильсона чем-то напоминает
А чему равно x в Вашем методе?
Там еще квантор всеобщности по x не дописан, да
ничему, это переменная, нас интересуют только коэфициенты при ней
А, понял. По ходу, если число p - простое, то оно должно делить все биномиальные коэффициенты, кроме, естественно, единичных. А вот верно или нет обратное - не знаю:)
А вот верно или нет обратное — не знаю:)
Верно. Alexandroppolus чуть ниже привел доказательство. Но наверняка
Хотя код/метод и справляется с достаточно большим количеством чисел, я не стану утверждать, что он работает на 100% случаев.
Да вроде это тривиально доказывается. А именно, что если m не простое, то найдется такое 0 < n < m, что C(m, n) не делится на m. Пусть в m есть простой делитель p в степени k. Тогда берем n = p, и получаем C(m, n) = m! / (p! * (m - p)!) = m * (m-1) * (m-2) * ... *(m-p+1) / p!. В этой дроби числитель равен (p^k * a), знаменатель равен (p * b), где a и b не делятся на p, итог будет (p^(k-1) * с), т.е. не делится на m
Ну а для простого m всё очевидно
Похоже на очень наивную реализацию метода AKS. Основано на той же теореме, только вместо проверки в поле по модулю X^r-1 тут брутфорсом проверяются все коэффициенты (ну ладно, половина — все равно плохо).
В итоге, получилось вообще бесполезное упражнение. Этот метод проверяет число N за O(N) операций с BigInt. Очень сложных операций. Наивная же проверка на делимость с одной единственной оптимизацией (проверять делители до корня) работает на порядки быстрее — за O(sqrt(N)).
Более того, поскольку тут считаются сами коэффициенты бинома, то в процессе вычисления получаются числа длины O(N). Т.е. на самом деле тут сложность даже не линейная от числа, а квадратичная! Более медленный и бесполезный метод проверки числа на простоту придумать довольно сложно.
Возможно, в квантовых компьютерах многие наивные методы обретут актуальность.
Ну вот проверка на простоту — один из немногих методов, которые уже для кавантовых компьютеров разработаны. Так что я бы не надеялся на квантовые вычисления в качестве призрачной надежды на актуальность у описанного в статье метода.
что касается последних двух обзацев, они не уместны, поскольку ничего о практической применимости не говорилось, и не заявлялось что он "быстрый", это просто еще один метод ни на что не претендующий. мне метод нравится сугубо эстетически.
и не заявлялось что он "быстрый"
Простите, но вы прямо в лиде заявляете, что он «эффективный и надёжный», а он ни то, ни другое.
поскольку ничего о практической применимости не говорилось
Ну тогда у метода должна быть хоть какая-то фишка. Иначе, ну зачем он? Красивое теоретическое обоснование? Возможность расширить метод и гораздо лучше его реализовать? Простота реализации? Ничего этого в статье нет. Можно было бы привести доказательство критерия простоты. Можно было бы порассуждать о более эффективной релизации в поле по модулю небольшого полинома.
Такие алгоритмы являются предметом любопытства, а не практического применения. А что такое любопытство? Оно вообще нужно?
Вы движетесь в правильном направлении. Попробуйте делать все это на питоне. Кстати для питона есть хорошая либа gmpy2.
Завидую тому, что у вас есть время на такие занятия.
На мой вкус, вместо
(x - 1)^p - (x^p - 1)
лучше будет записать
(x + 1)^p - x^p - 1
Убирается головная боль, связанная с тем, чтоб следить за минусом при a_k, который, судя по тексту статьи, нам всë равно не нужен, а все последующие формулы становятся проще для восприятия
Применение формулы бинома для определения простых чисел