Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6] 7 8 9   вперед  Ctrl      все
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Усов - твой принц.

Его ответственность что-то доказывать. Наша позиция - позиция критиков. Мы - опровергаем.
1 окт 19, 15:14    [21983966]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Усов - твой принц.

Его ответственность что-то доказывать. Наша позиция - позиция критиков. Мы - опровергаем.
Что конкретно опровергаете?

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

Откуда: loopback
Сообщений: 42891
Не скажу. Иш ты какой хитрый. Вот скажу - тогда побежишь исправлять.
1 окт 19, 15:25    [21983982]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Раз ничего нет, значит, и исправлять нечего

Строгое математическое доказательство
1 окт 19, 15:30    [21983992]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1843
Ну я-то скорее скептик, чем критик.
И скажу крылатыми словами: Такой принц нам не нужен!
Gennadiy Usov
Раз ничего нет, значит, и исправлять нечего
Строгое математическое доказательство
Хотелось бы верить ... да только в суде так строго бывает: на "Нэт!" и суда нет(цэ)

Нет, а ну-ка, погоди, что значит "ничего нет"? т.е. все ку-ка-ре-ку - лажа?
2 окт 19, 22:32    [21985441]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Интересная ситуация получается

Есть эвристический алгоритм для определения всех простых чисел.
Есть упрощения алгоритма для определения всех чисел Мерсенна и их окружения.
Есть упрощение алгоритма для быстрого поиска 50% простых чисел.
Конечно, с учётом возможностей ПК.

И вдруг:
mayton
Наша позиция - позиция критиков. Мы - опровергаем.
Далее
Gennadiy Usov
Что конкретно опровергаете?
И итог
mayton
Не скажу. Иш ты какой хитрый. Вот скажу - тогда побежишь исправлять.
А это вообще ни в какие ворота не лезет
exp98
Ну я-то скорее скептик, чем критик.
И скажу крылатыми словами: Такой принц нам не нужен!
Gennadiy Usov
Раз ничего нет, значит, и исправлять нечего
Строгое математическое доказательство
Хотелось бы верить ... да только в суде так строго бывает: на "Нэт!" и суда нет(цэ)
Нет, а ну-ка, погоди, что значит "ничего нет"? т.е. все ку-ка-ре-ку - лажа?
А где логика с математикой?
3 окт 19, 05:53    [21985510]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Ребята я все не успеваю. Заполните плиз табличку.
Кстати, mayton,
а как поживает табличка?

"Завяла"?
3 окт 19, 06:07    [21985512]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Усов. Алгоритм чего ты разработал?
3 окт 19, 08:32    [21985529]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
3 окт 19, 09:40    [21985560]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
mayton
Усов. Алгоритм чего ты разработал?
Справка из начала сообщения21985510:

Есть эвристический алгоритм для определения всех простых чисел.
Есть упрощение алгоритма для определения всех чисел Мерсенна и их окружения.
Есть упрощение алгоритма для быстрого поиска 50% простых чисел.
3 окт 19, 10:03    [21985571]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Шикарно.
3 окт 19, 10:03    [21985572]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Всё уже придумано до нас. Усов, если вы думаете, что придумали что-то новое, то вы ошибаетесь, все это уже известно, просто вы плохо искали.

Придумал я как-то раз, как как можно добавить в сообщение контрольных битов, чтобы можно было не только обнаружить, что один из битов сообщения по дороге изменился, но и узнать какой именно, и исправить его. А оказалось, что Хэмминг придумал то же самое еще 50 лет назад.

Или вот тесты простоты и факторизация. Что делает тест Миллера-Рабина? Он фактически пытается убедиться в том, что порядок мультипликативной группы вычетов по модулю P делит P-1. По теореме о структуре конечной абелевой группы порядок любого элемента группы делит порядок группы. И если мы находим элемент, порядок которого не делит P-1 - значит число составное.
А можно, используя делители P-1, доказать простоту числа, не перебирая делители самого P.
И есть метод факторизации - p-1 метод Полларда - предполагая, что N=P*Q, пытаемся, перебрав все возможные делители P-1, получить единицу по модулю P.

Повторюсь, всё это базируется на мультипликативной группе вычетов по модулю P. А если взять другую группу?
Возьмем например матрицы 2х2. Умножение матриц не коммутативно, плохо, группа не абелева. Но можно выбрать коммутативную подгруппу. Например, для матриц вида
 x y
ny x
где n фиксированное, умножение будет коммутативным:
 x1 y1      x2 y2      (x1x2+ny1y2) (x1y2+x2y1)
