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

Дальше ряд заканчивается, число 333333331 = 17*19607843, простым не является.

Желающие могут проверить самостоятельно, не обладают ли другие последовательности (51, 551, 61, 661 и пр) такими же свойствами.

Еще одна интересная гипотеза была выдвинута Ферма, который предположил, что все числа вида

являются простыми. Эти числа называются “числами Ферма”. Однако, это оказалось верным только для 5 первых чисел: F₀=3, F₁=5, F₂=17,F₃=257, F₄=65537. В 1732 году Эйлер опроверг гипотезу, найдя разложение на множители для F₅: F₅= 641·6700417. Существуют ли другие простые числа Ферма, пока неизвестно до сих пор. Такие числа растут очень быстро (для примера, F₇=340282366920938463463374607431768211457), и их проверка является непростой задачей даже для современных компьютеров.

Актуальны ли простые числа сегодня? Еще как! Простые числа являются основой современной криптографии, так что большинство людей пользуются ими каждый день, даже не задумываясь об этом. Любой процесс аутентификации, например, регистрация телефона в сети, банковские платежи и прочее, требуют криптографических алгоритмов. Суть идеи тут крайне проста и лежит в основе алгоритма RSA, предложенного еще в 1975 году. Отправитель и получатель совместно выбирают так называемый «закрытый ключ», который хранится в надежном месте. Этот ключ представляет собой, как, наверное, читатели уже догадались, простое число. Вторая часть — «открытый ключ», тоже простое число, формируется отправителем и передается в виде произведения вместе с сообщением открытым текстом, его можно опубликовать даже в газете. Суть алгоритма в том, что не зная «закрытой части», получить исходный текст невозможно.

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

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

Числа Мерсенна

Про простые числа Мерсенна уже упоминалось ранее, они достаточно интересны, чтобы остановиться на них подробнее. Это числа, вычисляемые по формуле N = 2n - 1.

Но не все так просто. Во-первых, не все числа такого вида являются простыми, была доказана теорема, что число N простое, только если n является простым. Однако, это необходимое но не достаточное условие, к примеру 11 простое число, а 211-1 = 2047 = 23·89 простым не является.

Используя вышенаписанную функцию is_prime, получить первые 9 чисел Мерсенна весьма просто.

m = 0

for p in range(2, 32):

if is_prime(p) and is_prime(2**p - 1):

m += 1

print("M{} = {} (p={})".format(m, 2**p - 1, p))

С помощью программы легко получить первые 10 чисел Мерсенна.

M1 = 3 (22-1)

M2 = 7 (23-1)

M3 = 31 (25-1)

M4 = 127 (27-1)

M5 = 8191 (213-1)

M6 = 131071 (217-1)

M7 = 524287 (219-1)

M8 = 2147483647 (231-1)

M9 = 2305843009213693951 (261-1)

Однако, проверка таких чисел на языке Python занимает весьма приличное время - даже нахождение числа M10 может занять более получаса.

К счастью для нас, еще в начале прошлого века математики Люка в 1870г и Лемер в 1930г доказали теорему о том, что простоту числа Мерсенна можно узнать, проверяя лишь остатки от деления определенной последовательности (подробнее можно прочитать в Википедии). Этот тест выполняется в тысячи раз быстрее, и позволяет проверять числа гораздо большей длины.

Полный текст программы приведен ниже.

import math, time

def is_prime(n):

if n % 2 == 0 and n > 2:

return False

for i in range(3, int(math.sqrt(n)) + 1, 2):

if n % i == 0:

return False

return True

def is_mersenne_prime(p):

# Lucas-Lehmer 2^p-1 number primality test

if p == 2:

return True

else:

m_p = 2**p - 1

s = 4

for i in range(3, p+1):

s = (s ** 2 - 2) % m_p

return s == 0

m = 0

for p in range(2, 100):

if is_prime(p) and is_mersenne_prime(p):

t_start = time.time()

res = is_mersenne_prime(p)

m += 1

val = 2**p - 1

print("M{} = {} (p={}, T={})".format(m, val, p, time.time() - t_start))

