Первый метод ускорения заключается в том, что время вычисления НОД занимает много времени, поэтому используем китайскую теорему об остатках и попробуем ускорить начальный алгоритм. Китайская теорема об остатках: любое не отрицательное число которое не превышает каждого из множителей  модуля можно однозначно восстановить если известны его остатки по этим модулям.

Доказательство Пусть числа и определены согласно m1m2 × × × mk = Msms, причем  º 1(mod ms),  s = 1, 2, . . . , k и целые числа  попарно взаимнопростые, то есть ,

Пусть b1, b2, . . . , bk тоже целые числа такие что ,

Тогда система сравнений:

x º b1(mod m1),

x º b2(mod m2),

. . . . . . . . . . .

x º bk(mod mk)

Имеет в интервале где M = m1×m2 × × × mk одно общее решение

(7)

Если числа  и определены из условий m1m2 × × × mk = Msms, причем  º 1(mod ms),  s = 1, 2, . . . , k и целые числа  попарно взаимнопростые, то есть , то совокупность значений x которые удовлетворяют систему (1) определяется сравнением  где  +, х – в виде уравнения (7) удовлетворяет систему (6). Согласно другой теореме – если b1, b2, . . . , bk независимо друг от друга пробегают полную систему остатков по модулям . Число x0 может принять значение одного из остатков по модулю M = m1×m2 × × × mk., т.е. .

Докажем что для x0 из интервала для разных наборов целых чисел b1, b2, . . . , bk таких что , , общее решение (7) является единственным. Доказательство будет вестись от обратного допустим что существует еще один набор чисел  таких, что ,  Пускай для конкретности эти наборы отличаются числами что стоят на s-позиции т.е. . Но тогда мы приходим к тому что справедливы сравнения  и  так как по условию теоремы при всех  выходит . Поэтому из равенства чисел вытекает справедливость сравнения . При условии  это значит  а это противоречит начальному условию. Следовательно решение (6) единственно.

Второй метод ускорения строится на алгоритме нахождения периода последовательности методом Брента. Пусть F – конечное множество, x F и f: F → F отображение, которому соответствует последовательность xn+1 = f(xn), начинающая с x0.Цели алгоритма Брента – сосчитать длину периода последовательности (xn)n≥0, использую при этом как можно меньше памяти . Сложность алгоритма имеет порядок квадратичного корня из F.

Отметим, что для h = 2i – 1 интервал соответствующих значений k равен [h+1, 2h +1]. Для того, чтобы теперь xh = xk, необходимо и достаточно, чтобы h ≥ μ (индекс вхождения в период) и k – h было кратно λ (длина периода) – условие, которое выполняется при достаточно большом h (так как интервал для k удваивается на каждом этапе). Пусть h – какой-либо индекс, для каждого существует k  [h+1,2h+1] c xh = xk. Если k – первый индекс интервала [h+1,2h+1], для которого xh = xk, то k – h равно длине периода λ. Наконец, если μ – наименьший индекс, такой, что xμ = xμ+λ, то μ – индекс вхождения в период. Это приводит к алгоритму, в котором переменная j  принимает значения h+1, т.е. степени 2. Хотя алгоритм находит только длину периода, дальнейшее применение метода Брента позволяет определить все 4 параметра (h,k,μ,λ), описанные выше: сложность измеряется при помощи параметра k, который равен числу итераций x ← f(x) и обозначается kf,x0.