ny1 x1 * ny2 x2 = n(x1y2+x2y1) (x1x2+ny1y2)
Если дополнительно потребовать, чтобы определитель такой матрицы был равен 1, получим уравнение Пелля, и решения этого уравнения можно умножать, получая новые решения - это как раз соответствует умножению таких матриц.

Ну вот у нас есть абелева группа решений уравнения Пелля. А давайте рассмотрим их по модулю простого числа P, и поинтересуемся порядком этой группы.
Оказывается, что если n квадратичный вычет по модулю P, то порядок этой группы равен P-1, а если n квадратичный невычет, то порядок равен P+1.
Первый случай неинтересен, такая группа изоморфна мультипликативной группе вычетов по модулю P. А вот случай невычета можно рассмотреть поподробнее.
Тут можно построить тест простоты по аналогии с Ферма: найдем n такое, что символ Якоби (n/P) был равен -1 и решение уравнения Пелля для этого n. Возведем это решение в степень P+1 по модулю P. Убедимся, что получили тривиальное решение (1,0).
Или даже аналог Миллера-Рабина: представим P+1 в виде 2sd, d нечетно. Возводим начальное решение в степень d, и убеждаемся, что либо сразу получили (1,0), либо, после не более s возведений в квадрат, (-1,0).

И вот придумал я значит эту конструкцию, проверил, что работает, а потом посмотрел повнимательней - а оказалось, что Люка это уже больше ста лет назад придумал. Только описано оно у него немножко по другому - через последовательности Люка.
Последовательности Люка определяются как линейные рекуррентные последовательности Vn и Un, параметризованные парой коэффициентов P, Q.
Но можно получить матричное представление: считаем дискриминант характеристического многочлена D = P*P - 4Q и подставляем в матрицу
P/2 1/2
D/2 P/2
Определитель этой матрицы равен Q, а возводя ее в степень n, получим Vn/2 и Un/2 в первой строке. Сильный вариант теста как раз требует Q=1 - вот и уравнение Пелля.

И P+1 метод факторизации также можно описать через степени решений уравнения Пелля вместо последовательностей Люка.
Так что всё придумано до нас...
3 окт 19, 10:30    [21985604]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Barlone
Всё уже придумано до нас. Усов, если вы думаете, что придумали что-то новое, то вы ошибаетесь, все это уже известно, просто вы плохо искали.
.....
Так что всё придумано до нас...
Вы ещё забыли указать, что:

и квадратный корень до меня придумали, и модульное исчисление до меня придумали, и тест Миллера-Рабина до меня придумали.
И много других формул.

И непонятно, каким образом все идеи и методы, что Вы перечислили в сообщении, помогают определять простые числа.

Это инструменты для решения проблемы определения простых чисел.

А теперь у меня к Вам вопросы:

1. А где написано, что числа Мерсенна определяет ещё какой-нибуть тест, кроме теста Люка-Лемера, да ещё с сопоставимой скоростью?

2. Где написано, что можно БЕЗ ВЕРОЯТНОСТИ определять ВСЕ простые числа (с учётом мощности ПК)?

3. Где написано, что можно за менее 4-х раундов для каждого числа определять 50% ВСЕХ простых чисел (с учётом мощности ПК)?

Говорите конкретно, а не пересказывайте всю высшую математику.
3 окт 19, 10:49    [21985615]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
И главное, кто определял простые числа в окрестности чисел Мерсенна?
Плюс 4, плюс 8, плюс 12 и т.д.

А эвристический алгоритм определяет такие числа.

То есть, кроме последовательности простых чисел Мерсенна
Mn = 2^n - 1
эвристический алгоритм определяет простые числа
Mnk = 2^n - 1 + k, k = 4, 8, 12, 16, 20, ...

Это тоже уже было?
3 окт 19, 11:17    [21985646]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov
1. А где написано, что числа Мерсенна определяет ещё какой-нибуть тест, кроме теста Люка-Лемера, да ещё с сопоставимой скоростью?

2. Где написано, что можно БЕЗ ВЕРОЯТНОСТИ определять ВСЕ простые числа (с учётом мощности ПК)?

3. Где написано, что можно за менее 4-х раундов для каждого числа определять 50% ВСЕХ простых чисел (с учётом мощности ПК)?

