LINUX.ORG.RU

Дискретное логарифмирование по модулю 530-битного простого числа


0

0

Немецкие ученые успешно решили проблему дискретного логарифмирования по модулю 530-битного (160 десятичных знаков) простого числа p. Предполагаемая сложность вычисления дискретных логарифмов лежит в основе многих криптографических алгоритмов, например, протокола Диффи-Хелмана для выработки общего секрета (ключа). Таким образом, представленный результат позволяет лучше оценить криптографическую стойкость и безопасные параметры для таких алгоритмов.

Из соображений беспристрастности простое число p было выбрано из последовательных цифр числа "пи" так, чтобы оно также удовлетворяло стандартным криптографическим требованиям, усложняющим дискретное логарифмирование. Для вычисления дискретного логарифма был использован алгоритм Общего Решета Числового Поля (General Number Field Sieve, GNFS), который является на данный момент лучшим из известных (как впрочем, и для задачи факторизации больших чисел). Вычисления производились на множестве компьютеров в Институте Численного Моделирования и в Математическом Институте университета Бонна, в том числе и на кластере Himalaya (128 x dual-Xeon EM64T) под управлением Ubuntu 6.06 LTS с ядром 2.6.15 (64 bit). Кластер параллельно выполнял до 8 задач, каждая из которых использовала от 12 до 24 процессоров. На одиночном 3.2 GHz Xeon64 PC этот же объем работ потребовал бы около 17 лет.

Про кластер Himalaya: http://wissrech.iam.uni-bonn.de/resea...

>>> Подробности

anonymous

Проверено: Pi ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> под управлением Ubuntu 6.06 LTS Хренасе! =)

pento ★★★★★ ()

Сенсация.

Сенсация, Linux использован в качестве операционной системы на очередной числодробилке.

Camel ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

вот бы на таком кластере в Doom'а погонять (шутка) ;-)

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

На таком кластере наверное можно риалтайм рейтрейс рендеринг делать...

Mikail ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>На таком кластере наверное можно риалтайм рейтрейс рендеринг делать...

Нельзя. Слабоват. Максимум будет обсчитывать 1 кадр в секунду а надо в 25-30 раз быстрее.

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>Нельзя. Слабоват. Максимум будет обсчитывать 1 кадр в секунду а надо в 25-30 раз быстрее.

не надо людей в заблуждение вводить %) реал рейтрейс уже реален (каламбур %) на обычных машинах, все зависит от сложности сцены и разрешения ессно. Ну конечно если сцена сложная и качество кинематографическое - то одна машинка ни асилит, но у нас вот тут дизайнеры backburner server понаставили на машинки офисные простаивающие (начиная от двухкорых кончая обычными соплеронами 2.4, а меньше ща и не купишь %-( и собрали "кластер" (бугага), ролики считаются вполне шустро %)

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>А что Слака или Гента будет лучше?

В данном случае это глубоко параллельно.

Хотя есть именно "кластероориентированные" дистрибутивы: Rocks, ClusterKnoppix, ParallelKnoppix, PlumpOS, MandrakeClustering, кластерная версия SLES ну и наверное RHAS. Хотя "кластерного" там наверное больше в названии (просто в поставке уже идут нужные библиотеки для HPC и в некоторых случаях модифицированные ядра). С таким же успехом на кластерах работают и другие дистрибутивы + обвязка + модифицировынные ядра. Котструктор он и есть конструктор.

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>не надо людей в заблуждение вводить %) реал рейтрейс уже реален (каламбур %) на обычных машинах, все зависит от сложности сцены и разрешения ессно. Ну конечно если сцена сложная и качество кинематографическое - то одна машинка ни асилит, но у нас вот тут дизайнеры backburner server понаставили на машинки офисные простаивающие (начиная от двухкорых кончая обычными соплеронами 2.4, а меньше ща и не купишь %-( и собрали "кластер" (бугага), ролики считаются вполне шустро %)

Ага. если имеется ввиду изображение размером с почтовую марку то может быть ;)

ЗЫ: Ознакомтесь с циферками по скорости -> http://www.tabsnet.com/index.php?option=com_benchmark&task=list&bid=1...

на сценке далеко не кинематографического качества.

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

