Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 6 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

7
Введение
The problem of distinguishing prime numbers from composite numbers and of
resolving the latter into their prime factors is known to be one of the most
important and useful in arithmetic. Further, the dignity of the science itself
seems to require that every possible means be explored for the solution of a
problem so elegant and so celebrated.
Karl Friedrich Gauss «Disquisitiones Arithmeticae» (1801)
Проблема различения простых и составных чисел и разложения последних
в их главные факторы, как известно, является одной из самых важных и
полезных в арифметике. Далее, достоинство самой науки требует, чтобы
все возможные средства были исследованы для решения этой проблемы,
столь изящной и настолько знаменитой.
Карл Фридрих Гаусс «Арифметические исследования» (1801)
В 1977 г. трое ученых Рональд Райвест (Ronald Linn Rivest),
Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из
Массачусетского Технологического Института (MIT) опубликовали в
журнале Scientific American новый алгоритм шифрования, основанный на
идее двухключевого шифрования, названный по первым буквам фамилий
авторов методом RSA.
В этом методе известным параметром служит некоторое целое
число n большой длины (обычно 1024 или 2048 бита), являющееся
произведением двух простых чисел p и q . Эти числа p и q являлись
секретными параметрами метода, и для взлома системы RSA было
достаточно найти множители p и q, т.е выполнить разложение числа n на
простые сомножители.
На момент опубликования алгоритма RSA было известны лишь
небольшое количество алгоритмов факторизации, самым известным из
которых являлся метод Ферма. Эти методы позволяли на тот день
факторизовать числа, состоящие не более чем из 25 – 30 цифр. Поэтому
использование в качестве n натурального числа, имеющего более 100
десятичных знаков, гарантированно обеспечивало безопасность шифрования
                                                                                        7

     Введение

            The problem of distinguishing prime numbers from composite numbers and of
            resolving the latter into their prime factors is known to be one of the most
            important and useful in arithmetic. Further, the dignity of the science itself
            seems to require that every possible means be explored for the solution of a
            problem so elegant and so celebrated.
            Karl Friedrich Gauss «Disquisitiones Arithmeticae» (1801)

            Проблема различения простых и составных чисел и разложения последних
            в их главные факторы, как известно, является одной из самых важных и
            полезных в арифметике. Далее, достоинство самой науки требует, чтобы
            все возможные средства были исследованы для решения этой проблемы,
            столь изящной и настолько знаменитой.
            Карл Фридрих Гаусс «Арифметические исследования» (1801)

     В 1977 г. трое ученых Рональд Райвест (Ronald Linn Rivest),
Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из
Массачусетского Технологического Института (MIT) опубликовали в
журнале Scientific American новый алгоритм шифрования, основанный на
идее двухключевого шифрования, названный по первым буквам фамилий
авторов методом RSA.
     В этом методе известным параметром служит некоторое целое
число n большой длины (обычно 1024 или 2048 бита), являющееся
произведением двух простых чисел p и q . Эти числа p и q являлись
секретными параметрами метода, и для взлома системы RSA было
достаточно найти множители p и q , т.е выполнить разложение числа n на
простые сомножители.
     На момент опубликования алгоритма RSA было известны лишь
небольшое количество алгоритмов факторизации, самым известным из
которых являлся метод Ферма. Эти методы позволяли на тот день
факторизовать числа, состоящие не более чем из 25 – 30 цифр. Поэтому
использование в качестве n натурального числа, имеющего более 100
десятичных знаков, гарантированно обеспечивало безопасность шифрования

Страницы