Открыл делитель числа Ферма F299 !

[Alexey Komkov]

Вчера нашел делитель числа Ферма F299 ( $2^{2^{299}}+1$ ) .
Вот он : ${272392805475}*2^{304}+1$

[venco]

Поздравляю!
На http://www.fermatsearch.org/ сообщили?

[moscwicz]

странный вид спорта

[ИСН]

всяко менее странный, чем пинать круглый предмет по полю

[Руст]

Мне интересен только алгоритм поиска. Найден путем перебора множителя $m$ в выражении
$p=m2^{301}+1$ и начиная с 2 возводит в квадрат в 299 раз. Или есть более разумный не переборный по всем возможным $m$ алгоритм нахождения этого множителя?

[Alexey Komkov]

venco
Спасибо! В fermatsearch.org уже сообщил.

Руст
Да, алгоритм такой, только степень 304(у Вас наверное опечатка).

[Руст]

Alexey Komkov в сообщении #377883 писал(а):

venco
Спасибо! В fermatsearch.org уже сообщил.

Руст
Да, алгоритм такой, только степень 304(у Вас наверное опечатка).

Мы знаем только о 301, получилось что $m$ еще делится на 8, которую вы внесли в степень потом.
Вы же заранее не знали, что он дополнительно делится на 8.
При этом проверять на простоту числа $p=m*2^{301}+1$ бессмысленно, так как быстрее 299 раз возводит в квадрат по модулю p. Это на мой взгляд не оптимальный алгоритм. Сколько дней ушло на нахождение делителя?
У меня есть некоторые соображения как уменьшить перебор, но нет особого интереса заниматься этим.

[Alexey Komkov]

На нахождение ушло пол года, при загрузке 30 машин P4. Небыло задачи найти делитель именно F299. Фиксировалась степень двойки, а потом перебирались нечетные m. Предварительно часть составных делителей отсеивалась решетом.

[Руст]

Спасибо, теперь понятно, что вы искали делитель числа $F_n, n\le 302$. Заодно объединяя (не повторяясь) в вычислениях квадратов по этому модулю для меньших $n$. Естественно так же по решету предварительно отсеять числа $p=m*2^{304}+1$ проверяя делимость примерно до 10 000 000. Это число можно уточнять в зависимости от типа умножения. При выборы показателя 304, быстрое умножение с преобразованием Фурье еще уступает простому табличному умножению по скорости. У меня получалось, что оно выгоднее после 2000-3000 битов. Возможно числа такого порядка выгоднее всего умножать по Карацуба. Доказывать простоту выбранного р все равно бесполезно.
Еще вопрос, почему выбрали показатель 304? Насколько я знаю, еще не найдены делители многих чисел Ферма из первой сотни.

[Alexey Komkov]

Все верно, так и искал, только преимущество Фурье начинается примерно с чуть более 1000 бит. Был выбран диапазон 300 - 345, в первой сотне искать делитель почти бесполезно, там уже перебрали порядка $2^{48}$ чисел m, а для некоторых степеней намного больше.

[drug39]

Просто интерено. Как вы считаете, стали бы люди столько заниматься поисками делителей чисел Ферма, если бы точно знали, что количество простых чисел Ферма бесконечно?

[Руст]

Искали бы с еще большим усердием. Это дает кандидат $n\ge 33$ на простое число, для которого не докажешь не опровергнешь простоту компьютером и возможно ничем(вряд ли для них найдут другой способ устанавливать это).

[drug39]

Руст в сообщении #393028 писал(а):

Искали бы с еще большим усердием...

Чесно говоря, не понял. Я думал, что интерес подогревается мыслью, что вдруг будет найдено последнее простое число Ферма...

[ИСН]

Дак на нём не написано, что оно последнее, если и так.
Вообще, при поиске чего-то большого вариантов масса:
- их точно бесконечно много (как простых чисел вообще);
- их скорее всего бесконечно много, но это открытый вопрос (как чисел Мерсенна);
- их скорее всего конечное число, но это открытый вопрос (как чисел Ферма);
- их скорее всего нет вообще, но это открытый вопрос (как нечётных совершенных);
- их точно конечное число или нет вообще, но до границы пилить ещё немеряно (исключения из Гольдбаха-3)
- их точно конечное число или нет вообще, и граница достижима (Seventeen or bust).
И знаете, всем этим кто-нибудь да занимается.

[Gortaur]

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