Модульное возведение в степень в Java с использованием totient Эйлера и китайской теоремы об остатках

Question

Редактировать - уточнил

Я пытаюсь реализовать модульное возведение в степень в Java, используя лагранж и теорему об остатках в Китае.

Например, если N равно 55, с учетом простых факторов 5 и 11, фи равно 40, так что я знаю, что есть 40 чисел, взаимно простых с N ниже 55. Мой инструктор говорит, что способ сделать это - "использовать теорему Лагранжа"., несколько умножений по модулю 5 и 11 и CRT, чтобы объединить оба результата "

Моя проблема в том, как мне рассчитать эти числа? Мне нужно, чтобы они поместили их в китайскую теорему об остатках, чтобы закончить вычисления, но я не могу придумать умного способа перебрать N, используя в результате phi(n). N будет чрезвычайно большим числом, по крайней мере, 1024 бит. Я мог бы быть здесь на неправильном пути, мне вообще нужны все эти простые числа?

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

Я не понимаю код в Сколько чисел ниже N взаимно простых с N? так что это не сильно помогает мне, и математические статьи, на которые я смотрю, мне очень трудно следить, обозначения суммы и типа продукта меня немного сбивают с толку. Кроме того, в некоторых ответах используются квадратные корни и журналы, которые на самом деле не подходят для BigInteger (поправьте меня, если я ошибаюсь)

Кто-нибудь может дать мне ответ на простом английском языке?

Можно показывать мне код, это скорее учебное упражнение, потому что ответ, который я собираюсь представить, использует Монтгомери. (Да, я знаю, странно, что я мог бы вычислить Монтгомери из математической формулы, но этот Лагранж плюс ЭЛТ меня совершенно сбил с толку)

Я дошел до этого, работая над примером, который нашел. Основными факторами являются семь и пять, поэтому число 35 равно 24 (у меня есть рабочая функция Эйлера).

Answer 1

Смотрите этот ответ для отработанного примера. Он показывает, как именно выполнить модульное возведение в степень по модулю композита, выполнив операцию по модулю простых факторов и объединив результаты.

Answer 2

Чтобы найти все числа, взаимно простые с N, просто итерируйте алгоритм Евклида GCD() над [1,N]. Если GCD(a,N) == 1, то a, N взаимно просты