Теория чисел. Факторизация. Проверка на простоту

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