Рассказы о математике | страница 13

В чем хитрость? А в том, что произведение двух простых чисел вычислить несложно, а вот обратной операции не существует — если не знать первой части, то такая процедура может быть выполнена лишь перебором. И если взять действительно большие простые числа (например, в 2000 символов длиной), то декодирование их произведения займет несколько лет даже на современном компьютере (к тому времени сообщение станет давно неактуальным). Гениальность данной схемы в том, что в самом алгоритме нет ничего секретного — он открыт и все данные лежат на поверхности (и алгоритм, и таблицы больших простых чисел известны). Сам шифр вместе с открытым ключом можно передавать как угодно, в любом открытом виде. Но не зная секретной части ключа, которую выбрал отправитель, зашифрованный текст мы не получим. Для примера можно сказать, что описание алгоритма RSA было напечатано в журнале в 1977 году, там же был приведен пример шифра. Лишь в 1993 году при помощи распределенных вычислений на компьютерах 600 добровольцев, был получен правильный ответ.

В завершение темы простых чисел, приведем вид так называемой “спирали Улама”. Математик Станислав Улам открыл ее случайно в 1963 году, рисуя во время скучного доклада на бумаге числовую спираль и отмечая на ней простые числа:

Как оказалось, простые числа образуют вполне повторяющиеся узоры из диагональных линий. В более высоком разрешении изображение выглядит так (картинка с сайта http://ulamspiral.com):

В общем, можно предположить что далеко не все тайны простых чисел раскрыты и до сих пор.

6. Совершенные числа

Еще одно удивительное свойство мира чисел было доказано еще Евклидом: если число вида 2^>p-1 является простым (уже известное нам число Мерсенна), то число 2^>P-1(2^>p-1) является совершенным, т.е. равно сумме всех его делителей.

Рассмотрим пример для p=13:

2^>13-1 = 8191. Как показывает приведенная ранее программа, 8191 - действительно простое число.

2^>12*(2^>13-1) = 33550336.

Чтобы найти все делители числа и их сумму, напишем небольшую программу:

def is_perfect(n):

sum = 0

for i in range(1, int(n/2)+1):

if n % i == 0:

sum += i

print(i)

print("Сумма",sum)

return sum == n

is_perfect(33550336)

Действительно, 33550336 делится на числа 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8191, 16382, 32764, 65528, 131056, 262112, 524224, 1048448, 2096896, 4193792, 8387584, 16775168. И сумма этих чисел равна искомому 33550336.