В программу также добавлен вывод времени расчета для каждого числа.

Интересно заметить, что простота числа M25 = 221701-1 была доказана студентами Noll и Nickel в 1978г с помощью университетского компьютера, и это “открытие” попало даже в телевизионные новости. Сейчас с помощью вышеприведенной программы, это число можно сделать даже на 20-долларовом компьютере Raspbery Pi, сама проверка занимает не более минуты.

С помощью 2х вышеприведенных функций легко проверить такое число Мерсенна:

bp = 2**21701 - 1

print(bp, is_mersenne_prime(21701))

Нельзя не признать, что само число 221701-1 выглядит достаточно внушительно:

44867916611904333479495141036159177872720902372938861301036480447512785609158053637162018395920183108689149613973035533621134551674715287880007134345347194681025732056939825423723521750452980127215084299527266875706892007262798468825185681532142985720637290299313726344463257416449344509835102458816789016394945893696705168502436180232259551672603295389186364437045681350697590862198047118901225352609650331560624641680529360950276322519541199378781611887950368067065467094570602703933944508795918017973611326798274338403964825448745270434393258865935311826270281291301767537362073560471706796018086986188192305477308263143033689309402401116023184218739861793173381674293624039080146446533167893142403441626243986354829868152963856856097613981370008545290902178852760181267516916666189196652889272405457548015727583223936389690623948268629738406595342536881770621194098884299042222510205198907427651269590866489020849331593183544730378438673619905441075619665362094087700417583472204239335761771260615063239687136058218014855376128809648109025328444692060981149171853122623214490315199270347679840250650446624361158632712607371820441076129040576076156413981966443384174935945557589269550551384444249641738589326431062350244259749888495427561113138125373546749571089212977055534105306317668036525450115619994704703080975001831039096328170193148671686659220369588362291591980963840251182084839045643052580945876198697254235294718583716788165976228557375284260972377346244685323620326927812128869122804644917707943186384476057711810558228653120572801809938250702311789320142979213175068746598525343177694757992501015403459055756096150131796369342571712916973547166474698856592132612717244249685861542410597610354729550125380584497109056463991926448357223209008827764713220228439775757230755516658614028292960947522709456751199752268424383084190316769975828969408161512929731166188774631973942613003505328030528435929861943028814647224393409604332129915709479716480001751152901047730022099226496393622633345405009361146955156338963448113785646130979933903537929751619768669550563002423706161236691536299577305442116055910462682405728304933022695634876033547918117176704431651372729753611485207957283097607765933169252913861287726833830000755907168496373643201886627226059186824987046158950280121480310106220821760865120562920439756658081153617726352709131801387158672559847396101178548655217308890158788609324326427919178121708326042669857675282709609677929532780738060001705557411238564945972873592110131239116174462947424279402757853073650206058072089139080813381552120237889176959032725532187981806390188976611966923383780080589571180304127953763426872458894003176440733448130784320760858250357720163697308151884697269173048039142351116460009341135465682559795451407065757164712682892684340399927996841540378943787439234382545562253973300003977291497945580368468642313784723553952911754115108385290054865563784523161325911184338403975092561182541488447059744171236348865292897919507096247432485742758096709852132553243687088002636637356883647209281384466468348661473539477676114713952390574283871138643608927689646270265436227072361361556969326026972555137795806131512078396392381117163021488319719122953967241849650035686516897636532829829413559438271078909648012546818155830670649731025924561052079518365511691315910359549578098542021850858860195694976630351366074278129451101792937644085504395275589852388064138602439346909569031381270272833205694814223411334423565977453887542395353485301546284835327702006873689327611630437966491140077951840154972590243416512380587609900111470825767310676939441942826834427612997756892340669203408743659224466633723212596650417249730825215118303577011272768581293371366148392778532335573122542905472394542069919985611732624482347646980930805586007081976261003097963198812882873782621377463926668786498204922447802136607398552526766227205124310008056632919363553194966717056709446690809053625020657218419836547624618595375352039018705449062959037038925284556675116361168237279922207920794703117075921951295707710873733317931433110923531405719416365240907518118794096775462324423434250371711420947553571555908465792580645089870615111865933553809003552706994499748706917899889082891225016257753453229705906397483096836459677640750701051127649136815511445021677568414826304009394300853762240103073543616073297109679097852591173721376034038403903797326084264850909622924265141840684883798695123898530601713627917934581206083528373369371952855787986368194089909153037760311683730584329384267492189510884229753903906808988993523259437606901944039838823315225488711871355530334671879703287493612171018890720047791219983006575690550227543246901734749051876793980240930546447655515405860615566182339568500526080685358056916078877218441535928716267560418132595102517522928981353833074067246933111570873295331815501725771241383698605105802286768924861382741652271179538064625778814288737402101220075694269814240934893379113612806306410045157701609671517543787442511524203121293023260598375610136932287924468473569626893292863959506611559181514200293625478634965230187600993204860736747921056014359652196606989325320755082356901630669240688685505174445515739151017185696401582807173431580481627122423292641208991071222953038343766541925054971737959169869292375645057151727543470106206531135735154136115144300015873080448570355596137321380062748881332031472142823024949510022409370177712994235289702790490255826941441774321618772576455298250619988354955614763200793811728997204477597638052792510878225745663494703701392574625552528908681553926116252158243953964293657171414581341823547346468074289772645946104841180801333621512150598625594195401601933368973292090945435953301875202828322848138663871822530516790587144451339179411203328134884327892252621182901800244630979609876813374281202935998128401633959108387881070976339195584757402099414224321539543476019604874975720230127703172732861447718691961098975942332752633167063512960112700154075209382155551695503282689329429789346503176351007528609841743736084042408094015850910964618482805649640269394165006760210370817982850495571836159005709917919149733735278914364020463842602726375487527643414975692020200079346255666615166515258291939313433912222614621242014153365037286833662921186290423547789663783785467893012638041082143785487398866487992341179948504338667781255945413472465246231194881401316071628427281713042247869185631200192333698966933544361629391311041730956501694662754558875644345191269279600693551809271956450264294092857410828353511882751

