Все новости от 3 декабря 2003 г.

Общими усилиями найдено самое большое простое число

Число, в котором больше 6,3 млн цифр, уже шестое, найденное участниками проекта Great Internet Mersenne Prime Search (GIMPS). Два года назад ими же был открыт предыдущий рекордсмен — относительный легковес, содержащий всего около 4 млн цифр.

Новое простое число нашел компьютер 26-летнего Майкла Шафера из Университета штата Мичиган. Эта машина — Dell с 2-ГГц процессором Pentium — всего лишь один из 211 тыс. компьютеров, принадлежащих 60 тыс. добровольцев, участвующих в проекте.

Поиск простых чисел, который концептуально сродни проекту SETI@home по обнаружению сигналов внеземных цивилизаций в радиоволнах, улавливаемых радиотелескопами, это одна из граней целого спектра технологий объединения вычислительных ресурсов.

В проекте GIMPS участвуют слабо связанные машины, которые лишь изредка обращаются к центральному серверу, — такой подход часто называют распределенными вычислениями. Схемы, при которых ресурсы теснее объединяются в общий пул, окрестили сетевыми (grid computing) и коммунальными (utility computing) вычислениями.

Коммунальные вычисления, с которыми связаны крупные проекты IBM, Hewlett-Packard и Sun Microsystems, имеют прямые бизнес-приложения, такие как обеспечение доступа к дополнительной вычислительной мощности в периоды пиковой нагрузки. Распределенными и сетевыми вычислениями интересуется главным образом академическая наука, но они становятся все более полезными и в таких коммерческих приложениях, как фармацевтические исследования.

Инфраструктуру GIMPS предоставила компания Entropia, которая продает ПО распределенных вычислений. Серверы GIMPS собирают результаты работы сети ПК, в совокупности выполняющих 9 трлн операций в секунду.

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

В частности, простые числа Мерсенна, которые ищет GIMPS, названы так в честь французского монаха Марена Мерсенна, родившегося в 1588 году; он исследовал свойства простых чисел определенного типа: 2 в степени p минус 1, где p — обычное простое число.

В найденном числе, о котором объявлено во вторник, p=20 996  011 — это 40-е известное на сегодняшний день число Мерсенна.

Значения самих чисел можно найти на сайте MathWorld компании Wolfram Research. Энтузиасты могут приобрести постеры со всеми простыми числами — а также лупы для их прочтения. 

 Предыдущие публикации:

 В продолжение темы:

Обсуждение и комментарии

	Anti-MS 3 Dec 2003 5:34 PM
сразу видно кто переводил с уроков математики в школе сбегал. не 2 в степени p-1, а (2 в степени p) минус 1
	Cheetah 3 Dec 2003 6:16 PM
Нафига ? ((c) "Агата Кристи")
	Турок 3 Dec 2003 8:17 PM
С простыми числами не все так просто. Лучше бы попробовали опровергнуть ужасно противную гипотезу Гольбаха.
	torvic 4 Dec 2003 1:50 AM
Я не большой спец в дискретной математике, но по крайней мере для шифрования с открытым ключом нужны два простых числа, причем чем больше тем лучше.
	Skull - sibskullmail.ru 4 Dec 2003 9:59 AM
Есть игроманы, которые играются, линуксоиды, которые копаются в своей ОС. А есть и те, которые занимают процессорное время всякой хернёй. Им даже автоматы не дают... :) Присоединяюсь по этому вопросу к своим постоянным оппонентам... :)
	Sandro - sandrobincom.ru 4 Dec 2003 11:13 AM
Cheetah, Вы не из тех, кто считае, что полёты в космос - напрасная трата денег?
	Bosch 4 Dec 2003 12:59 PM
Вам же написали, что самые большие представляют чисто академический интерес. Надеюсь, с тем, что математика - самая важная дисциплина, никто не будет спорить?
	73137 4 Dec 2003 1:22 PM
а еще для ускоренного взлома закрытого ключа неплохо иметь ?*непрерывную* базу простых чисел от 2 до 2^(длина ключа). как можно вычислить ее объем в зависимости от этой длины? так как эти числа встречаются все реже и реже, объем базы должен расти намного медленнее, чем 2^n (зато объем вычислений для пополнения базы - примерно с той же скоростью, но весь прикол, что эти вычисления могут выполняться один раз в распределенном проекте)... далее, наличие такой базы намного ускоряет взлом ключа (сначала из нее отфильтровываются только числа, на которые может делиться исходное число - путем проверки делимости по последнему знаку в 2, 6, 8, 10, 16, ... системах исчисления; запись простых чисел в этих системах ведется тоже один раз при распределенном пополнении базы; после первичного фильтрования оставшуюся массу проверяем по 2, 3, ... последним знакам и т.д., пока не останутся исходные делители). Конечно, схема нуждается в отладке, но главное то, что совместный проект по подготовке базы для взлома ключей сделает подобный алгоритм шифрования если не бесполезным, то намного менее защищенным, чем в случае тупого перебора.
	Kon 4 Dec 2003 4:10 PM
Bosh - (Надеюсь, с тем, что математика - самая важная дисциплина, никто не будет спорить?) Миллионы людей будут спорить! Я тоже считаю, что ерундой занимаются, но возможно сеть больше ни на что пока не способна. Но вот уважаемый 73137 нашел и практическую сторону этого дела. Не все так плохо!
	Bosch 4 Dec 2003 4:55 PM
2 Kon BosCh, с Вашего позволения! =) Из 6 миллиардов людей, конечно, наберутся миллионы спорщиков... =)
	Cheetah 6 Dec 2003 11:46 PM
2 Sandro: не из тех. :-) К тому же, вспоминая старый анекдот, скажу: если хоть один еврей вызовется лететь в космос, значит деньги на развитие космических полетов были потрачены не зря :-)
	Cheetah 7 Dec 2003 11:54 PM
from Anecdotov.net: Российские хакеры взломали бортовой компьютер российского истрибителя СУ-27, теперь у самолёта бесконечное количество ракет. ;)
	miksoft - miksoftmail.ru 8 Dec 2003 6:24 PM
имхо, рано спорить о полезности/бесполезности этого проекта! это всего лишь очередная тренировка задолго до начала соревнований! заодно и поиск задач, пригодных для решения в распределенных вычислениях... 2 Anti-MS: вообще-то операция возведения в степень имеет более высокий приоритет, чем вычитание, так что скобки ставить необязательно!
	Victor - petvichotmail.com 28 Sep 2004 12:39 PM
Выведена формула получения простых чисел http://www.laplas.narod.ru/moiform.htm пункт №4
	vagon 4 Aug 2005 1:08 AM
было ды круто, если бы 60 000 компов и куча учёных из разных стран участвовало во всемирном проекте по поиску самой большой простой цифры. Пусть формулы выводят, программы пишут и тд. А вообще всемирная наука движется по одному единственному принципу, который всегда работает. принцип такой: Пришейте к подушке куриную голову. Пришили? Молодцы. Теперь объясните, зачем вы это сделали.