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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1840
В эвристическом алгоритме для числа 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

Откуда:
Сообщений: 1840
Появилась ещё одна статья.
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

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

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

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

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

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

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

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

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


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

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

Откуда: loopback
Сообщений: 42918
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

Откуда:
Сообщений: 1840
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
Сообщений: 42918
Gennadiy Usov,

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

Откуда:
Сообщений: 1840
Не стал много считать на своём стареньком ПК, поэтому только один час:

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

Откуда:
Сообщений: 1840
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

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

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

a mod(b)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда: loopback
Сообщений: 42918
Можно нарисовать табличку Пифагора для сложения. Я думаю что закономерность будет.
11 окт 19, 16:56    [21992398]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
Gennadiy Usov
mayton
Или ты имел в виду дистрибутивность операции mod?
Да. Может быть можно получить функцию вида
x mod(c) +- y mod(d) +- (что-то), или другие опперации?
Вопрос странный. Формулу вида x mod(c) +- y mod(d) +- (что-то) получитьможно всегда.
Надо тщательнЕе расставлять скобки, а то догадки разбегаются как тараканы:
b (mod x) = c + (d (mod x))
b (mod x) = (c + d)(mod x)
b (mod x) = c(mod x) + d (mod x)
((c + d)(mod x))(mod x)
Здесь только один вариант верен для натуральных в общем случае.
А вообще, найти опровергающие примеры было в тягость, школьная арифметика, не царское это дело.
13 окт 19, 14:12    [21993052]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
exp98
Gennadiy Usov
Да. Может быть можно получить функцию вида
x mod(c) +- y mod(d) +- (что-то), или другие опперации?
Вопрос странный. Формулу вида x mod(c) +- y mod(d) +- (что-то) получитьможно всегда.
Надо тщательнЕе расставлять скобки, а то догадки разбегаются как тараканы:
b (mod x) = c + (d (mod x))
b (mod x) = (c + d)(mod x)
b (mod x) = c(mod x) + d (mod x)
((c + d)(mod x))(mod x)
Здесь только один вариант верен для натуральных в общем случае.
А вообще, найти опровергающие примеры было в тягость, школьная арифметика, не царское это дело.
Здесь надо было связать сообщение с предыдущим сообщением:

Если есть
a mod (x+y),
то можно ли это выражение разложить на
a1 (mod x) и a2 (mod y)?
13 окт 19, 16:59    [21993099]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov, нет конечно
Легко найти пару чисел, равных по модулям a и b, но при этом неравных по модулю a+b.
Или наоборот, пару чисел, равны по модулю a+b, но неравных по модулям a и b.
13 окт 19, 20:35    [21993233]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Убежден что Геннадия ведет какая-то интуиция. И она ему подсказывает искать формулы
ускоренного сложения чисел по модулю. Очевидно что за этим стоит некая оптимизационная
цель.
13 окт 19, 21:46    [21993261]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
- Гена, знаешь, когда идёшь по рельсам,то никогда не заблудишься.
- Эт ты пральна сказал, Чебурашка.
(цэ)
13 окт 19, 23:05    [21993281]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Здесь больше подходит диалог Алисы и Чеширского кота

— Скажите, пожалуйста, куда мне отсюда идти?
— А куда ты хочешь попасть? — ответил Кот.
— Мне все равно... — сказала Алиса.
— Тогда все равно куда и идти, — заметил Кот.
— Только бы попасть куда-нибудь, — пояснила Алиса.
— Куда-нибудь ты обязательно попадешь, — сказал Кот. — Нужно только достаточно долго идти.
13 окт 19, 23:55    [21993300]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Нашел для Питона распечатку программы pow:
http://qaru.site/questions/132239/how-did-python-implement-the-built-in-function-pow

def pow_mod(x, y, z):				
	"Calculate (x ** y) % z efficiently."			
	number = 1			
	while y:			
		if y & 1:		
			number = number * x % z	
		y >>= 1		
		x = x * x % z		
	return number	


Это самая быстрая программа для Питона для pow?
16 окт 19, 09:20    [21995132]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov,
"Быстрая" и "для питона" - это оксюморон.
В природе существуют https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери и https://ru.wikipedia.org/wiki/Умножение_Карацубы но это не для питона
16 окт 19, 12:18    [21995349]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Для прототипирования Питона вполне достаточно. Если мы упрёмся именно в процессорные ресурсы для умножения
или деления то можно подключать к питону библиотечки-ускорители.

