УСКОРЕНИЯ МЕТОДА ФАКТОРИЗАЦИИ ФЕРМА НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ ПРИБЛИЖАЮЩИХ КОЭФФИЦИЕНТОВ

Анотація

Предложен способ ускорения метода Ферма факторизации чисел за счет использования приближающих коэффициентов, когда вместо решения уравнения N XY 2 2   в целых числах, где q  p = N  при больших значениях отношений p) > (q  q/p , решается уравнение KN XY 2 2   для  1 K  . Поскольку отношение  q/p неизвестно, то для поиска коэффициента K предлагается использовать метод покрытия. В случае использования исключительно целых нечетных K предложен упрощенный алгоритм их выбора.  

Ключевые слова: факторизация, метод Ферма, прореживание, ускорение.