К счастью для нас, язык Python может работать с большими числами неограниченной длины, ну и мощность современных компьютеров достаточно велика. Сама проверка этого числа методом Люка-Лемера заняла всего лишь 15с, разумеется, для компьютеров и программистов в 1978г это было гораздо более сложной задачей.

Изучение чисел Мерсенна продолжается энтузиастами и сейчас. Самым большим на момент написания книги простым числом, является число М₄₉ = 274207281 - 1, содержащее 22 338 618 знаков. А в начале 2018 года было найдено 50е число Мерсенна М₅₀ = 277232917-1. Его проверка заняла на 32-ядерном сервере Xeon 82 часа. Существует даже сеть распределенных вычислений https://www.mersenne.org, присоединиться к которой может любой желающий, для этого достаточно установить на компьютер программу для расчета.

Кстати, вывести число 277232917-1 совсем несложно с помощью Python. Само вычисление числа проблем не составляет, а вот стандартная функция print для таких длинных чисел не работает - результата дождаться так и не удалось. Однако, число можно вывести посимвольно, если каждый раз выводить остаток от деления на 10, и уменьшать число во столько же раз.

bp2 = 2**77232917 - 1

while True:

print(bp2%10, end='')

bp2 = bp2/10

if bp2 == 0: break

Разумеется, только вывод на экран таким способом займет порядка нескольких часов. Второй недостаток программы в том, что число выводится задом наперед, т.к. первыми выводятся самые младшие разряды, после вывода данные в файле придется перевернуть. Зато мы все-таки можем посмотреть, как выглядит самое больше найденное число Мерсенна (в перевернутом виде) в современной истории: 1709712679608160372856311737129564169399997264989729636740737…

Впрочем, все это уже сделали за нас, уже готовое число M₅₀ можно просто скачать по ссылке https://www.mersenne.ca/primes/digits/M77232917.txt, размер файла составляет 23Мбайт.

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