Самое большое простое число

[darksab0r]

«Это 45-е простое число» — неправда ваша, их все же не так мало. В других-то местах есть уточнение, что это простые числа Мерсенна, а тут как-то странно, да еще и со ссылкой на статью «Простое число» в Википедии.

[maxshopen]

Всегда удивляло — зачем эти числа нужны? Ведь оперировать ими в каких либо расчетах не представляется возможным. Исключительно спортивный интерес?

Кстати простые числа Мерсенна это чуть-чуть не то, что вы написали. Простые числа Мерсенна это числа 2ⁿ-1, где n — простое число (а не натуральное). Это заметно уже по числу 15 — оно не простое :)

[gkozlenko]

> Всегда удивляло — зачем эти числа нужны?
Вроде как для шифрования…

> Простые числа Мерсенна это числа 2ⁿ-1, где n — простое число
Это тоже, мягко говоря, не верно.
11 — простое число
2¹¹ — 1 = 2047
2047 / 23 = 89
Простые числа Мерсенна это простые числа из последовательности Мерсенна (Mn = 2ⁿ — 1), где n — натуральное число. Но у них есть свойство — если Mn — простое, то и n — простое. Поэтому последовательность чисел Мерсенна используют для поиска простых чисел.

[maxshopen]

>> Вроде как для шифрования…
да я тоже слышал про это «вроде», но реально не представляю как это можно использовать такое число для шифрования :))

>> Это тоже, мягко говоря, не верно.
Да, и правда, я хоть и точнее сформулировал, но все равно криво — не до конца:)
Я описал вот это
Спасибо, что поправили+.

[theOnlyBoy]

Все очень просто. Простые числа используются, например, для систем шифрования с открытым ключем, где основным принципом является задача разложения числа на множители.
Можно прочитать об известной системе RSA, например, здесь: ru.wikipedia.org/wiki/RSA

[maxshopen]

Ну если честно — то нифига не просто, и ничего не объясняет. Я и так понимаю, для чего нужны простые числа достаточно большие. Но все же относительно. Прочтите по вашей ссылке алгоритм генерации ключей:

1. Выбираются два больших случайных простых числа p и q
2. Вычисляется их произведение n=pq !!!
3. Вычисляется Функция Эйлера phi(n)=(p-1)(q-1) !!!
....

А теперь подставьте сюда вместо p и q пару простых чисел Марсенна например 44-е и 45-е. Как думаете — кто то дождется генерации такого ключа?

[theOnlyBoy]

А вы думаете такие числа будут применять на вашем настольном ПК? :)

[maxshopen]

Исходя из того, какие ограничения накладываются на простые числа в том же RSA — не думаю, что в ближайшие годы их где либо будут использовать. Потому что для RSA достаточно чисел гораздо-гораздо меньших, например типа такого — 439351292910452432574786963588089477522344331.

Глядя затраты на нахождение этих чисел — имхо, нерационально их использование.

[theOnlyBoy]

В чем вы пытаетесь меня-то убедить? :) Я привел RSA как пример.
Ваше непонимание надобности подобных исследований простых чисел никоим образом не опровергает необходимость и актуальность оных, которые проводятся людьми, на порядок более смыслящими в этой области, чем мы с вами вместе взятые.

[maxshopen]

Да я не убедить, скорее наоборот — понять хочу. Я пытался найти информацию о том, зачем эти числа нужны — единственное объяснение — что большие простые числа используются в криптографии, но это больше похоже на стандартную отмазку :)

А то что люди смыслящие… ну даже не знаю, многие эксперименты проводятся из спортивного интереса и любопытства. Не исключаю что и поиски этих чисел — очередное «покорение вселенной» без практического применения.

[theOnlyBoy]

Ну как спортивный… получить четверть+ миллиона зеленых президентов тоже тот еще интерес :)

[maxshopen]

С этим не поспоришь :)

[ibnteo]

Не надо искать смысла во всем, иначе и жизнь покажется бесполезной.

[calx]

Не исключено, что какой-то практический интерес в этом все же есть. Хотя бы и такой как в фильме «Пи» :)

[1Tiger1]

Прогрессс двигают любопытство и лень. (с) не помню кто.

[ikohut]

>> Вроде как для шифрования…

