сложность наибольшего общего делителя (gcd)

Рассмотрим следующую проблему подсчета (или связанную с ней проблему решения): учитывая два натуральных числа, закодированных в двоичном виде, вычислим их наибольший общий делитель (gcd). В каком классе наименьшей сложности содержится эта проблема? Можете ли вы предоставить ссылку?

В этом вопросе меня интересуют не асимптотические оценки времени выполнения, а классы сложности. Проблема в переменном токе? Можно ли доказать, что он не лежит в AC0? Какие еще классы сложности внутри P имеют здесь значение?

Это главный открытый вопрос в теории сложности: неизвестно, можно ли вычислить GCD в NC, и неизвестно, является ли вычисление GCD P-полным. Лучшие параллельные алгоритмы имеют сублинейное параллельное время выполнения, один из таких алгоритмов принадлежит Соренсону:

Дж. Соренсон. Два быстрых алгоритма GCD . Журнал Алгоритмов, 1994.

Если я не ошибаюсь, даже не известно, можно ли решить, являются ли два целых числа относительно простыми в NC.

$\mathsf{AC}^0$$\mathsf{AC}^0[p]$$p$

В этом документе, опубликованном в 2007 году, говорится, что целочисленный GCD находится в NC.

Изменить: утверждение, вероятно, неверно. Проверьте комментарии.