AndreyS писал(а):
Но, к сожалению, она не сильно ускоряет расчеты - даже обычное умножение произвольного числа.
Тоесть умножаемые числа надо сначало либо факторизовать полностью (что при
больших числах ....), а потом умножить, либо сразу умножить обычным
способом.
В чистом виде она даже не используется в алгоритмах факторизации.
Еще как используется.
Например, многие алгоритмы факторизации (вплоть до моднючего NFS, хотя там все сложнее) основаны на идее поиска соотношения

из которого при

легко получить нетривиальный делитель
Обычно выбирается базовое число

и числа типа

пытаются разложить по простым не превосходящим

Если это удается, то число считается "хорошим" (

-гладким) и его разложение ("цифры") запоминается как строка некоторой матрицы (с количеством столбцов равным

- количеству простых чисел не превосходящих

). После того как накоплено достаточное количество строк матрица рассматривается над полем

(т.е. все "цифры" разложения берутся по модулю 2) и с помощью алгоритмов линейной алгебры в ней ищется линейная комбинация строк, дающая нулевой вектор. Эта же комбинация в исходной матрице дает вектор, все компоненты которого четные, а значит он соответствует некоторому квадрату

Это правая часть искомого соотношения, а в левой части стоит произведение тех

для которых строки их цифр участвуют в линейной комбинации дающей

Примерно так это и работает в алгоритмах факторизации.