Факторизация (разложение на простые множители) тремя способами (CASIO fx-9750G Plus)

Эта страница была утеряна месяца два назад в результате аварии на сервере и теперь мною восстановлена повторно.

Вариант 1 - Разложение на множители методом перебора

Самый простой метод с точки зрения реализации, целесообразно использовать для чисел размера примерно до 1020 Алгоритм имеет экспоненциальную сложность с точки зрения времени счёта.

ClrText
“INPUT NUMBER”
?->A:sqrA->B
For 2->C To B
If Frac(A/C)=0
Then A/C->A:C■
C-1->C:sqrA->B
IfEnd
If I>2
Then I+1->I
IfEnd
Next
A■
“END FACTORISATION”

Сокращения: sqr - квадратный корень; / - символ деления,  - перевод строки

Вариант 2 - Р-1 метод Полларда

Этот метод самый быстрый (имеет полиномиальную сложность), но работает только для составных чисел специального вида, так называемых "гладких". По этому методу разложить не удаётся гораздо чаще, чем удаётся. Кроме того, этот метод раскладывает числа на два множителя не зависимо от того из скольки простых чисел состоит составное.
Суть метода заключается в следующем:
1. N - факторизуемое число;
2. B = Int(ln(N)); целая часть натурального логарифма
3. X = 2B!mod N;
4. P = НОД(X-1,N);//наибольний общий делитель
5. Q = N/P;

ClrText
“INPUT NUMBER”?->N
Abs ln N->B:2->A:1->I
Do
I+1->I:A->C
1->J
While J < I
AC-NInt(AC/N)->N
J+1->J
WhileEnd
C->A:A-1->C
N->X:C->Y
Prog “SUB NOD” 
LpWhile(((X=1)Or(X=N))And(I<=B))
N/X->Y
“ITER=”
Locate 6,3,I
Locate 3,4,X
Locate 3,5,Y

Подпрограмма "SUB NOD" вычисления наибольшего общего делителя по алгоритму Евклида

While Y>0
X-YInt(X/Y)->X
Y->Z:X->Y:Z->X
WhileEnd
Return

Вариант 3 - Ро метод Полларда

Это субэкспоненциальный метод, который требует значительных объёмов памяти, но для больших чисел даёт результат гораздо быстрее, чем переборный метод.
Суть метода состоит в следующем:
1. Вычисляем по рекуррентной формуле Xi = (X2i-1+1) mod N, X0 = 2 и запоминаем результаты до тех пор пока очередной результат не совпадёт с каким-либо предидущим.
2. Пусть совпали значения чисел на итерациях номер I и J. Тогда находим наибольший общий делитель из выражения P = НОД(N,(Xi-1-Xj-1)mod N)
3. Q = N/P.
Как и в предидущем методе, число раскладывается только на два множителя. Из-за конструктивных ограничений (длина списка в калькуляторе не более 255 чисел), если алгоритм потребует больше, чем 255 итераций, то калькулятор остановится и сообщит о недостатке памяти. Однако из-за большой продолжительности поиска список может заполнится за время превышающее 8 минут.

ClrText:“RO POLLARD”
“INPUT NUMBER”?C
255->Dim List1
2->List1[1]
For 1->I To 254
List1[I]->X
X2+1->X
X->List 1[I+1]
For I->J To 1 Step -1
If List1[J]=X
Then Break
IfEnd
Next
If J!=1
Then List 1[J-1]->X
List 1[J-1]->Y
X-Y+C->X
X-CInt(X/C)->X
C->Y
Prog “SUB NOD”
C/X->Y
Break
IfEnd
Next
If J>1 And I<254
Then “ITER=”
“REPT=”
“MUL1=”
“MUL2=”
Locate 6,4,I
Locate 6,5,J-1
Locate 6,6,X
Locate 6,7,Y
Else “=LOW MEMORY=”
IfEnd

Это, конечно, не все методы, но самые простые для понимания и запоминания.

Комментарии

Спасибо за восстановленные материалы