Гипотеза Била подорожала до 1 миллиона $

[needbmw]

Гипотеза

Если
где — натуральные и , то  имеют общий простой делитель.

То есть если вы подберёте такие числа, чтобы у A, B, C не было общего простого делителя, то заработаете миллион долларов.

http://habrahabr.ru/post/182312/

А ведь неплохая задачка для GPU, почему бы её не "помайнить"?  

[1715655549]

1715655549

[lexxus]

Нужен пул...

[needbmw]

Нужен пул...

Не обязательно, здесь же нет возможности сделать proof-of-work.
Соответственно вместо пула нужна тупо онлайн-таблица кто какую область считает, чтобы не делать дурную работу несколько раз. Нашедший получает все 

[anatolikostis]

радужные таблицы 

[needbmw]

радужные таблицы  

Радужные таблицы здесь совершенно не при чем.
Чтобы был понятен масштаб проблемы, чтобы перебрать все  A, B, C до 100000 и степени до 10 в расчетах используются целые числа до 10⁵⁰, а количество возможных комбинаций A,B и C оценивается в 10¹⁸
(см. статью Beal's Conjecture: A Search for Counterexamples)

Есть программисты на OpenCL готовые попытать счастья в этой рулетке?
Я подумаю как решить подобную задачку на FPGA, проблема в том, что у меня мощных FPGA практически не осталось в наличии, только для разработки пара плат и всё.

[needbmw]

Думаю я смог бы помочь с OpenCL если бы в этом был смысл.

Сделать вклад в мировую науку - не имеет смысла? Или смысл есть только в том, что можно измерить в процентах от PPS? 

[rPman]

Думаю я смог бы помочь с OpenCL если бы в этом был смысл.

Сделать вклад в мировую науку - не имеет смысла? Или смысл есть только в том, что можно измерить в процентах от PPS? 

мировой науке нужны алгоритмы, а не перебор тупой грубой силой.

[needbmw]

мировой науке нужны алгоритмы, а не перебор тупой грубой силой.

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

[SynDigHie]

Думаю, для начала неплохо было бы прикинуть масштаб возможности GPU с масштабом задачи. Если полный проход всех итераций займет миллион лет - целесообразнее подождать квантовых компьютеров
Если одна итерация SHA256(SHA256) требует приблизительно 12 KFLOP, сколько потребует итерация гипотезы Била?

[HappyS]

Да и вообще надо учитывать сначала что теорема эта может быть верна и числа не подобрать нужные.

[needbmw]

Да и вообще надо учитывать сначала что теорема эта может быть верна и числа не подобрать нужные.

Там вообще все интересно получается: если гипотеза Била верна, то она является однозначным доказательством Великой теоремы Ферма (от противного). Великая теорема Ферма доказана в 1995 г. Эндрю Уайлсом, НО это отнюдь не означает что гипотеза Била верна. Но скорее всего гипотеза верна, никто же не доказал еще обратного 

По ресурсоемкости "брут-форса" однозначно ответить сложно, надо подумать и посчитать как следует. Ну во-первых, перебор не закончится никогда, т.к. множество натуральных чисел бесконечно. Во вторых, возможны же разные подходы: считать "в лоб", считать по таблицам (вот тут могут реально пригодиться гигабайты видеопамяти), соответственно и скорость "брут-форса" разная получится. Короче, простор для оптимизации казалось бы простой формулы A^x + B^y = C^z
 
Википедия утверждает что гипотеза Била просчитана сейчас только для всех A,B,C,x,y,z < 1000, так что еще есть куда стремиться 

[HappyS]

У меня брат математик в интеле работает я его спросил - он сказал что херня это все, не хватит мощностей.

Это я к тому что я нихера не шарю, а кто шарит думают что это бессмысленно.

[alexxy]

Эта гипотеза скорее всего верна, так что перебор тут видимо бессмысленное занятие. К тому же на ней строится довольно много алгоритмов криптографии