Метод Полларда

Алгоритм факторизации для специального класса целых чисел

Пример 9.2

Пусть. Угадав, что, мы находим из

n = 5007958289; Sqrt[4*n + 200^2]

|| 141534

Из уравнений и, выводим.

q = (Sqrt[4*n + 200^2] + 200)/2

p = q-200

|| 70867

|| 70667

p * q == n

|| True

Итак, число должно быть большим. Способ достичь этого — взять больше, чем.

В литературе можно также найти несколько атак на систему RSA, имеющих вероятность успеха, которая лишь незначительно больше вероятности того, что случайно выбранное натуральное число, меньшее, имеет нетривиальный делитель, общий с числом. Тогда этот делитель — либо, либо. Вероятность того, что это произойдет, может быть вычислена с помощью функции Эйлера:

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

Ввиду того, что упомянутые выше "атаки" имеют малую вероятность успеха, обсуждать их не будем. Однако на них базируются некоторые другие методы факторизации.

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

Поллард описал способ разложения числа за шагов, где — наименьший простой делитель числа. Это объясняет, почему нужно брать и большими.

Основным предположением в -методе Полларда является то, что в разложении числа хотя бы один из двух[1] делителей, скажем,, обладает тем свойством, что имеет только малые простые делители.

Чтобы быть точнее, назовем целое число гладким относительно натурального числа, если все простые делители данного числа не превосходят. Мы будем предполагать, что — гладкое относительно некоторого.

Дата добавления: 2013-12-12