Кстати, последовательность простых чисел Мерсенна 2N-1 имеет следующий вид:
M2=3, M3=7, M5=31, M7=127, M13=8191, M17=131071, M19=524287, M31=2147483647, ...
При этом показатели N, что удивительно, сами тоже являются простыми числами (доказательство этой теоремы можно найти в интернете):
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, ...
Существует и другая теорема, называемая теоремой Ферма-Эйлера, открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4*k+1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4*111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197*19197 + 8710*8710. Теорема была доказана Эйлером лишь через 100 лет.
И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.
Так что с простыми числами не все так просто. Есть и удивительные факты. Например, в 1883 г. русский математик И.М.Первушин из Пермского уезда доказал простоту числа 261 — 1 = 2305843009213693951. Даже сейчас компьютеру с запущенной вышеприведенной программой требуется несколько минут на проверку данного числа, а на то время это была поистине гигантская работа.
Кстати интересно, что существуют люди, обладающие уникальными способностями мозга — так например, известны аутисты, способные находить в уме (!) 8-значные простые числа. Как они это делают, непонятно. Такой пример описывается в книге известного врача-психолога Оливера Сакса “Человек, который принял жену за шляпу”. По некоторым предположениям, такие люди обладают способностью “видеть” числовые ряды визуально, и пользуются методом “решета Эратосфена” для определения, является ли число простым или нет.
Еще два интересных простых числа: 73939133 и 1979339333. Они интересны тем, что если от них убирать правую цифру, то каждое новое число - тоже простое:
73939133 - 7393913 - 739391 - 73939 - 7393 - 739 - 73 - 7
1979339333 - 197933933 - 19793393 - 1979339 - 197933 - 19793 - 1979 - 197 - 19 - 1
Для нахождения всех подобных чисел можно написать несложную программу, использующую написанную ранее функцию is_prime:
for v in xrange(10000001, 99999999, 2):
v0, v1, v2, v3, v4, v5, v6, v7 = v, v/10, v/100, v/1000, v/10000,
v/100000, v/1000000, v/10000000
if is_prime(v7) and is_prime(v6) and is_prime(v5) and is_prime(v4) and
is_prime(v3) and is_prime(v2) and is_prime(v1) and is_prime(v0):
print v0, v1, v2, v3, v4, v5, v6, v7
Несколько сотен лет математикам известна другая, не менее оригинальная последовательность, где все числа простые:
31 331 3331 33331 333331 3333331 33333331
Дальше ряд заканчивается, число 333333331 = 17*19607843, простым не является.
Желающие могут проверить самостоятельно, не обладают ли другие последовательности (51, 551, 61, 661 и пр) такими же свойствами.
Еще одна интересная гипотеза была выдвинута Ферма, который предположил, что все числа вида
являются простыми. Эти числа называются “числами Ферма”. Однако, это оказалось верным только для 5 первых чисел: F0=3, F1=5, F2=17,F3=257, F4=65537. В 1732 году Эйлер опроверг гипотезу, найдя разложение на множители для F5: F5= 641·6700417. Существуют ли другие простые числа Ферма, пока неизвестно до сих пор. Такие числа растут очень быстро (для примера, F7=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