Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: [1] 2 3 4 вперед Ctrl→ все |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Ещё раз взглянул на сообщение 21976045 и подумал, а почему бы не создать отдельный топик по решению сверх-задачи, которую поставил mayton. Попробую эту сверх-задачу ещё раз сформулировать:
Ясно, что на своих ПК мы не сможем (пока) «искать простоту» вблизи таких больших чисел. Остаётся отрабатывать наши действия на меньших числах, и, если получится, распространить эти действия на большие числа (это ещё называется построением эвристического алгоритма). |
||
22 сен 19, 07:56 [21976145] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Можно искать следующее простое число за - искать следующее простое число Мерсенна; - искать следующее простое число, следующее за этим число Мерсенна. Если для первого варианта есть тест Люка-Лемера, то для второго варианта теста простоты пока нет Конечно, тесты простоты есть. Но с учётом того, что по этим тестам простоты нужно провести очень большое количество раундов, связанных с возведением в большую степень (в тесте Люка-Лемера только возведение в квадрат), то времени на поиск очередного простого числа потребуется во много раз больше, чем для теста Люка-Лемера. Остаётся найти другой тест для поиска простых чисел в окрестности чисел Мерсенна, по скорости сравнимого с тестом Люка-Лемера. |
22 сен 19, 15:46 [21976247] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Нам следует оставить бесполезные Попытки просто искать числа. В районе сверхбольших. Вычислительная сложность такова что наших машин не хватит. Давай откатывать гипотезы на малых числах которые хотя бы быстро вычислимы. |
22 сен 19, 17:12 [21976271] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
и если гипотеза работает, то, согласно эвристике, можно гипотезу в виде алгоритма распространить на большие числа. |
||
22 сен 19, 17:44 [21976286] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Немного о тесте Люка-Лемера. Как известно, числа Мерсенна получили известность благодаря тесту простоты Люка-Лемера. Однако тест Люка-Лемера может проверять только числа из последовательности Мерсенна. Другие большие числа этот тест не рассматривает. Все остальные известные тесты простоты не могут в разумное время определить простоту больших чисел, поскольку такие тесты включают в себя объём вычислений, намного больший, чем объём вычислений теста Люка-Лемера. При определении простоты числа последовательность чисел из (n – 2) остатков по модулю квадратов чисел, меньших n. После того, как последовательность сформирована, оценивается последний элемент последовательности. Если последний элемент равен числу 0, тогда число Mn простое. Если последний элемент не равен числу 0, тогда число Mn составное. В тесте Люка-Лемера не применяется формула Ферма, в отличие от большинства тестов простоты. Это является преимуществом теста по быстроте. Поэтому, если разрабатывать новый алгоритм, то его быстродействие должно сравниться с быстродействием теста Люка-Лемера. |
23 сен 19, 10:33 [21976558] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
В эвристическом алгоритме для числа n одним из основных элементов является число d. Появляется соблазн "сформировать" очень большие числа следующим образом. Выбирается очень большое число 2^m, и уже для этого числа «подбирается» число d. Таким образом, получается число 2^m * d + 1 Такие числа уже рассматривались. Они называются числами Прота. https://ru.wikipedia.org/wiki/Число_Прота Для проверки таких чисел на простоту существует теорема Прота https://ru.wikipedia.org/wiki/Теорема_Прота Данная теорема Прота является вероятностным тестом простоты. Самым большим известным простым числом Прота является число 10223*2^31172165 + 1 , которое является крупнейшим известным простым числом, не являющимся числом Мерсенна. Были проверены числа Прота на небольших числах m. Можно для каждого значения m определить минимальное значение d. |
24 сен 19, 13:33 [21977873] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Появилась ещё одна статья. http://sci-article.ru/stat.php?i=1569407195 Если коротко, то получен эвристический алгоритм для определения простых чисел Мерсенна Mn. Составлена на Python программа с применением эвристического алгоритма по определению простых чисел Мерсенна. Время работы такой программы сопоставимо со временем работы программы теста Люка-Лемера. Получается, что время определения (n – 2) квадратов чисел, меньших Mn, в виде остатков по модулю Mn почти равно времени определения остатка по модулю Mn для числа a^((Mn – 1)/2) В статье рассмотрено число a = 3. Показаны возможности других оснований степени. В отличие от теста Люка-Лемера данный эвристический алгоритм определяет простые числа Mnk = 2^n - 1 + 4*k, где k - натуральное число. Программа на Python подтвердила эти расчёты для n < 60 и для шагов 1 <= k <= 25. |
26 сен 19, 16:20 [21980061] Ответить | Цитировать Сообщить модератору |
Aklin Member Откуда: Прямо сейчас меня здесь нет Сообщений: 61163 |
Gennadiy Usov, продолжайте наблюдения. |
26 сен 19, 18:39 [21980221] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
1. Получен эвристический алгоритм определения всех простых чисел (проверено на диапазоне от 5 до 250 000 000) (новизна). 2. Получена последовательность простых чисел, состоящая из 50% всех простых чисел. При этом для каждого проверяемого числа достаточно 3-х раундов вычислений (новизна). 3. Получен эвристический алгоритм определения простых чисел Мерсенна, сопоставимый по времени работы с тестом Люка-Лемера. 4. Данный эвристический алгоритм можно применять для определения простых чисел в окрестности чисел Мерсенна (новизна). |
||
27 сен 19, 15:04 [21980972] Ответить | Цитировать Сообщить модератору |
fkthat Member Откуда: Сообщений: 4371 |
250 лямов это даже до 32 бит не дотягивает. Ты вот сгенери простое число битов так хотя бы на 256. ![]() |
||
6 окт 19, 22:39 [21987821] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Мы уже генерили до 2048 + хвостик. С использованием OpenJDK и господин математик с помощью магии Питона и своих эвристик. |
6 окт 19, 22:57 [21987835] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Первые 22 штуки в диапазоне 4096 бит. 2^4096 + 1 + 1760 2^4096 + 1 + 7226 2^4096 + 1 + 7422 2^4096 + 1 + 10092 2^4096 + 1 + 10472 2^4096 + 1 + 13964 2^4096 + 1 + 17334 2^4096 + 1 + 17354 2^4096 + 1 + 19890 2^4096 + 1 + 22802 2^4096 + 1 + 27014 2^4096 + 1 + 28346 2^4096 + 1 + 28652 2^4096 + 1 + 29634 2^4096 + 1 + 34512 2^4096 + 1 + 34956 2^4096 + 1 + 35294 2^4096 + 1 + 40160 2^4096 + 1 + 41280 2^4096 + 1 + 42590 2^4096 + 1 + 43344 2^4096 + 1 + 49562 |
|||||||||||||||||||||||||||||||||||||||||||
7 окт 19, 00:07 [21987855] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
|
|||||||||||||||||||||||||||||||||||||||||||||
7 окт 19, 06:28 [21987882] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Gennadiy Usov, Это ответ господину fkthat. |
7 окт 19, 07:43 [21987895] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Не стал много считать на своём стареньком ПК, поэтому только один час: 2019-10-07-09.53.54 -простое- 1760 -s- 5 -простое- 7226 -s- 1 -простое- 7422 -s- 1 -простое- 10092 -s- 2 -простое- 10472 -s- 3 -проверка чисел от - 2^4096 + 1 -дистанция - 11000 -количество простых чисел- 5 -количество раундов - 5687 -минимальное количество раундов для числа - 1 -количество минимальных раундов - 5495 -максимальное количество раундов для числа - 38 -количество максимальных раундов - 190 -остаток- 2 2019-10-07-10.54.48 Программа практически сразу определяет составное число. |
7 окт 19, 12:44 [21988109] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Уж лучше 500, 1500, 2500,... В работе http://sci-article.ru/stat.php?i=1569407195 показаны последовательности простых чисел, в которых есть следующие простые числа: 2^2370 - 1 + 4 2^2648 - 1 + 8 2^1661 - 1 + 12 2^2772 - 1 + 16 2^2810 - 1 + 20 |
||||
7 окт 19, 12:55 [21988126] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Тут появилась одна задачка: Пусть имеется выражение: a mod(b) Если в данном случае b = c + d, то как можно представить первоначальное выражение через mod(b) и mod(c), или через их комбинацию? |
11 окт 19, 12:56 [21992073] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Исправляю предыдущее сообщение: то как можно представить первоначальное выражение через mod(d) и mod(c), или через их комбинацию? |
11 окт 19, 12:57 [21992075] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Если b = c + d, то мы можем взять модуль с обоих сторон b (mod x) = c + d (mod x) |
11 окт 19, 13:42 [21992124] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Или ты имел в виду дистрибутивность операции mod? |
11 окт 19, 13:43 [21992125] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
Может быть можно получить функцию вида x mod(c) +- y mod(d) +- (что-то), или другие опперации? |
||
11 окт 19, 14:47 [21992198] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Для умножения что-то подобное было. Или для возведения в степень. Я думаю если Барлон заскочет в топик - то он прояснит. Вроде скилованный парень в этих кольцах и модулях. |
11 окт 19, 15:20 [21992254] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
|
||
11 окт 19, 16:40 [21992377] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2357 |
|
||||
11 окт 19, 16:54 [21992393] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51153 |
Можно нарисовать табличку Пифагора для сложения. Я думаю что закономерность будет. |
11 окт 19, 16:56 [21992398] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: [1] 2 3 4 вперед Ctrl→ все |
Все форумы / Программирование | ![]() |