Вот тут есть замечательная теорема, говорящая, что (упрощённо) если мы умеем эффективно считать Γ(z) через Γ(2z), то мы умеем эффективно факторизовывать числа. Доказательство теоремы очень простое и красивое. Надо бы запомнить трюк с gcd и факториалами.