Author

Topic: Гипотеза Била подорожала до 1 миллиона $ (Read 1871 times)

sr. member
Activity: 363
Merit: 250
Эта гипотеза скорее всего верна, так что перебор тут видимо бессмысленное занятие. К тому же на ней строится довольно много алгоритмов криптографии
legendary
Activity: 1568
Merit: 1008
У меня брат математик в интеле работает я его спросил - он сказал что херня это все, не хватит мощностей.

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

По ресурсоемкости "брут-форса" однозначно ответить сложно, надо подумать и посчитать как следует. Ну во-первых, перебор не закончится никогда, т.к. множество натуральных чисел бесконечно. Во вторых, возможны же разные подходы: считать "в лоб", считать по таблицам (вот тут могут реально пригодиться гигабайты видеопамяти), соответственно и скорость "брут-форса" разная получится. Короче, простор для оптимизации казалось бы простой формулы Ax + By = Cz
 
Википедия утверждает что гипотеза Била просчитана сейчас только для всех A,B,C,x,y,z < 1000, так что еще есть куда стремиться  Grin
legendary
Activity: 1568
Merit: 1008
Да и вообще надо учитывать сначала что теорема эта может быть верна и числа не подобрать нужные.
newbie
Activity: 22
Merit: 0
Думаю, для начала неплохо было бы прикинуть масштаб возможности GPU с масштабом задачи. Если полный проход всех итераций займет миллион лет - целесообразнее подождать квантовых компьютеров Smiley
Если одна итерация SHA256(SHA256) требует приблизительно 12 KFLOP, сколько потребует итерация гипотезы Била?
legendary
Activity: 1302
Merit: 1008
мировой науке нужны алгоритмы, а не перебор тупой грубой силой.
Условия задачи поставлены ясно - доказать гипотезу или найти контрпример (неважно каким образом, хоть на калькуляторе).
Второе полностью снимет необходимость доказывать гипотезу, что тоже является немалым вкладом, поэтому указанная в теме сумма присуждается за любой из данных результатов.
legendary
Activity: 1120
Merit: 1069
Думаю я смог бы помочь с OpenCL если бы в этом был смысл.
Сделать вклад в мировую науку - не имеет смысла? Или смысл есть только в том, что можно измерить в процентах от PPS?  Huh
мировой науке нужны алгоритмы, а не перебор тупой грубой силой.
legendary
Activity: 1302
Merit: 1008
Думаю я смог бы помочь с OpenCL если бы в этом был смысл.
Сделать вклад в мировую науку - не имеет смысла? Или смысл есть только в том, что можно измерить в процентах от PPS?  Huh
legendary
Activity: 1302
Merit: 1008
радужные таблицы  Grin
Радужные таблицы здесь совершенно не при чем.
Чтобы был понятен масштаб проблемы, чтобы перебрать все  A, B, C до 100000 и степени до 10 в расчетах используются целые числа до 1050, а количество возможных комбинаций A,B и C оценивается в 1018
(см. статью Beal's Conjecture: A Search for Counterexamples)

Есть программисты на OpenCL готовые попытать счастья в этой рулетке?
Я подумаю как решить подобную задачку на FPGA, проблема в том, что у меня мощных FPGA практически не осталось в наличии, только для разработки пара плат и всё.
legendary
Activity: 2026
Merit: 1005
радужные таблицы  Grin
legendary
Activity: 1302
Merit: 1008
Нужен пул... Cheesy
Не обязательно, здесь же нет возможности сделать proof-of-work.
Соответственно вместо пула нужна тупо онлайн-таблица кто какую область считает, чтобы не делать дурную работу несколько раз. Нашедший получает все  Grin
sr. member
Activity: 309
Merit: 250
legendary
Activity: 1302
Merit: 1008
Гипотеза

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


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

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

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