Но об этом еще рано говорить IMHO. Мы же не делаем новый стандарт несимметричного шифра.

Мы - экспериментируем.
16 окт 19, 12:29    [21995366]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
mayton
Убежден что Геннадия ведет какая-то интуиция. И она ему подсказывает искать формулы
ускоренного сложения чисел по модулю. Очевидно что за этим стоит некая оптимизационная
цель.
Расчёты на ПК по определению простых чисел Мерсенна показали, что практически за одно и тоже время определяют простые числа Мерсенна
как тест Люка-Лемера, так и эвристический алгоритм (одна формула вида pow).

Поэтому ставится задачка:

доработать алгоритм для процедуры pow таким образом, чтобы эвристический алгоритм при определении простых чисел Мерсенна работал быстрее, чем тест Люка-Лемера.
mayton
Если мы упрёмся именно в процессорные ресурсы для умножения
или деления то можно подключать к питону библиотечки-ускорители.
Но об этом еще рано говорить IMHO. Мы же не делаем новый стандарт несимметричного шифра.
Мы - экспериментируем.
Скорее всего, подключение библиотечек-ускорителей мало что даст.

Ведь идёт поиск алгоритма для программы, а не поиск самой программы.

На каждом компьютере и в каждой среде на нём будет своя скорость расчёта простых чисел.
И в каждой среде будут, скорее всего, такие же ускорители.
17 окт 19, 05:40    [21995987]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Если сравнивать тест Люка-Лемера и процедуру типа pow для чисел Мерсенна Mn, то оказывается, что :
- в каждом тесте количество циклов равно n;
- в каждом тесте в цикле идет умножение х = х*х;
- в тесте Люка-Лемера от числа х отнимается 2 для каждого элемента цикла;
- в pow число х умножается на предыдущее число (number) для каждого элемента цикла;
- и после каждой операции идёт операция %.

Данные рассуждения говорят о том, что скорости работы теста Люка-Лемера и процедуры pow почти равны,
о чём уже говорилось на топике по результатам работы прораммы.
17 окт 19, 06:08    [21995992]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Gennadiy Usov, я несколько раз обращался к тебе с просьбой собрать отклик твоего кода через равные
промежутки интервалов. Я хотел построить график. И по нему оценить асимптоматику. Это важно.
Важные даже не числа а форма графика. Парабола. Экспонента. Или x в степени x как некая ссылка
на комбинаторную сложность. Но мне показалось что данные у тебя беспорядочны и их мало и я отбросил
эту затею.

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

Откуда:
Сообщений: 1840
mayton
А асимптоматику надо считать.
В данном топике рассматривается задачка
построения алгоритма для определения очень больших простых чисел,
например, простых чисел Мерсенна, простых чисел, расположенных недалеко от чисел Мерсенна.

Программа на ПК показала, что эвристический алгоритм 21980061(одна формула) показывает результаты,
сравнимые с результатами работы теста Люка-Лемера:
- количество и перечень простых чисел Mn , время работы.
Проверено до n = 20000 (далее - ПК очень долго считает).

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

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

Откуда:
Сообщений: 1840
mayton
Если полином то хорошо.
Алгоритм для pow - полином?
17 окт 19, 13:49    [21996516]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

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

Откуда:
Сообщений: 1840
Сравнил pow из 21995132 и оказалось,
что этот алгоитм работает в два раза медленнее pow из стандартной библиотеки Питона.

Может быть есть ещё алгоритм для pow?
17 окт 19, 18:24    [21996850]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Сравнил pow из 21995132 и оказалось,
что этот алгоитм работает в два раза медленнее pow из стандартной библиотеки Питона.