>> да я тоже слышал про это «вроде», но реально не представляю как это можно использовать такое число для шифрования :))

Нет. для шифрования ТАКИЕ большие числа не используются. При использовании асиметричных криптосистем типа RSA оперируют числами порядка пары тысяч двоичных разрядов.

[tegger]

> Вроде как для шифрования…

На самом деле — just for fun.

[eugenius_nsk]

just for scientific fun ;-)

[max7]

Зачёт!

[vilgeforce]

Именно что n — не простое число, а степень двойки, что очевидно из приведенной последовательности.

[imil]

В криптографии нужны случайные простые числа. Как можно использовать для шифрования числа Мерсенна, если их всего известно 46?

[smartov]

А это для эстонской криптографии.
Раскриптовать легко, но долго — ппц.

[gkozlenko]

Ни кто же не говорит использовать только простые числа Мерсенна. Их можно использовать наряду с обычными простыми числами.
Правда использовать такие огромные числа для шифрования, по крайней мере сейчас, есурсы не позволяют.

[gkozlenko]

то есть ресурсы… :-)

[imil]

Нельзя использовать для шифрования простые числа Мерсенна. Ни наряду с обычными простыми числами, ни отдельно. По той простой причине, что все они прекрасно известны, следовательно, использовать их для генерации ключа — все равно, что иметь пароль qwerty.

[kurokikaze]

… которыми заведуют жиды. ;)

[kurokikaze]

В криптографии очень широко используются.

[putnik]

Немного наоборот. Это действительно 46-е число Мерсена, но 45-е было найдено на две недели позже, а не раньше.

[grep0]

И даже это не совсем верно, потому что еще не все числа меньше этого проверены, так что вполне вероятно, что где-нибудь между 44-м и 45-м есть еще парочка.

[lexa0]

s/45-е простое число/45-е простое число Марсена/

[makaron]

Это что-то из разряда "… американский исследовательский институт провёл исследование на тему: не слишком ли много исследований проводят американские исследовательские институты..." :)

[makaron]

Да какая разница :), я просто не вижу практического применения таких знаний

[kurokikaze]

Это нужно для криптографии.

[kurokikaze]

Сорри, не туда.

[bmm]

Простите, 45-е простое число??
Список простых чисел

[seneast]

Имеются ввиду простые числа Мерсенна

[max7]

Это уже не первый пост на Хабре про «простые числа Мерсенна». И в них полно коментов ....(см. выше ↑) Это огорчительно [:╣

[ernt]

Осталось создать тематический блог «Простые числа Мерсенна» :)

[kurokikaze]

Почему же огорчительно? :) Математика — это очень интересно :)

[VoidEx]

Почему пишут пятизначная цифра, но не пишут пятисимвольная буква?

[Adam_B]

блеск! Даже не задумывался когда читал, а сейчас — ржу в кулачок, чтобы не разбудить домочадцев.

[smartov]

Цифры сколько-то там значными не бывают. Они всегда 1 знак.
Многозначные только числа.

[smartov]

Поэтому
1) Пятизначное число
2) Пятибуквенное слово
Всё на месте

[VoidEx]

Ну так я потому и удивляюсь, что многозначных цифр не бывает, ибо цифра и есть знак.

[smartov]

Наверное тогдя я чего-то не понял. :) А к чему вы свой комментарий написали?

[VoidEx]

По-моему он вполне однозначен.
Почему во фразе «пятисимвольная буква» каждый увидит что-то неладное, а «пятизначную цифру» я слышу повсюду?

[smartov]

А… В этом смысле.
Просто неграмотность имхо

Мне просто не совсем было ясно как это относится к данному топику. Всё пытался привязать. А это просто «размышления на тему».

[VoidEx]

это 45-е простое число Мерсенна делает количество атомов в известной вселенной ничтожной величиной, с их «всего 80-значной цифрой»

Я вот тут заметил :)

[smartov]

Ох! А я просмотрел! Теперь все ясно. Спасибо.

[kostitsyn]

заголовок вообще не имеет ничего общего с реальностью. Самого большого простого числа не существует.

[nooze]

существует самое большое из известных…
Каждый уже придрался к чему только мог, не комменты а собрание редактуру какое-то :)

[burzum]

