Контрольні питання. Для простого числа число — гладкое относительно , что можно проверить с помощью функций FactorInteger и PrimeQ из пакета Mathematica

Висновки

Пример 9.3

Для простого числа число — гладкое относительно, что можно проверить с помощью функций FactorInteger и PrimeQ из пакета "Mathematica".

p = 70877; PrimeQ[p]

FactorInteger[p-1]

|| True

|| {{2, 2}, {13, 1}, {29, 1}, {47, 1}}

Для каждого простого числа наибольшая степень, которая все еще не превосходит, удовлетворяет неравенству

или, эквивалентно,.

Определим равенством

т.е. ‑ это произведение простых чисел в степени,.

Пример 9.4 (часть 1)

Рассмотрим число и предположим, что хотя бы для одного его простого делителя число гладко относительно.

Как вытекает из

Prime[15]

Prime[16]

|| 47

|| 53

имеются 15 простых чисел, не превосходящих. С помощью функций Prime, Log и Floor из пакета "Mathematica" можно вычислить по формуле (9.8):

n = 6700892281;

||4049567180360871571548109887351145051687154638935149024506072707670221428242481373494650191940316796203975457787003008948633600000000000000

Посмотрим (ради любопытства) на показатели простых чисел, входящих в разложение и меньших 50:

FactorInteger[R]

{{2, 32}, {3, 20}, {5, 14}, {7, 11}, {11, 9}, {13, 8},

{17, 7}, {19, 7}, {23, 7}, {29, 6}, {31, 6}, {37, 6},

{41, 6}, {43, 6}, {47, 5}}

Каждый сомножитель близок к, но не превосходит. Нам неизвестно значение, но мы предполагаем, что нам известны все простые сомножители, из которых состоит, и не известны их степени (знание степеней определяет собственно).

Если ‑ гладкое относительно, то каждая степень простого числа, которая делит, будет также делителем числа, так как не превосходит. Отсюда следует, что делит ().

По теореме Эйлера любое целое удовлетворяет сравнению
. Поскольку можем записать, где - некое целое составное число, тогда.

Возьмем теперь случайное целое, и найдем.

Если, тогда является делителем числа, а т.к. состоит всего из двух сомножителей ‑, то или.

Если, то из сравнения следует, что для некоего целого числа можно записать и соответственно (помним, что само нам неизвестно, ‑ простое число, а значит при ситуации число является одним из простых сомножителей).

Поскольку весьма неправдоподобно, что еще и, мы почти наверняка находим делитель числа (а именно), вычисляя, т.к. и. Заметим, что при этом не нужно вычислять абсолютное значение, ‑ достаточно значения.

Пример 9.4 (часть 2)

Чтобы найти делитель числа, выберем случайное между и и вычислим посредством функций Random, PowerMod и GCD из пакета "Mathematica".

a = Random[Integer, {2, n}]

GCD[PowerMod[a, R, n] - 1, n]

|| 3922094384

|| 81919

Это означает, что — делитель числа. Другим делителем будет. Заметим, что если бы тоже было гладким относительно, то при вычислении мы получили бы.

Ради любопытства посмотрим, из каких же сомножителей всё-таки состоит число, поскольку изначально мы предположили, что число гладко относительно, т.е. простые сомножители не превышают число.

FactorInteger[81919-1]

|| {{2,1},{3,3},{37,1},{41,1}}

Резюмируем -метод Полларда на следующем рисунке.

input: натуральное число

select границу гладкости;

calculate из (9.8);

select случайное

calculate;

if, then — делитель

else STOP или выбрать новое случайное.

Рис. 9.1. -метод факторизации Полларда.

Для того, чтобы -метод Полларда оказался невыполнимым, при формировании системы RSA часто выбирают так называемые безопасные простые числа. Это простые числа вида — (большое) простое число. В этом случае имеет ровно один малый делитель, равный.

1. Яким чином формується система RSA перед шифруванням?

2. Яким чином здійснюється шифрування в системі RSA?

3. Як реалізується електронний цифровий підпис в системі RSA?

4. Яким чином система RSA реалізує шифрування з електронним цифровим підписом?

5. Які атаки можливі на систему RSA?

6. Які швидкі алгоритми факторизації можуть бути використані для атак на систему RSA?

7. Які небезпечні режими існують в системі RSA?

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