Может быть есть ещё алгоритм для pow?
Учитывая, что pow из стандартной библиотеки питона написан не на питоне, даже удивительно, что всего в два раза медленнее...
17 окт 19, 20:11    [21996908]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Алгоритмы есть конечно - вот можно http://cacr.uwaterloo.ca/hac/about/chap14.pdf посмотреть
17 окт 19, 21:03    [21996939]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Вот pow из питона https://github.com/python/cpython/blob/master/Objects/longobject.c#L4243
а тут gmp https://gmplib.org/repo/gmp/file/tip/mpn/generic/powm.c
17 окт 19, 21:19    [21996947]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Вот pow из питона https://github.com/python/cpython/blob/master/Objects/longobject.c#L4243
а тут gmp https://gmplib.org/repo/gmp/file/tip/mpn/generic/powm.c
Если это питон, то почему скобки {?
17 окт 19, 21:41    [21996956]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov,
Интерпретатор питона написан на С. Сюрприз!
18 окт 19, 06:32    [21997019]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Немного отдохнул, и решил сравнить два теста: тест Люка-Лемера и эвристический алгоритм21980061.

Составил две программы на Питоне и выбрал интервал чисел Мерсенна от 11 до 5000 без применения делителей с шагом 2.

Получились следующие результаты:
для теста Люка-Лемера определение простых чисел Мерсенна шло 14 мин. 05 сек.
2019-10-25-15.11.25
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
2019-10-25-15.25.30 
Для эвристического алгоритма определение простых чисел Мерсенна шло 13 мин. 20 сек.
2019-10-25-15.31.05
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
2019-10-25-15.44.25 
То есть, эвристический алгоритм «работает» на 5% быстрее, чем тест Люка-Лемера.

Таким образом, получен самый быстрый алгоритм для определения простых чисел Мерсенна – эвристический алгоритм.
25 окт 19, 18:29    [22002962]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
5% это слишком мало. Это можно списать на погрешность
- Оптимизатора Python
- Недостатки твоей реализации.

Вообще интересно было-бы рассматривать 1000% и больше. Этож криптография мать ее так.
Полумеры нам не нужны.

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

Откуда:
Сообщений: 1840
mayton
5% это слишком мало. Это можно списать на погрешность
- Оптимизатора Python
- Недостатки твоей реализации.

Вообще интересно было-бы рассматривать 1000% и больше. Этож криптография мать ее так.
Полумеры нам не нужны.

Уж если бахнуть так бахнуть.
И там и там - Python.
Две формулы по три оператора - что проще?
25 окт 19, 18:46    [22002972]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Gennadiy Usov
И там и там - Python.
Две формулы по три оператора - что проще?

Шо там пробовать? Сало - як сало.
25 окт 19, 18:49    [22002973]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Однако, 5% - это хорошее подспорье.

При 20 часах работы ПК экомится 1 час работы!
(или вместо 20 чисел можно проверить 21 число за то же время.)
25 окт 19, 19:11    [22002987]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Для крипто-задач я думаю комиссия смотрела-бы не на 5% а на какие-то другие технологические поинты.
25 окт 19, 19:20    [22002993]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
mayton
Для крипто-задач я думаю комиссия смотрела-бы не на 5% а на какие-то другие технологические поинты.
Просто так отказаться от алгоритма, который считает на 5% быстрее?
Всего-то: каких-то 3 оператора меняются на 3 других оператора.

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

Откуда: loopback
Сообщений: 42918
Да яж говорю. Плевать на 5%.

Это не стоит никакого апгрейта. Тут не то что алгоритм. Тут люди ключи годами не хотят менять.
25 окт 19, 19:33    [22003002]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
mayton
5% это слишком мало. Это можно списать на погрешность
- Оптимизатора Python
- Недостатки твоей реализации.

Вообще интересно было-бы рассматривать 1000% и больше. Этож криптография мать ее так.
Полумеры нам не нужны.

Уж если бахнуть так бахнуть.
И там и там - Python.
Две формулы по три оператора - что проще?
pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.
25 окт 19, 21:41    [22003056]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Малыхин Сергей
Member

Откуда: г. Курск
Сообщений: 729
Странно что в теме нет графика простых чисел в полярных координатах

[youtube=]
25 окт 19, 23:45    [22003081]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov
И там и там - Python.
Две формулы по три оператора - что проще?
pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.
Две программы написаны на питоне.

Эта часть программы для эвристического алгоритма
a1 = 3					
while p <= P:					
	Mp = pow(2, p) -1 				
	t1 = (Mp -1)//2				
	x = pow(a1, t1, Mp)				
	if x == Mp- 1:				
		print (p)			
					
	p  +=2
Эта часть программы для теста Люка-Лемера
while p <= P:					
	Mp = pow(2, p) -1 				
	c = 4				
	i = 2				
	while i <= p-1:				
		c =(c*c-2) % Mp 			
		i += 1			
	if c == 0:				
		print(p)			
	p +=2	
И где нечестное сравнение?
26 окт 19, 07:25    [22003102]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

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

Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
26 окт 19, 08:08    [22003109]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
Хотите сказать, что цикл на Питоне работает медленнее цикла на С, на котором написана процедура pow?
26 окт 19, 09:03    [22003121]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Gennadiy Usov
Barlone
Gennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
Хотите сказать, что цикл на Питоне работает медленнее цикла на С, на котором написана процедура pow?

В целом да. Но тебе на сях писать не надо. Там - другие сложности в которых ты потонешь.

Но другие участники форума могут помочь тебе с портированием твоего кода на С.
Только его надо причесать. Выделить главную функцию и параметризировать ее.
26 окт 19, 13:58    [22003184]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
На самом деле, даже не в скорости дело. Тест Люка-Лемера для чисел Мерсенна детерменированный, то есть доказано, что число, пошедшее тест - действительно простое. В отличие от...
26 окт 19, 18:41    [22003293]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

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

На то он и эвристический алгоритм, что он помогает в расчётах, и его не обязательно доказывать.
Главное - проверено на небольших числах:

Найденные эвристическим алгоритмом простые числа совпадают с простыми числами Мерсенна
(ранее найденными тестом Люка-Лемера).

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

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
Поставил функцию, время работы алгоритма "просело".
Однако, за счет последующего улучшения алгоритма, над которым идёт работа,
время работы алгоритма превышает время работы теста Люка-Лемера примерно на 2 - 3 %.

Есть ещё сложности: на моём ПК время работы программы зависит от времени суток (?).
Поэтому стараюсь проводить сравнение сразу друг за другом.
27 окт 19, 07:18    [22003497]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Может антивирус работает параллельно.
27 окт 19, 09:33    [22003509]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
mayton
Может антивирус работает параллельно.
Может и антивирус. Давно не обновлял, хотя есть напоминания.
Но вчера и сегодня могут отличаться на 30 сек для программы на 13 минут.

Компьютер старенький...
27 окт 19, 10:09    [22003521]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Поскольку ты - новичек в анализе перформанса приложений то послушай совет.

Нажми Ctr+Shift+Esc. Для Windows будет такая картинка.

Картинка с другого сайта.

Ты должен запускать замер производительности когда "CPU Usage" будет близко к нулю.
Это означает что в данный момент нет посторонних активностей в ОС Windows.
А там их бывает много.

Понаблюдай как коррелирует загрузка с твоем процессом. Возможно ты увидешь как 1 ядро
будет загружено (из 8 возможных на картинке).

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

Откуда:
Сообщений: 1840
mayton
Понаблюдай как коррелирует загрузка с твоем процессом. Возможно ты увидешь как 1 ядро будет загружено (из 8 возможных на картинке).
Понаблюдай насколько оно загружено.
Спасибо!

Запустил Люка-Лемера.
Ядер у меня 4.(четыре картинки сверху). Все загружены. одно очень сильно.Одно слабо.
ЦП - 26-29%
27 окт 19, 11:34    [22003558]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
В форуме С++

Дано натуральное число P. Определить все совершенные числа, не превосходящие P
28 окт 19, 16:55    [22004437]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
mayton
В форуме С++

Дано натуральное число P. Определить все совершенные числа, не превосходящие P
И что?
Определяет и определяет.
Обычное деление на множители.
28 окт 19, 17:07    [22004449]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Может быть, было бы интереснее сделать двухступенчатое деление:
сначала определяются простые числа для деления, а потом само деление.
И всё это идет по наростающей.
28 окт 19, 17:11    [22004458]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Вот ты спрашивал про С++. Вот тебе и С++.
Типы данных - от 32 до 64 бит вобщем.
То что обзывают int.
28 окт 19, 17:16    [22004465]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
mayton
Вот ты спрашивал про С++. Вот тебе и С++.
Типы данных - от 32 до 64 бит вобщем.
То что обзывают int.
Не спрашивал я про С++, про С, про ...
И какая разница, какой язык применяется при расчётах.
Главное: чтобы этот язык работал с большими числами.

Ведь разговор идёт об алгоритме, о тесте, о формуле.

А как всё это реализовать, каждый решает на удобном ему языке.
(естественно, с учетом быстродействия).
28 окт 19, 18:17    [22004510]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Как будет угодно.
28 окт 19, 18:19    [22004513]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
При работе с эвристическим алгоритмом при определении чисел Мерсенна 21980061 меня удивляло:
почему для проверки числа достаточно только одного раунда (одно обращение к оператору pow).

Проведённые исследования 22015600 показали, что числа Мерсенна входят в рабочий диапазон этих чисел Мерсенна.

Поэтому для проверки числа Мерсенна достаточно одно обращение к оператору pow (с основанием степени 3).
14 ноя 19, 18:28    [22016510]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / Программирование Ответить