Читал мало, понял ещё меньше, но сдаётся мне, что длина пароля в средненьких требованиях безопасности теперь ещё на порядок вырастет

router ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> ЗЫ: Ознакомтесь с циферками по скорости ->

>http://www.tabsnet.com/index.php?option=com_benchmark&task=list&bid=1...

> на сценке далеко не кинематографического качества.

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

Насценых по сложности как Q1, и разрешении типа 640х480 - такой кластер будет вполне быстро рисовать.

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>ЗЫ: Ознакомтесь с циферками по скорости

А шо мне ознакамливаться, есть как бы какие то ознакомилки, а есть реальная работа, которую несут между прочим на центральные каналы ТВ %)

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> реальная работа ... на центральные каналы ТВ
гы - сразу вспоминается Generation П;)

mumpster ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>Насценых по сложности как Q1, и разрешении типа 640х480 - такой кластер будет вполне быстро рисовать.

конечно это глубокий оффтоп уже все. Но еще раз повторюсь - дело же далеко не в разрешении только, еще очень важны такие вещи как сложность сцены, глубина рейтресинга, количество объектов переотражения и т.п. Далеко не всегда нужно все "на максимум" включать, ибо смысл в этом редко проявляется.

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> но сдаётся мне, что длина пароля в средненьких требованиях безопасности теперь ещё на порядок вырастет

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

isden ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

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

Это стандартный старый (chessmark) bench из PovRay.

Там есть еще новый (NewMark), который рассчитывается примерно на порядок дольше.

> Насценых по сложности как Q1, и разрешении типа 640х480 - такой кластер будет вполне быстро рисовать.

640x480 это ни разу не кинематографическое качество как и Q1

Данный (chessmark) бенч если мне склероз не изменяет 800x600

У меня на старом кластере в 4x-узловой конфигурации (другие не пробовал) он считается 54-56 сек. На новом пока тоже не гонял.

PS: Про полигоны не понял ;) Вы что такое Ray tracing представляете ?

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>А шо мне ознакамливаться, есть как бы какие то ознакомилки, а есть реальная работа, которую несут между прочим на центральные каналы ТВ %)

Вы таки определитесь об чем спич. О том что кто-то куда то несёт или о RT RayTracing с кинематографическим качеством. Иначе никто бы не городил Render Farm от сотен до тысяч узлов, которые загружены 7/24.

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

На держи на потренироваться http://en.wikipedia.org/wiki/Image:Glasses_800_edit.png исходник для povray3.6 там вроде приложен.

Потом доложишь результат в плане скорости ;)

Это правда уже не кинематографическое качество а фотореалистичное ;)

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

Требования к безопасности повышаются.. :-)

MiracleMan ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

классно :)

только при очень внимательном рассмотрении замечаются отличия от реальности (кубики подкачали).

а так рулез, неотличимо :)

gr_buza ★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

Непонятно за какое время они решили задачу на своем кластере?

(Понятно итак что на одном Xeon-е это займет до 17 лет)

necromant ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

Можно прикинуть. Пусть было 8 задач, каждая на 18 процессорах в среднем, то есть всего было задействовано 144 процов. Поэтому времени им понадобилось примерно 17/144 лет, то есть примерно полтора месяца.

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>> реальная работа ... на центральные каналы ТВ
> гы - сразу вспоминается Generation П;)
ага, у меня такая же реакция. :^)

Spherix ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>Вы таки определитесь об чем спич. О том что кто-то куда то несёт или о RT RayTracing с кинематографическим качеством.

речь о сложности сцены %) Просто сам по себе RT RayTracing ни о чем не говорит, надо применять его к сцене, и уже тогда говорить что "вот на этой сцене надо такой то кластер что бы посчитать ее риалтайм". Вот о чем я. Картинка зач0тная, кстати. зы, очень здорово ускорило бы юзанье хардварных мощностей GPU, если написать рендер с использованием хотя бы даж готовых либов (есть же такие, считать на GPU математику). Сразу вспоминается компьютер от SGI с 512 firegl и 2итаниумами, типа станцию визуализации они делали такую, подробности правда забыл... Вот такая перделка была бы уже пошустрее, чем насиловать бедный x86.

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

