Предварительные сведения из теории чисел (полная и приведенная системы вычетов, теорема Вильсона, малая теорема Ферма, функция и теорема Эйлера, китайская теорема об остатках, алгоритм Гарнера, квадратичные вычеты, символя Лежандра и Якоби).