Найдено очередное самое больше простое число

bmv007

мая этого года участником проекта GIMPS было найдено еще одно простое число.
Сейчас оно проверяется на других компьютерах, чтобы уберечься от каких-либо случайных ошибок.
В связи с этим я еще раз приглашаю присоединиться к мех-матской команде проекта GIMPS.
Как это сделать подробно написано на странице
http://vilenin.narod.ru/gimps.htm

bmv007

up

satyana

какой практический толк в gimps я так и не понял...
вот FAD - это хоть пользу каку-нить принесет

Genek62

математикам просто заняться нечем, вот они ищут ненужные числа

bmv007

ап

urchin

Напиши это число.

anna13

согласен

nikmif

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

Xephon

именно числа Мерсенна использовать для таких целей не очень хорошо
так как по их структуре алгоритм разложения легче

s_varya

Ты выложи текст, инета нет

dimaxd

GREAT INTERNATIONAL MERSENNE PRIME SEARCH
Смысл задачи состоит в том чтобы найти простые числа в виде 2########-1, где ######## - простое. Самое большое из известных ныне простых чисел имеет более 7 миллиона цифр в десятичной записи (224036583-1 - 7235733 знаков). Вам предлагается найти числа больше этого, т.е. Вы сможете похвастаться, что Вы нашли самое большое из известных простых чисел. Плюс объявлен приз в сумме $100,000 за нахождение простого числа с 10 миллионами цифр. Шанс найти такое число на одном компьютере довольно мал, но если мы объединим много компьютеров, то вероятность того, что этот приз достанется именно нам сильно возрастет. Еще немного по поводу призов: призы (до $5,000) получат все, кто нашел хотя бы одно новое (если оно на момент нахождения будет самым большим) простое число.
Более подробную информацию можно найти на http://www.mersenne.org
А на http://www.mersenne.org/math.htm можно найти описание алгоритмов проверки числа на простоту, используемых в программе.
Присоединиться к поиску чисел могут все желающие.

Далее описывается, как, собственно, присоединиться к проекту.

illegal

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

Custodian

Интересно, а как же проверяют такие числа на простоту? Полиномиальный алгоритм вроде бы придумали буквально в том году, а размеры чисел настолько большие, что 100% сказать, что данное число простое просто не хватит времени.
Если это числа определенного вида (см. пост alessio) и для них есть более быстрые алгоритмы разложения, тогда какой практический толк в самих числах? Кроме того, если они знают все простые числа и могут сказать нашли ли мы новое число, тогда использование в системах шифрования получается вообще не допустимым - перебираем все известные простые и ключик раскладываем на множители.
Скорее всего даже при всем желании, денег получить не удастся. Если бы это было так легко сделать, то по 5000$ не бросали бы налево и направо. Значит написание прог будет просто пустая трата собственного времени.
Единственно объяснение почему платят деньги - поиск новых идей и алгоритмом, а как следствие - новые методы шифрования (более длинные ключики) и новые методы взлома.

antcatt77

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

Custodian

т.е основные вычисления уходят не на генерацию числа, а на проверку того факта, что данное число простое.
Это понятно. И в случае если число составное, то чаще всего можно это быстро определить. Но если число простое, тогда лучшее - полиномиальная проверка. Возьмем теперь примерный порядок числа. Как было написано: N = 2^224036583. Берем очень быстрый комп: F = 10Ггц < 2^40. Тогда время для одного компа, пусть даже алгоритм линейный будет T = N/F = 2^(224036583-40). Сколько бы компов не подключить к данному проекту сказать, что число простое на 100% невозможно. Где ошибка в рассуждениях? За что платят бабки?

Xephon

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

Xephon

он полиномиален не по числу (такой кубичный - даже решето Эратосфена )
он полиномиален по длине этого числа

Custodian

он полиномиален не по числу (такой кубичный - даже решето Эратосфена )он полиномиален по длине этого числа

Дело говоришь.
А насчет вероятностных аглогитмов - они только лишь с большой вероятностью могут сказать что число простое. В реальных задачах шифрования конечно больше и не надо. Но тогда не понял за что же бабло платят? За то что написали распределенную систему поиска псевдопростых чисел?

tania_12

Но тогда не понял за что же бабло платят? За то что написали распределенную систему поиска псевдопростых чисел?
бабло за то, чтоб ты её у себя запускал

Custodian

бабло за то, чтоб ты её у себя запускал

Наконец-то понял - чуваки тестят свою систему и плятят бабки. Спасибо.

antcatt77

Можно сказать, что бабки платят просто так. За общее развитие и т.д.
ps
За что платят нобелевскую премию? Или за победу в школьных олимпиадах?

antcatt77

> Наконец-то понял - чуваки тестят свою систему и плятят бабки. Спасибо.
Неправильно.
Бабки платят одни, а систему пишут, развивают, поддерживают другие.

Custodian

За что платят нобелевскую премию? Или за победу в школьных олимпиадах?

В идеале для повышения уровня образования, для поддрежки интересов и т.д. Но на самом деле, просто потому, что кто-то получает бабки. Не знаю как это устроено в нобелевских премиях, а с олимпиадами просто (по информатике по крайней мере):
Либо находится фирма, которая дает бабло и потом получает неплохих кадров (IBM для олимпиады ACM). Либо просто кто-то разводит спонсоров (например CBOSS олимпиады). На России по информатике для школьников это было именно так (Andreff Soft получил судя по всему очень нелхохие доходы). Очень часто разводят департаменты образования и т.д. Подумай внимательно, а за чей счет идут школьные олимпиады, оказываются школьники за участие платят бабки (не сами школьники, а города, и т.д.). Где здесь благотворительность?
Неправильно. Бабки платят одни, а систему пишут, развивают, поддерживают другие

Взаимовыгодное сотрудничество не более. Одни объявили тендер, а другие написали систему и выиграли тендер. В конечном итоге у заказчика прибыль. В целом детали уже не столь интересны, примерная схему я понял, остальное неважно.
Всем спасибо за коментарии. Предлагаю дальше эту тему не продожать или в отдельном треде, а то как-то уже не соответствует тематике.
Оставить комментарий
Имя или ник:
Комментарий: