В java есть реализованный алгоритм Евклида для BigInteger - метод gcd. Он в данном случае будет намного эффективнее обычного, т.к. там реализован двоичный алгоритм Евклида, работающий быстрее обычного в размерность чисел раз быстрее
да gcd есть. но РАСШИРЕННЫЙ алгоритм Евклида, метода которого я не нашел, дает не только НОД, но и ещё кое-какие числа, которые мне и были нужны для реализации RSA.