Выкачал я это тринадцатимегабайтное число. Удивительно, но его запись не содержит моего номера телефона.

[homm]

Оно пятимегабайтное, как верно заметили, и состоит из одних двоичных единичек.

[burzum]

Не знаю, я десятичное выкачивал.

[Evilutioner]

Не подскажешь ссылку?

[burzum]

prime.isthe.com/no.index/chongo/merdigit/long-m37156667/prime-c.html.gz
6,14 Мб
Вообще, я по другой ссылке смотрел, там просто цифры шли, а тут с разделителями разрядов, ну можно поиском/заменой убрать :)

[Nafanoid]

Разве 15 и 63 — простые?

[theOnlyBoy]

А чего минуснули-то? Вполне нормальный вопрос.
Автор статьи ошибся немножко при формулировке Мерсенна: n в данном ряде Мерсенна — натуральное число. Есть также ряд Мерсенна, где индекс p — простое, и тогда ряд выглядит так:
3, 7, 31, 127, 8191, 131071, 524287,…

[theOnlyBoy]

уточнение: в данном случае индекс p — это простое n

[mr_smile]

вообще, я где-то читал, что такого рода числа содержат в себе скрытую информацию о нашем мире (это относилось к числу Пи, но я думаю простые числа тоже содержат в себе подобную информацию)

встает вопрос, как эту информацию расшифровать :)
вот это уже задачка поинтереснее будет

[mr_smile]

> информация, которая содержится в простых числах (если она там вообще есть) не дает ничего нового

т. е. Вы знаете все, что может(гипотетически) содержать эта информация?

или что есть для Вас «новое»?
формула бессмертия человека для вас «новое»? или не «новое»?

:)

[mr_smile]

ну тогда я Вас не правильно понял, ведь Вы сказали, что эта информация не содержит ничего нового. что Вы имели ввиду? спрашиваю с целью познания, а не с целью уличения в чем то)

вообще, информация новой или старой не может быть сама по себе. это свойство присуще информации только лишь относительно кого-то, кто эту информацию воспринимает.
я, например, когда учился в школе, не любил уроки истории, и если я щас начну читать исторические книжки, то вся(ну почти вся) полученая для меня информация будет новой :)
понимаете?
то же самое с информацией зашитой в кодах.

а теперь давайте представим, сколько информации еще предстоит открыть человечеству. а вы говорите — «не дает ничего нового». это все равно что утверждать, что всей вселенной мы единственная планета с разумной жизнью =)

[Dzinko]

Не понял % 70, но звучит очень круто и внушительно 13 Мб цифр ух ты, не знал что кто-то ищет самое большое просто число =)

[freehome]

Там еще писали в сми, что они задействовали для поиска все компы и уже начали искать следующее число, но думают, что не найдут.

[yad]

ru.youtube.com/watch?v=gz_loRAhxp4&feature=related

[AndreyVHS]

я придумал самое большое число!

это то что сверху +1!

[Regis]

Это число не будет простым, а потому — бесполезно.

[Regis]

13 мб одних только цифр
И вовсе не 13мб, а всего чуть более 5мб. И все эти цифры — единицы (в двоичной записи) :)
Если быть точным 43,112,609 двоичных единичек. И это число чертовки хорошо «архивируется» :)

[homm]

В этом отличие интеллекта от алгоритма. Вы способны с ходу сказать формулу сверх компактной записи, но на архивацию реальных пяти мегабайт данных у вас уйдут годы :)

[GMM]

ради интереса сжал в 7z — получилось 940 байт.

[denplis]

0|0|000010100100011101100010100001|000010| — 1
скорее всего не так записывается, но все же, это не 940байт

[denplis]

А если это число умножить на два и добавить 1?

[grep0]

Результат будет составным.
2 (2^p-1) +1 = 2^p+1-1
Поскольку p нечетное, p+1=2m, так что
2^2m-1 = (2^m+1)(2^m-1)
И вообще, число вида 2^m-1 не может быть простым, если m составное (упражнение ;) ).
Но даже если m простое, это еще ничего не значит: 2¹¹-1=2047=23*89

[qweewq]

а мне за ваш пост поставили зачёт по матану :) ГРАН МЕРСИ, добрый автор…

