Два бояна и кое-что о числах

Мужики уже умеют искать поток за O(n m). Некоторые говорят, что это боян, но я увидел только пару недель назад. Оригинальная работа вышла в августе 2012. До этого было что-то близкое по сложности, со страшными логарифмами.

Мужики умеют искать раскраску в 4 цвета для планарных графов за квадрат. Честно говоря, ВНЕЗАПНО. С какого-то 199? года. Там (с хроматическими числами) чуть ли не половина задач NP-трудные/сложные. Да и как планарность за линию делают - в моей интуиции это не укладывается. Жаль, что времени на это выделить я полноценно не смогу.

Обнаружил замечательный факт по числам Мерсенна. Пока его нигде не видел. Напомню, что тест Люкаса-Лемьера состоит в 

s_0 = 4

s_n = s_{n-1}^2 - 2 mod M_p

Если s_{p - 2} = 0, то все хорошо. 

Я все брежу, чтобы идти с конца. Корни же не всегда извлекаются. 

То есть надо идти с нуля, применяя следующую операцию, \x -> sqrt(x + 2), что дает 2 числа, либо облом.

Так вот, для Мерсенновых получается идеальное бинарное дерево. Начиная с 2 (0 + 2) получаем два числа, затем 4 числа, и так далее. На последнем шаге получаем красоту, пока необъяснимую. Никаких циклов, все числа использованы, из последнего слоя уже корни квадратные не извлекаются. Думал, что извлекаемость корней есть полный беспорядок, а тут идеальная структура. Уже недели две хожу с упоротыми глазами.

А те, которые неМерсенновы, получаем облом на втором шаге. Корень из двух очевидно равен 2^{(p + 1) / 2}. А извлечь корень из 2^{(p + 1) / 2} + 2 быстро не могу. Для неМерсенновых там облом идет. Знаний пока мало, маленький еще. Чтобы решить x^2 = a mod M_p можно просто x = a^{2^{p-2}}. То есть возведениями "в_квадрат" все равно O(p) шагов, что тот же Люкаса-Лемьера ничем не лучше. Фенечка на первом шагу для 2 заключается в том, что 2 порождает хорошую группу размером в p. Поэтому все быстро. Но стоит отойти на шаг в сторону, и размер группы будет несколько великоват, во что и утыкаюсь.

Еще пытаюсь что-то извлечь из x^3 = 1 mod M_p. Так как 2^p - 2 очевидно делится на 3, то у нас есть подгруппа размера 3. Первый корень тривиален. Тут внезапно работает теорема Виетта, та которая про сумму и произведение корней и первый/последний член полинома. Другие два корня тривиально находятся, если найти x^2 = -3 mod M_p. Что эффективнее чем Люкас я пока не вижу как. Утык.

Где бухают теоретики-числовики и прочие алгеброиды? Как в стране, так и в мире... И чтобы дети, моего уровня, смогли приобщиться. Всякие http://math.stackexchange.com/ понятно, но хочется очные.