Рейтрейсинг-рейтрейсинг.... Какой нафик рейтрейсинг??? На таком кластере надо мозиллу и опенофис компилить!!!!

Orlangoor ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>речь о сложности сцены %) Просто сам по себе RT RayTracing ни о чем не говорит, надо применять его к сцене, и уже тогда говорить что "вот на этой сцене надо такой то кластер что бы посчитать ее риалтайм". Вот о чем я

Я про тоже.

>чень здорово ускорило бы юзанье хардварных мощностей GPU, если написать рендер с использованием хотя бы даж готовых либов (есть же такие, считать на GPU математику).

Есть но пока в качестве эксперимента http://www.gpgpu.org/

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>На таком кластере надо мозиллу и опенофис компилить!!!!

а с -j 256 оно соберётся ? ;)

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

на gpgpu нашел забавный документ - http://www.gpgpu.org/sc2006/workshop/presentations/Paolini_IBM_Cell.pdf Хотя наверное баян ужо %) Но радует местами, особенно теми где как раз рассматриваются вопросы рендеринга и рейтрейс

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> Это правда уже не кинематографическое качество а фотореалистичное ;)

Ренедарить пол-дня вместо того чтобы взять и снять? Кстати, на размытие, даваемое объективом - все равно непохоже. Хотя конечно лучше ужастной картинки трехмерных мыльтиков....

sv75 ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>Ренедарить пол-дня вместо того чтобы взять и снять?

К сожалению (а для кого-то и к счастью %)) не все можно снять %-) Да и по деньгам иногда дешевле (и быстрее) отрисовать/замоделить/рендер, чем снимать это (даже если это физически возможно)

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

где новость? насколько я знаю, уже год, как разложили на множители 790битное число.

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>Ренедарить пол-дня вместо того чтобы взять и снять?

Как предлагается снимать вещи которых нет в природе ? ;)

>Кстати, на размытие, даваемое объективом - все равно непохож

У вас просто объектив другой ;)

ЗЫ: Лично у меня претензии только к качеству пива ;) (нет ни пены ни пузырьков) да и тёплое оно ;) Можно было -бы поработать над конденсатом на стеклянных поверхностях (это не особо сложно если учесть физику - размер микрокапель в зависимости от теплового состояния объекта в различных местах) но это уже не совсем raytracing ;)

PPS: В перельнице не хватает горы бычков ;)

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> PS: Про полигоны не понял ;) Вы что такое Ray tracing представляете ?

Гм. На чисто обывательском уровне. А чем там данные задаются? Сегментами поверхностей N-ного порядка (типа кривых Безье - не знаю, как оно назвается в 3D)?

Не вижу, кстати, что мешает трассировать полигональные сцены (ну, кроме буссмысленности процесса).

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>> Вы что такое Ray tracing представляете ?

> Гм. На чисто обывательском уровне.

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

baka-kun ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>> Ренедарить пол-дня вместо того чтобы взять и снять?

> Как предлагается снимать вещи которых нет в природе ? ;)

А причем тут натюрморт с пивом?

>> Кстати, на размытие, даваемое объективом - все равно непохож

> У вас просто объектив другой ;)

Есть формальный тест - нужна сцена с точечным источником света (например бликами) в нерезкости. Оптика дает кружочки, типа таких:

http://sevik.ru/photos/vnuki/08_IMG_7944.jpg

sv75 ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>> а с -j 256 оно соберётся ? ;)

> А почему может не собраться ? Не понял что-то юмора...

Юмор в том, что есть много пакетов, которые не собираются в параллельном режиме. Причём зачастую это действительно большие пакеты. OpenOffice.org, например.

const86 ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

>> Ренедарить пол-дня вместо того чтобы взять и снять? >> Как предлагается снимать вещи которых нет в природе ? ;) > А причем тут натюрморт с пивом?

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

sS ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> Есть формальный тест - нужна сцена с точечным источником света (например бликами) в нерезкости. Оптика дает кружочки, типа таких: http://sevik.ru/photos/vnuki/08_IMG_7944.jpg

А че у нее во рту?

anonymous ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

> А че у нее во рту?

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

sv75 ★★★★★ ()

Re: Дискретное логарифмирование по модулю 530-битного простого числа

Убойная тема, учитывая дебилизацию ЛОРа. лол

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.