Рассказы о математике с примерами на языках Python и C

К примеру, если взять два простых числа 444388979 и 444388909, то «закрытым ключом» будет 444388979, а открыто будут передано произведение 197481533549433911 (444388979 * 444388909). Лишь зная вторую половинку, можно вычислить недостающее число и расшифровать им текст.

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

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

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

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

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

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

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

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

2¹² * (2¹³ - 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.

Совершенные числа встречаются довольно-таки редко, их последовательность согласно Википедии, образует вид:

6,

28,

496,

8128,

33 550 336,

8 589 869 056,

137 438 691 328,

2 305 843 008 139 952 128,

2 658 455 991 569 831 744 654 692 615 953 842 176,

Кстати, еще Эйлер доказал, что все совершенные числа имеют только вид 2^p-1(2^p - 1). А вот нечетных совершенных чисел пока не обнаружено, но и не доказано что их не существует. Интересно проверить этот факт практически. Совершенное число 137438691328 обнаружил еще немецкий математик Иоганн Мюллер в 16-м веке. Сегодня такое число несложно проверить на компьютере.

Во-первых, слегка оптимизируем приведенную выше программу. Как нетрудно видеть, если число N делится нацело на P, то мы «автоматом» сразу находим и второй делитель N/P. Например, если 10 делится нацело на 2, то оно делится и на 10 / 2 = 5. Это позволяет заметно сократить число вариантов перебора. Во-вторых, используем тип чисел Decimal, позволяющий использовать большие числа. Обновленная программа выглядит так:

from decimal import *

def is_perfect(n):

    s = Decimal(1)

    p = Decimal(2)

    while p < n.sqrt()+1:

        if n % p == 0:

            s += p

            if p != n/p: s += n/p

        p += 1

    return s == n

print(is_perfect(Decimal('137438691328')))