ЗЫ извините, пожалуйста, что так жестоко воспользовался Вашим драгоценным трудом

[debacle]

По-моему, формулировка заголовка некорректна… для того, чтобы утверждать, что это самое большое число, нужно точно знать, что оно последнее простое число и больше него простых чисел нет… а это всего лишь самое большое из известных простых чисел…

[jerom]

Уже более двух тысяч лет люди знают, что ряд простых чисел бесконечен. Предки были очень умны.

Более того, даже известно, во сколько раз количество простых чисел меньше, чем составных.

[debacle]

кажется, вы не уловили главную суть коммента… я не хочу сказать, что есть самое большое простое число… я хочу сказать, что это НЕ является самым большим простым числом… именно потому, что ряд простых чисел бесконечен…
И зачем минусить — непонятно… если в том что я сказал что-то неверно, поясните?

[debacle]

А по поводу «известно, во сколько раз количество простых чисел меньше, чем составных. »:
Насколько я помню, множество простых чисел равномощно множеству натуральных чисел… это было курсе на втором…

[clover]

«Самое большое простое число» — группа такая есть! :)
У них есть песенка «Маленькие человечки».
Мне кажется, что она про хабрахабр! :)

[Pingwin32]

Я знаю ещё один вариант использования таких чисел, актуально для осеннего сезона в России. Есть программы вроде SuperPi, которые очень хорошо прогревают процессор. И таким образом можно отапливать помещения :)

[Regis]

Лучше BOINC поставьте, хоть от вычислений польза больше будет :)

[Regis]

Если бы это было никому не интересно, то этот топик не получил бы сотню комментариев.

[tamaki]

… Снупи, я знаю, что мы едем слишком быстро
Но, пожалуйста, убери с моих глаз свои лапки…

[mitko]

К вопросу о том, зачем это: давно известно что наука — это способ удовлетворения личного любопытства за счет государства. Просто кому-то показалось забавным сделать такие вычисления, заняв какой-нибудь суперкомпьютер. Ученые — они ведь как дети :)

[gaki]

> Нет надежды на написание этого числа: 243,112,609-1 заняло бы в длину много километров.

Нет, этого нельзя так оставлять, надо что-то замутить! Например, построить специализированный дорожный разметчик и нанести его в виде разделительной полосы на трассе Санкт-Петербург — Владивосток.

[nAggOHOK]

Заметьте что ряд: 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 — Это Числа Марсена
А найдено 45-е ПРОСТОЕ число Марсена.
Последовательность простых чисел Марсена начинается: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647
p.s. Не умничаю, просто дисонанс начался когда речь идет о простых числах… а в ряде вижу «15»

[ranx]

И куда делись простые числа 2, 5, 11, 13, 17, 19 и пр.?..

[ranx]

А, понял, они немерсеновские :)

[Racoon]

А черт бы с ним, с Мерсенном… Скажите лучше, найдено ли последнее обычное простое число? Я имею в виду то, которое без остатка делится только на себя и единицу. :)

[paly4]

простых чисел бесконечное множество. доказательство от обратного: пусть их конечное число и последнее, например, n. тогда перемножим все простые числа до n включая само n и прибавим к произведению 1. получившееся число не будет делиться на все простые числа до него, т. е. будет простым. следовательно простых чисел бесконечное множество.

[paly4]

начнем с того, что 500 не простое число.
ну да ладно… предположим, что 11 — последнее простое число. тогда перемножим все простые числа до 11 включительно и прибавим к нему 1 => 2*3*5*7*11+1=2311 — простое число, что можно проверить в списке простых чисел: ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
следовательно предположение неверно и простых чисел бесконечно много…
хотите, можете проверить то же самое с числом близким к 500… :)

[Racoon]

Да знаю я, знаю. Это я вроде как неудачно пошутил.

[pxx]

По-моему, у кого-то слишком много свободного времени и вычислительных ресурсов…

[obscuro]

А я могу в пицот раз длиннее нахерачить — хрен проверите простое оно или нет.

[Elastep]

главное не попались, чтоб на чётную цифру число не заканчивалось

[Regis]

Оно будет заканчиваться на 5 :)

[cc00ffee]

Круто, а где можно купить?

[askarmuk]

Что было на картинке? Кто-нибудь помнит?