Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl→      все
 Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
 		Ещё раз взглянул на сообщение 21976045 и подумал,
а почему бы не создать отдельный топик по решению сверх-задачи, которую поставил mayton.

Попробую эту сверх-задачу ещё раз сформулировать:
mayton
Давайте поставлю сверх-задачу.

Пускай задана максимально-известная prime-константа Мерсенна (Хи-мерсенна).


На каком расстоянии от Хи-Мерсенна находится следующее простое число?

Ясно, что на своих ПК мы не сможем (пока) «искать простоту» вблизи таких больших чисел.

Остаётся отрабатывать наши действия на меньших числах,
и, если получится, распространить эти действия на большие числа
(это ещё называется построением эвристического алгоритма).
22 сен 19, 07:56    [21976145]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
 		Можно искать следующее простое число за , двумя способами:
- искать следующее простое число Мерсенна;
- искать следующее простое число, следующее за этим число Мерсенна.
Если для первого варианта есть тест Люка-Лемера, то для второго варианта теста простоты пока нет

Конечно, тесты простоты есть. Но с учётом того, что по этим тестам простоты нужно провести очень большое количество раундов, связанных с возведением в большую степень (в тесте Люка-Лемера только возведение в квадрат), то времени на поиск очередного простого числа потребуется во много раз больше, чем для теста Люка-Лемера.

Остаётся найти другой тест для поиска простых чисел в окрестности чисел Мерсенна, по скорости сравнимого с тестом Люка-Лемера.
22 сен 19, 15:46    [21976247]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
 		Нам следует оставить бесполезные Попытки просто искать числа. В районе сверхбольших. Вычислительная сложность такова что наших машин не хватит.

Давай откатывать гипотезы на малых числах которые хотя бы быстро вычислимы.
22 сен 19, 17:12    [21976271]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
mayton
Нам следует оставить бесполезные Попытки просто искать числа. В районе сверхбольших.
Вычислительная сложность такова что наших машин не хватит.
Давай откатывать гипотезы на малых числах которые хотя бы быстро вычислимы.
Конечно, сначала проверка гипотез будет на малых числах,
и если гипотеза работает,
то, согласно эвристике, можно гипотезу в виде алгоритма распространить на большие числа.
22 сен 19, 17:44    [21976286]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
 		Немного о тесте Люка-Лемера.
Как известно, числа Мерсенна получили известность благодаря тесту простоты Люка-Лемера.
Однако тест Люка-Лемера может проверять только числа из последовательности Мерсенна.
Другие большие числа этот тест не рассматривает.
Все остальные известные тесты простоты не могут в разумное время определить простоту больших чисел,
поскольку такие тесты включают в себя объём вычислений, намного больший, чем объём вычислений теста Люка-Лемера.

При определении простоты числа тест простоты Люка-Лемера формирует
последовательность чисел из (n – 2) остатков по модулю квадратов чисел, меньших n.
После того, как последовательность сформирована, оценивается последний элемент последовательности.
Если последний элемент равен числу 0, тогда число Mn простое.
Если последний элемент не равен числу 0, тогда число Mn составное.
В тесте Люка-Лемера не применяется формула Ферма, в отличие от большинства тестов простоты.
Это является преимуществом теста по быстроте.

Поэтому, если разрабатывать новый алгоритм,
то его быстродействие должно сравниться с быстродействием теста Люка-Лемера.
23 сен 19, 10:33    [21976558]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
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]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
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]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 61163
 		Gennadiy Usov,

продолжайте наблюдения.
26 сен 19, 18:39    [21980221]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
Aklin
Gennadiy Usov,
продолжайте наблюдения.
Дальнейшие наблюдения уже почти не нужны.

1. Получен эвристический алгоритм определения всех простых чисел (проверено на диапазоне от 5 до 250 000 000) (новизна).

2. Получена последовательность простых чисел, состоящая из 50% всех простых чисел. При этом для каждого проверяемого числа достаточно 3-х раундов вычислений (новизна).

3. Получен эвристический алгоритм определения простых чисел Мерсенна, сопоставимый по времени работы с тестом Люка-Лемера.

