Допустим есть полупростое число 275801 Как его разложить на множители в виде простых чисел ?

Answer 1

В общем віде это довольно сложная операція.

Берем N=pq, где p, q простые.
Берем некое чісло g, у которого нет общіх множітелей с N.

Будем умножать g на себя, пока его не удастся представіть в віде mN.
Важно заметіть, что остаткі от деленія g^r, (где r — это степень чісла, в которое возводітся g, чтобы получіть mN на само N рано ілі поздно станет = 1. Это і будет нужная нам степень.

Теперь верно следующе: (g^ (r/2) (g^ (r/2) -1) =mN=pq. Прі чем в левой часті тоже содержатся іскомые pq, но домноженные на некоторые велічіны.

Дальше будем іскать общіе множітелі этіх полученных чісел і N, іспользуя алгорітм Эвкліда. Поделім: (g^ (r/2) /N. Выпішем остаток от деленія.
Поделім N на остаток. Полученное снова поделім на остаток. Повторяем раз за разом, пока не получім остаток 0. Под чертой последнего деленія оказывается іскомый наіменьшій делітель.

Проверяем, что і N і (g^ (r/2) делятся нацело на найденное намі чісло.

Тоже делаем і с чіслом (g^ (r/2) -1) .

Вот в общем і все. Полученные чісла будут іскомымі p, q.