Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 94
Числа Мерсенна имеют вид 2n-1
насколько я помню, 2^n — 1 было…
Думаю что, вероятнее всего это связано с криптографией, так как многие крипто-алгоритмы используют большие простые числа и их устойчивость как раз заключается в трудности подбора и поиска больших простых чисел.
Простите, но «10 миллионов десятичных цифр» не используется ни в одном крипто алгоритме. И очень сомневаюсь что будут такие компьютеры, в которых такое использование возможно и уж тем более оправдано в течении нашей жизни.
> 13 число Мерсенна состоит из 157 цифр, 14 из 183.
Че-то не совсем понял? Это откуда так много цифр взялось?
2^13 — 1 = 8191
2^14 — 1 = 16383
Че-то не совсем понял? Это откуда так много цифр взялось?
2^13 — 1 = 8191
2^14 — 1 = 16383
16383 — совсем не простое число. Оно делится на 3. Не все числа этого ряда простые.
он ошибся, он наверное имел ввиду 13 и 14 простое число Мерсенна:
2^521-1, и 2^607-1
2^521-1, и 2^607-1
Там ещё запутанней. :)
Начиная с какого-то числа нет уверенности, что не пропустили пары-тройки простых чисел. То есть, они, возможно, существуют, и их ещё не нашли. Поэтому в данном случае, 45-е число — это не 45-е подряд число Марсена, это 45-е найденное. :)
Начиная с какого-то числа нет уверенности, что не пропустили пары-тройки простых чисел. То есть, они, возможно, существуют, и их ещё не нашли. Поэтому в данном случае, 45-е число — это не 45-е подряд число Марсена, это 45-е найденное. :)
Мне всё нравится, просто вы сказали что «Числа Мерсенна имеют вид 2n-1, где n — натуральное число», и что «13 число Мерсенна состоит из 157 цифр»… и можно было бы запутаться(что и случилось с FB3 ), подумав что 13-ое число имеет вид 2^13 — 1 = 8191. Я просто пояснил что имеется ввиду 13-ое простое число Мерсенна. Ибо не все знакомы с этой тематикой, и не всем понятно… что говоря номер числа Мерсенна имеется ввиду простое число Мерсенна (именно из-за этой путаницы так много комментариев...)
P.S> лично у меня никаких непоняток и претензий нет =)
P.S> лично у меня никаких непоняток и претензий нет =)
Спасибо всем, кто откомментил. Я уже разобрался и внизу отписался для всех, кто затупил, как я и не сразу понял.
Неужели вы первый раз слышите слова простое число и криптография?
Вобщем мое предположение оказалось верным — ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE
Используется этот алгоритм для определения простоты числа, а это весьма важная задача.
Также как выяснилось используется в генераторах случайных чисел.
ps не успел на работе ответить, заминусовали :/
Вобщем мое предположение оказалось верным — ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE
Используется этот алгоритм для определения простоты числа, а это весьма важная задача.
Также как выяснилось используется в генераторах случайных чисел.
ps не успел на работе ответить, заминусовали :/
Да, я имел ввиду тест Люка-Лемера — который в свою очередь использует в том числе и числа Мерсенна. Разве не применение к криптографии?
Вы так отчаянно пытаетесь мне доказать что их не сипользуют — хотя я нигде не написал что есть какой либо алгоритм базирующийся на выборке этих чисел. Так что ваш упрёк сомнительный Почитали бы дальше про генератор псевдослучайных чисел не прошёл.
Вы так отчаянно пытаетесь мне доказать что их не сипользуют — хотя я нигде не написал что есть какой либо алгоритм базирующийся на выборке этих чисел. Так что ваш упрёк сомнительный Почитали бы дальше про генератор псевдослучайных чисел не прошёл.
Нет, для криптографии они совершенно бесполезны. Там в качестве ключа каждый раз генерируются новые случайные простые числа.
вспомнил, утром жеж фид читал)
mathworld.wolfram.com/MersennePrime.html
связано с Простыми Числами. рядами. теорией чисел.
думаю, что для вас ключевой фразой будет эта:
Mersenne primes were first studied because of the remarkable properties that every Mersenne prime corresponds to exactly one perfect number. L. Welsh maintains an extensive bibliography and history of Mersenne numbers.
mathworld.wolfram.com/MersennePrime.html
связано с Простыми Числами. рядами. теорией чисел.
думаю, что для вас ключевой фразой будет эта:
Mersenne primes were first studied because of the remarkable properties that every Mersenne prime corresponds to exactly one perfect number. L. Welsh maintains an extensive bibliography and history of Mersenne numbers.
и еще немного информации для любознательного хабрачеловека: primes.utm.edu/notes/faq/why.html
Кто-то из великих математиков прошлого столетия (вроде Нейман, но я очень не уверен), сказал (цитирую по памяти), что «вероятно, все действительно интеренсные и необычные вещи происходят с такими числами, которые человек себе не может даже представить». Вот числа Мерсенна эта одна из попыток подобраться к таким числам.
Шифрование — один из самых очевидных вариантов.
Мне кажеться точнее было бы сказать 45 ПРОСТОЕ число Марсенна!
Мля, хабр затрахал. Есть чтоль какой-то хоткей, который коммент отправляет?
У автора топика в посте:
Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Последовательность чисел Мерсенна начинается так:
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,… (последовательность A000225 в OEIS).
</>
15=3*5
255 делится на 5 по определению. Какие ж это простые числа?
По той же ссылке со слов
The verification run using a different program on different hardware has already begun.
перечисляются простые числа Мерсенна.
n order for M_n to be prime, n must itself be prime. Так что у автора в посте враки. Или враки по ссылке.
одно из двух.
Укажите верное.
У автора топика в посте:
Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Последовательность чисел Мерсенна начинается так:
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,… (последовательность A000225 в OEIS).
</>
15=3*5
255 делится на 5 по определению. Какие ж это простые числа?
По той же ссылке со слов
The verification run using a different program on different hardware has already begun.
перечисляются простые числа Мерсенна.
n order for M_n to be prime, n must itself be prime. Так что у автора в посте враки. Или враки по ссылке.
одно из двух.
Укажите верное.
Блин, я облажался.
Что такое число Мерсенна?
А ссылка была на простое число Мерсенна и тема называется соответствующим образом.
Т.е. есть такие числа, числа Мерсенна, а среди них бывают и простые числа.
Тогда все становится понятным. Действительно, название топика несколько неудачно.
А кто математикой занимается, может откомментить, чем 45 число поможет науке и людям земли?
Что такое число Мерсенна?
А ссылка была на простое число Мерсенна и тема называется соответствующим образом.
Т.е. есть такие числа, числа Мерсенна, а среди них бывают и простые числа.
Тогда все становится понятным. Действительно, название топика несколько неудачно.
А кто математикой занимается, может откомментить, чем 45 число поможет науке и людям земли?
Блин, я облажался, автор, извини.
Что такое число Мерсенна?
А ссылка была на простое число Мерсенна и тема называется соответствующим образом.
Т.е. есть такие числа, числа Мерсенна, а среди них бывают и простые числа.
Тогда все становится понятным. Действительно, название топика несколько неудачно.
А кто математикой занимается, может откомментить, чем 45 число поможет науке и людям земли?
Что такое число Мерсенна?
А ссылка была на простое число Мерсенна и тема называется соответствующим образом.
Т.е. есть такие числа, числа Мерсенна, а среди них бывают и простые числа.
Тогда все становится понятным. Действительно, название топика несколько неудачно.
А кто математикой занимается, может откомментить, чем 45 число поможет науке и людям земли?
ппц, чо минус ставить-то? Ставьте автору топика, за то что он не отличает простое число от непростого. И хабру, за то что комменты постит не по нажатию на «написать», а хер знает как.
Надо озаглавить так: Найдено 45 число Мерсенна, которое является простым.
Тогда сразу понятно, что числа Мерсенна не обязательно простые. На википедии написано так:
Число́ Мерсе́нна — числа вида Mn = 2n — 1, где n — натуральное число. Названы в честь французского математика Мерсенна.
Последовательность чисел Мерсенна начинается так:
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,… (последовательность A000225 в OEIS)
Иногда числами Мерсенна называют числа Mp с простыми индексами p. Эта последовательность начинается так:
3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607,… (последовательность A001348 в OEIS)
Что значит простой индекс? Это еще одно понятие, или подразумевается, что p — простое число? Если так, то 45 — не простое число.
Не понятно.
Тогда сразу понятно, что числа Мерсенна не обязательно простые. На википедии написано так:
Число́ Мерсе́нна — числа вида Mn = 2n — 1, где n — натуральное число. Названы в честь французского математика Мерсенна.
Последовательность чисел Мерсенна начинается так:
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,… (последовательность A000225 в OEIS)
Иногда числами Мерсенна называют числа Mp с простыми индексами p. Эта последовательность начинается так:
3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607,… (последовательность A001348 в OEIS)
Что значит простой индекс? Это еще одно понятие, или подразумевается, что p — простое число? Если так, то 45 — не простое число.
Не понятно.
«Надо озаглавить так: Найдено 45 число Мерсенна, которое является простым»
Это тоже не однозначно. Это звучит как «Найдено 45ое число Мерсена(тоесть 2^45 — 1 как стоит понимать), которое является простым(это звучит как особеностью этого числа). Соответственно тоже не тривиальный заголовок. Выше уже писали более удачные варианты.
Это тоже не однозначно. Это звучит как «Найдено 45ое число Мерсена(тоесть 2^45 — 1 как стоит понимать), которое является простым(это звучит как особеностью этого числа). Соответственно тоже не тривиальный заголовок. Выше уже писали более удачные варианты.
Автор все отличает, это я неправильно прочитал.
Поменяйте последовательность в топике — поскольку 63 и 255 точно не являются простыми числами.
В топике написано правильно.
В числах Марсенна выделяют подмножество чисел, которые являются простыми. 45 таковое было найдено.
Если же брать все числа Марсенна то их бесконечное множество.
В числах Марсенна выделяют подмножество чисел, которые являются простыми. 45 таковое было найдено.
Если же брать все числа Марсенна то их бесконечное множество.
Множество простых чисел тоже бесконечно:)
Не видел ни одного строгого доказательства ;)
Ну в общем это одна из причин, почему простые числа постоянно ищут — хотят узнать, а много ли их там.
Ну в общем это одна из причин, почему простые числа постоянно ищут — хотят узнать, а много ли их там.
o_O Это один из древних фактов теории чисел, восходит как минимум к Евклиду.
«Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.»
«Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.»
Убедили )
Хотя в натуральном числовом ряду плотность простых чисел стремительно падает.
Хотя в натуральном числовом ряду плотность простых чисел стремительно падает.
Логарифм «к стремительным функциям» никогда не относился. Отношение π(n) к n/ln(n) стремится к единице, когда n стремится к бесконечности. В районе гугола простых чисел больше чем одно на 500! Что, собственно, и позволяет использовать их в криптовании: куда не плюнь — с хорошей вероятностью попадёшь в простое число для не совсем уж забубенных чисел. А если ещё и плевать с умом…
Зачем?
Я туплю или все тупят? если последоваельнось (2 в степени n)-1, то 44 число будет (2 в степени 44)-1, а не (2 в 32582657 степени) — 1.
объясните кто-нибудь на пальцах простым пацанам — в чём суть этой шумихи?
в том, чтобы просто посчитать чему равно 2^x-1?
или как?
в том, чтобы просто посчитать чему равно 2^x-1?
или как?
Чтобы найти такое n при котором 2^n-1 — ПРОСТОЕ число.
Простых чисел бесконечное множество. А сто тыщ бакинских, которые нужно отмыть, конечное.
Блин, разобрался наконец (прочел по ссылке):
Mersennse primes, named for 17th-century French smarty-pants monk Marin Mersenne, follow the formula 2^p – 1, where the power p is itself a prime number. (Commenters, don't hesitate to pounce on errors in my arithmetic.)
Простые числа Мерсенна, названные в честь французского монаха Марина Мерсенна, жившего в 17 веке, соответствуют формуле 2^p — 1, где степень p также является простым числом.
Соответственно, проверяются два условия:
1. Степень p является простым числом
2. 2^p — 1 является простым числом
Mersennse primes, named for 17th-century French smarty-pants monk Marin Mersenne, follow the formula 2^p – 1, where the power p is itself a prime number. (Commenters, don't hesitate to pounce on errors in my arithmetic.)
Простые числа Мерсенна, названные в честь французского монаха Марина Мерсенна, жившего в 17 веке, соответствуют формуле 2^p — 1, где степень p также является простым числом.
Соответственно, проверяются два условия:
1. Степень p является простым числом
2. 2^p — 1 является простым числом
Только при соответствии числа этим двум условиям оно может называться ПРОСТЫМ числом Мерсенна.
Тогда получается, что открыто число Мерсенна.
Но оно не является простым, т.к. 45 (индекс числа) не является простым.
Или я не так опять что-то понимаю? Я уже задавал этот вопрос в комменте
Но оно не является простым, т.к. 45 (индекс числа) не является простым.
Или я не так опять что-то понимаю? Я уже задавал этот вопрос в комменте
При четвертое простое число Мерсенна.
В 1877 году Э.Лукас доказал, что число 2^127-1 простое. Для этого понадобилось около ста часов вычислений… ручных.
«… Лукас сделал себе шахматную доску и записывал числа по линиям этой доски, расставляя ладьи на местах единиц и оставляя пустыми клетки нулей. Циклически есложения можно тогда осуществлять как „игру“, следуя нескольким простым правилам. Потребовалось примерно 100 часов такой игры, чтобы вычислить r_127 по модулю 2^127-1.»
http://www.mccme.ru/free-books/matpros/i5127139.pdf.zip
В 1877 году Э.Лукас доказал, что число 2^127-1 простое. Для этого понадобилось около ста часов вычислений… ручных.
«… Лукас сделал себе шахматную доску и записывал числа по линиям этой доски, расставляя ладьи на местах единиц и оставляя пустыми клетки нулей. Циклически есложения можно тогда осуществлять как „игру“, следуя нескольким простым правилам. Потребовалось примерно 100 часов такой игры, чтобы вычислить r_127 по модулю 2^127-1.»
http://www.mccme.ru/free-books/matpros/i5127139.pdf.zip
Кстати, есть такое интересный русский м… артист Самое Большое Простое Число
Меня аж в дрожь бросило, когда увидел последний рекорд числа Мерсенна
А сто миллионов знаков числа Пи не видели?
3.141592653589793238462643383279502884197169399375105820974944592.jp/
3.141592653589793238462643383279502884197169399375105820974944592.jp/
Судя по теме, приз предусмотрен не человеку, нашедшему это число, а самому числу. На месте числа я бы отказался от денег :)
Lenta.ru: а проверку нового кандидата начали 26-го августа. Она проходит на двух компьютерах с процессором Pentium IV 2,4 гигагерца и должна занять около двух недель.
Вы: Его проверка идёт уже неделю на двух суперкомпьютерах,
Что-то вы погорячились на счёт суперкомпьютеров… (ну или Лента врёт)
Вы: Его проверка идёт уже неделю на двух суперкомпьютерах,
Что-то вы погорячились на счёт суперкомпьютеров… (ну или Лента врёт)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Найдено 45-е простое число Мерсенна?