4. Данный эвристический алгоритм можно применять для определения простых чисел в окрестности чисел Мерсенна (новизна).
27 сен 19, 15:04    [21980972]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
fkthat
Member

Откуда:
Сообщений: 4371
Gennadiy Usov
проверено на диапазоне от 5 до 250 000 000


250 лямов это даже до 32 бит не дотягивает. Ты вот сгенери простое число битов так хотя бы на 256.
6 окт 19, 22:39    [21987821]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
 		Мы уже генерили до 2048 + хвостик. С использованием OpenJDK и господин математик
с помощью магии Питона и своих эвристик.
6 окт 19, 22:57    [21987835]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
Range Primes Found(Usoff) Primes Found(JDK::BigInteger) Primes (theoretical) Elapsed time(s) Average Speed (primes/sec)
2 - 1002400
2^200 + 1 - 2^200 + 1 + 1 000 000713461189
2^500 + 1 - 2^500 + 1 + 200 0005762288
2^1024 + 1 - 2^1024 + 1 + 200 000281835
2^2048 + 1 - 2^2048 + 1 + 100 00078272
2^4096 + 1 - 2^4096 + 1 + 50 00022950


Первые 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]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
mayton
Range Primes Found(Usoff) Primes Found(JDK::BigInteger) Primes (theoretical) Elapsed time(s) Average Speed (primes/sec)
2 - 1002400
2^200 + 1 - 2^200 + 1 + 1 000 000713461189
2^500 + 1 - 2^500 + 1 + 200 0005762288
2^1024 + 1 - 2^1024 + 1 + 200 000281835
2^2048 + 1 - 2^2048 + 1 + 100 00078272
2^4096 + 1 - 2^4096 + 1 + 50 00022950
И что даёт таблица?
7 окт 19, 06:28    [21987882]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
 		Gennadiy Usov,

Это ответ господину fkthat.
7 окт 19, 07:43    [21987895]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
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]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
fkthat
Gennadiy Usov
проверено на диапазоне от 5 до 250 000 000
250 лямов это даже до 32 бит не дотягивает. Ты вот сгенери простое число битов так хотя бы на 256.
А зачем так мало? 256?

Уж лучше 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]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
 		Тут появилась одна задачка:

Пусть имеется выражение:

a mod(b)

Если в данном случае b = c + d,

то как можно представить первоначальное выражение через mod(b) и mod(c),
или через их комбинацию?
11 окт 19, 12:56    [21992073]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
 		Исправляю предыдущее сообщение:

то как можно представить первоначальное выражение через mod(d) и mod(c),
или через их комбинацию?
11 окт 19, 12:57    [21992075]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
 		Если b = c + d, то мы можем взять модуль с обоих сторон

b (mod x) = c + d (mod x)
11 окт 19, 13:42    [21992124]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
 		Или ты имел в виду дистрибутивность операции mod?
11 окт 19, 13:43    [21992125]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
mayton
Или ты имел в виду дистрибутивность операции mod?
Да.

Может быть можно получить функцию вида

x mod(c) +- y mod(d) +- (что-то),

или другие опперации?
11 окт 19, 14:47    [21992198]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
 		Для умножения что-то подобное было. Или для возведения в степень. Я думаю если Барлон заскочет
в топик - то он прояснит. Вроде скилованный парень в этих кольцах и модулях.
11 окт 19, 15:20    [21992254]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1451
mayton
Для умножения что-то подобное было. Или для возведения в степень. Я думаю если Барлон заскочет
в топик - то он прояснит. Вроде скилованный парень в этих кольцах и модулях.
Для умножения. Китайская теорема об остатках.
11 окт 19, 16:40    [21992377]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2357
Barlone
mayton
Для умножения что-то подобное было. Или для возведения в степень. Я думаю если Барлон заскочет
в топик - то он прояснит. Вроде скилованный парень в этих кольцах и модулях.
Для умножения. Китайская теорема об остатках.
Получается, что есть формулы только для умножения, а для сложения формул нет.
11 окт 19, 16:54    [21992393]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 51153
 		Можно нарисовать табличку Пифагора для сложения. Я думаю что закономерность будет.
11 окт 19, 16:56    [21992398]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl→      все
Все форумы / Программирование Ответить