1. Тест Люка-Лемера для простоты проверки 2p-1 требует p-1 возведений в квадрат. Возведение в степень 2p-1-1 потребует p-2 возведений в квадрат плюс p-2 умножений, что минимум в два раза медленнее, а с учетом того, что возведение в квадрат быстрее, чем умножение произвольных чисел, более чем в два раза медленнее. Для поиска максимальных известных простых чисел это весьма существенно - там каждое число на обычном компьютере проверяется несколько месяцев.

2. Для математиков, пока вы строго математически не ДОКАЗАЛИ, что ваш алгоритм действительно это определяет, он не имеет никакого значения. А с практической точки зрения, для криптографических целей комбинация одного раунда Миллера-Рабина с тестом Люка достаточна.

3. Опять же, для математиков 50% простых - совсем не интересно. Либо вы доказываете теорему, которая выполняется для всех простых, либо это никому не нужно.
3 окт 19, 12:02    [21985695]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Barlone
3. Опять же, для математиков 50% простых - совсем не интересно. Либо вы доказываете теорему, которая выполняется для всех простых, либо это никому не нужно.
Как сказать...

Согласно тесту Миллера-Рабина для очень больших чисел N количество раундов при поиске простого числа составляет около log(N).

Допустим, нужно быстро найти несколько простых чисел на диапазоне очень больших чисел.

И для этого диапазона находится 50% простых чисел всего за 4 раунда.

Это никому не нужно?

Например, найти быстро очередное (не следующее) простое число.
3 окт 19, 12:23    [21985725]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Barlone
2. Для математиков, пока вы строго математически не ДОКАЗАЛИ, что ваш алгоритм действительно это определяет, он не имеет никакого значения.
А эвристический алгоритм и не надо доказывать по определению.

То что, алгоритм работает, доказано проведёнными расчётами на диапазоне чисел от 5 до 1 000 000 000.
Программа приведена на топике.

Далее, согласно эвристике, алгоритм можно распространить на большие числа.

Barlone
А с практической точки зрения, для криптографических целей комбинация одного раунда Миллера-Рабина с тестом Люка достаточна.
Данное утверждение не совсем верно.

Данные тесты - вероятностные.
Следовательно, есть вероятность сразу "попасть", а есть вероятность "промахнуться" с одного раза.
Что выбираете?
3 окт 19, 12:31    [21985735]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Вот на этих числах свой алгоритм проверьте: https://oeis.org/A074773
3 окт 19, 12:34    [21985740]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Вот еще хорошее число: 3825123056546413051
3 окт 19, 12:37    [21985749]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Barlone
1. Тест Люка-Лемера для простоты проверки 2p-1 требует p-1 возведений в квадрат.
Возведение в степень 2p-1-1 потребует p-2 возведений в квадрат плюс p-2 умножений, что минимум в два раза медленнее,
а с учетом того, что возведение в квадрат быстрее, чем умножение произвольных чисел, более чем в два раза медленнее.
Для поиска максимальных известных простых чисел это весьма существенно -
там каждое число на обычном компьютере проверяется несколько месяцев.
Сошлюсь на эвристику (практика - это сила) ...

Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
Взял эвристический алгоритм (одно уравнение) и написал программу на Питоне.

Обе программы определяли простые числа Мерсенна Mn для n < 20000.
Дальше - программа очень медленно работала.

Результаты работы программ совпали: по простым числам и почти по времени (несколько процентов).

При отдельном прогоне конкретного простого числа иногда эвристический алгоритм чуточку обгонял тест по времени.
3 окт 19, 12:50    [21985763]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9473
Gennadiy Usov
Сошлюсь на эвристику (практика - это сила) ...
... но не доказательство.
Любое число подтверждений в конкретных частных случаях не позволяет доказать гипотезу, зато единственное опровержение требует отвергнуть гипотезу.
3 окт 19, 12:55    [21985775]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov
Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
На питоне? Да, хороший вариант для измерения скорости :)
3 окт 19, 13:00    [21985784]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Barlone
Вот еще хорошее число: 3825123056546413051
Программа оценила число:

2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
3 окт 19, 13:01    [21985790]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9473
Gennadiy Usov
Программа оценила число:
2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
Этот загадочный ответ сообщает, что число простое или как?
3 окт 19, 13:04    [21985794]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Barlone
Gennadiy Usov
Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
На питоне? Да, хороший вариант для измерения скорости :)
Но сравнивались две прогроммы на Питоне.

Я же не говорю о времени работы программ.
Я говорю об одинаковых условиях для двух программ: старенький ПК, Питон.
3 окт 19, 13:06    [21985797]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6] 7 8 9   вперед  Ctrl      все
Все форумы / Программирование Ответить