Найдите число, взаимно простое с модулем

Я провел некоторое исследование системы шифрования RSA, довольно просто закодировать ее с использованием небольших простых чисел, поскольку возможностей не так уж много, а производительность не является реальной проблемой.

Вот как работает RSA:

• Во-первых, вы генерируете значение n, произведение двух простых чисел, выбранных случайным образом:

  n = p * q
  

  • Затем вам понадобится ваш открытый ключ, который называется e. Это может быть любое число, взаимно простое с φ(n):

    mcd(φ(n), e) = 1

  • Согласно функции Эйлера, φ(n) = (p-1)(q-1)

  • Вам по-прежнему нужен закрытый ключ, известный как d, который является инверсией e on modulo **φ(n).

  • So d * e = 1 (mod φ(n))

  • n и e — ваши общедоступные значения, а d — ваш закрытый ключ. Никто не должен знать p или q, так как с этими значениями можно было бы получить φ(n) и использовать его для вычисления d.
• Чтобы зашифровать сообщение, мы используем M = m^e (mod n), где m — исходное сообщение, а M — зашифрованное. Таким образом, каждый может отправить вам зашифрованное сообщение, которое вы сможете прочитать, используя ваши общедоступные значения.
• Чтобы расшифровать сообщение, вы используете d, так как это значение, обратное e, поэтому M^d = (m^e)^d = m (mod n). Сообщение можно расшифровать, но только с помощью d.

Зная это, чтобы зашифровать сообщение, нам просто нужно получить два случайных простых числа, вычислить n, e, d, и создать наши методы шифрования и дешифрования.

Теоретически это кажется довольно простым, теперь давайте превратим это в java-код:

Сначала я выбираю два случайных простых числа, чем больше число, тем сильнее шифрование. Так что я выберу p = 1644623 и q = 1644751. Согласно этой странице, это простые числа.

BigInteger p = new BigInteger("1644623");
BigInteger q = new BigInteger("1644751");

Затем в моем методе инициализации я инициализирую n, e и d:

BigInteger p = new BigInteger("1644623");
BigInteger q = new BigInteger("1644751");

BigInteger n;
BigInteger e;
BigInteger d;

void init() {
    n = p.multiply(q);

    BigInteger pn = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

    e = n.subtract(pn);
    while (!mcd(pn, e).equals(BigInteger.ONE)) {
        e = e.add(BigInteger.ONE);
        System.out.println(e);
    }

    d = e.modPow(new BigInteger("-1"), pn);
}

Я использовал BigInteger вместо long, так как используемые значения очень велики.

Теоретически все работает. Практически pn = 2704992034500, так что проверить, если mcd(pn, e) = 1, и если не добавить 1 к e, и попробовать еще раз, это не вариант. Эта программа работает уже 30 минут, в среднем 150 000 номеров в секунду. e = 548151505 и до сих пор не найден mcd(pn, e) = 1.

Есть ли способ найти e за разумное время?