Настройки поиска (Страница 1 из 4)

Я решил немного изучить быстрые алгоритмы факторизации и проверки на простоту. Начнем с проверки на простоту:
В Кормене вычитал про тест Миллера-Рабина, увидел, что реализация довольно простая, написал, даже работает..:) У меня в силу скудных познаний математики возникли вопросы, на которые не Кормен, ни гугл ответов (понятных для меня) не дали. Отличие теста Миллера-Рабина от простой проверки малой теоремы Ферма заключается в том, что по ходу возведения в степень мы ещё и проверяем некий нетривиальны корень из 1. Собственно вопрос: что такое этот корень из 1 и как он влияет на алгоритм, простоту числа и т.д?
С факторизацией дела немного хуже обстоят. В том же Кормене  прочитал про метод Полларда, который ро. Мало того, что метод для меня совсем не очевиден, так ещё работает он достаточно сомнительно. В моем алгоритме я сначала проверял число на простоту, потом проверял все простые числа меньшие чем 10^7, которые в самом начале решетом нашел, а потом, зная, что N=pq, писал Полларда-ро. Реализация из Кормена и та, котору я списал с е-макса, на злостных тестах вроде (2^31-1)*(10^9+7) не работает. Гуглил другие методы, из всех понятным мне кажется лишь метод Ферма, который, кстати, прилично работает, но на вышеупомянутых тестах и он валится. Метод Лемана в реализации простой, но там мне кажется огромная константа в силу постоянных вычислений корней разных степеней+переполнение на тестах где N^4/3>2^63-1, то есть работает где-то для N<=10^13 степени, что как-бы не серьезно. Хотя я могу ошибаться, ибо опираюсь лишь на статью из Википедии.
Знаю, есть ещё куча разных методов, вроде р+1, р-1 и так далее, но они тёмные какие-то для меня.
Какими методами пользуетесь вы, в чём их суть? Если не сложно, то объясните в двух словах детали реализации и почему они правильные? Возможно я просто плохо понимаю тот же Полларда-ро, а на самом деле он хорошо работает, но моя кривая реализация подвела.
Заранее спасибо!

Собственно, есть DAG, нужно для каждой вершины узнать сколько вершин достижимо из неё. Нужно самое быстрое решение. Слышал, можно как-то сделать за (N^2)/32, но слабо представляю как.

Как решать эту задачу двоичным подъёмом в режиме онлайн? Нам ведь нужно определять является ли одна вершина предком другой. Я знаю, что если выполнить все запросы добавления, а потом найти все LCA, то тоже будет правильно, но мне интересно как решать эту проблему "влоб".