|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Каждое целое положительное число, большее 0, будет считаться псевдопростым или вероятностно простым до тех пор, пока к этому числу не применили какой-нибудь тест простоты, и этот тест показал, что проверяемое число является составным числом. По моему так... Кстати, название - нечётное число - это то же является самым простым (предварительным) тестом простоты. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.08.2019, 18:23 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonВобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы прямого брутфорса. Потом Миллера Раввина в пересечечии с Люка-Лемьером. Причем идет пересеченеи условий. Необходимое - Миллер. Я бы на 3-ю подзадачу поиска простых чисел на диапазоне очень больших чисел поставил следующую подзадачу: Подзадача 3. "Применение теста Ферма". (более мелкое решето) из-за следующего - тест Ферма позволяет "не забыть" ни одно простое число (в тесте Миллера-Раввина многое решают случайные числа 21956300 ). - тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина. И уже на следующем шаге подключать более сложные тесты. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 05:59 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov- тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина. С чего бы быстрее? Возводить в степень (n-1)/2, а потом в квадрат или сразу в (n-1) - по времени никакой разницы. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 07:51 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneGennadiy Usov- тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина. С чего бы быстрее? Возводить в степень (n-1)/2, а потом в квадрат или сразу в (n-1) - по времени никакой разницы.В тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1). Разница по времени вычисления теста для одного числа n есть? ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 08:55 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Только сейчас заметил, что если для теста Миллера-Раввина получаем случайное число 2, то тест Миллера-Раввина превращается в тест Ферма. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 08:59 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Забыл сказать, что тест Миллера-Раввина может превратиться в тест Ферма при степени 2 только для случая, когда (n - 1) делится только на одну 2. Далее, первая часть теста Миллера-Раввина "не ловит" простые числа 13,17,37,97,113,193, и т.д. При этом первая часть теста Миллера-Раввина принимает за простое число 341. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 13:30 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, что за "первая часть"? ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 13:36 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovВ тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1). Разница по времени вычисления теста для одного числа n есть?Ну это вообще ерунда, и Ферма можно по разным основаниям считать. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 13:39 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovВ тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1). Разница по времени вычисления теста для одного числа n есть?Ну это вообще ерунда, и Ферма можно по разным основаниям считать.Конечно можно. Только при реальной проверке произвольного числа на простоту сколько оснований закладывается в программу? ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 13:48 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneGennadiy Usov, что за "первая часть"?У теста Миллера-Раввина есть два условия https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина Я пока проверяю первое условие (первая часть). ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 13:52 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovЯ пока проверяю первое условие (первая часть).Оно так не работает ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 13:57 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovЯ пока проверяю первое условие (первая часть).Оно так не работаетПочему не работает. Ещё как работает! Подробности позднее. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 14:14 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Так не работает же Gennadiy UsovСделал код для теста Миллера — Рабина. Пока сделал код для первого условия: . Оказалось, что для 2047 (составное число) для разного расчета - запуск программы (разные случайные числа) получаю разные данные: то для числа 2047 - получаю 1 (число простое), то нет 1. В вики для теста записано: "выполняется хотя бы одно из условий": Как быть?В вики написано: "если число простое, то выполняется хотя бы одно из условий". Значит, если не одно из условий не выполняется, число точно составное. Вы проверили только одно. Это не дает ничего. Если первое условие выполнено, число может быть как простым, так и составным. Если первое условие не выполнено, а второе не проверялось, то число тоже может быть как простым, так и составным. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 15:54 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
А в чем проблема то проверить второе условие? У вас есть s - количество младших нулевых битов в n-1. Вы полученное на первом шаге число s-1 раз возводите в квадрат по модулю n и каждый раз сравниваете с n-1. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 16:07 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneТак не работает жеGennadiy UsovСделал код для теста Миллера — Рабина. Пока сделал код для первого условия: . Оказалось, что для 2047 (составное число) для разного расчета - запуск программы (разные случайные числа) получаю разные данные: то для числа 2047 - получаю 1 (число простое), то нет 1. В вики для теста записано: "выполняется хотя бы одно из условий": Как быть?В вики написано: "если число простое, то выполняется хотя бы одно из условий". Значит, если не одно из условий не выполняется, число точно составное. Вы проверили только одно. Это не дает ничего. Если первое условие выполнено, число может быть как простым, так и составным. Если первое условие не выполнено, а второе не проверялось, то число тоже может быть как простым, так и составным.Так Вы же всё отметили в сообщении. Число 2047 по первому условию теста Миллера — Рабина может быть признано простым (псевдопростым), поскольку иногда по случайному числу получаем 1. 21956300 При этом будет цикл из log( n ) случайных чисел. Если получилась 1, то согласно теста Миллера — Рабина второе условие можно не выполнять. Вот и вся история с географией. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 16:08 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneА в чем проблема то проверить второе условие? У вас есть s - количество младших нулевых битов в n-1. Вы полученное на первом шаге число s-1 раз возводите в квадрат по модулю n и каждый раз сравниваете с n-1.А этим нарушаются условия теста Миллера — Рабина: "выполняется хотя бы одно из условий:"(из вики) Иначе можно договорить о доработке теста Миллера — Рабина с точки зрения: выполнения двух условий. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 16:12 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
С логикой у вас проблемы. Из того, что число простое, следует, что выполняется хотя бы одно из двух условий. Из того, что выполняется первое условие, ничего не следует. Из того, что не выполняется первое условие, тоже ничего не следует. Из того, что ни одно из двух условий не выполняется, следует, что число составное. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 16:33 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovИначе можно договорить о доработке теста Миллера — Рабина с точки зрения: выполнения двух условий. Ну оба условия сразу выполниться никак не могут, сколько единицу в квадрат не возводи, она минус единицей не станет. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 16:44 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneС логикой у вас проблемы. Из того, что число простое, следует, что выполняется хотя бы одно из двух условий. Из того, что выполняется первое условие, ничего не следует. Из того, что не выполняется первое условие, тоже ничего не следует. Из того, что ни одно из двух условий не выполняется, следует, что число составное.При чём здесь логика? Я выполняю правила теста Миллера — Рабина. Я эти правила нарушил? Где, в каком месте? ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 16:54 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Если обсуждать алгоритм nextProbablePrime который я приводил то Миллер-Рабин срабатывает 1) Только для аргументов числа-кандидата больше 2^95. Это видно в исходном коде. 2) Выполняется числом раундов от 27 до 2 в зависимости от разрядности сетки. Это сделано ради экономии ресурсов скорее всего (число 2). 3) Внутри параметризируется встроенным генератором случайных чисел на который мы извне не влияем. Этот датчик практически не должен дать два подряд одинаковых случайных числа в таком юзкейсе b = new BigInteger(this.bitLength(), rnd); Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68.
Тоесть если вы хотите показать что он работает неверно то нужно оперировать формулами вероятности и учесть условные вероятности ложно-позитивного срабатывания Миллера с учотом того что Люка тоже дал ложное срабатывание и не заметил что число составное. Что там? Формулы Бернулли кажется. Я не помню. Я прошу прощения я не сильно навязываюсь? Просто у меня ощущение что я влез со своим исходником в ваш топик и как-будто бы внёс другую повестку дня. Если я мешаю - то скажите и я не буду больше писать. Просто мне кажется что вы "ломитесь" в открытую дверь. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 17:18 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonЕсли обсуждать алгоритм nextProbablePrime который я приводил то Миллер-Рабин срабатывает 1) Только для аргументов числа-кандидата больше 2^95. Это видно в исходном коде. 2) Выполняется числом раундов от 27 до 2 в зависимости от разрядности сетки. Это сделано ради экономии ресурсов скорее всего (число 2). Тоесть если вы хотите показать что он работает неверно то нужно оперировать формулами вероятности и учесть условные вероятности ложно-позитивного срабатывания Миллера с учотом того что Люка тоже дал ложное срабатывание и не заметил что число составное. Что там? Формулы Бернулли кажется. Я не помню. Я прошу прощения я не сильно навязываюсь? Просто у меня ощущение что я влез со своим исходником в ваш топик и как-будто бы внёс другую повестку дня. Если я мешаю - то скажите и я не буду больше писать. Просто мне кажется что вы "ломитесь" в открытую дверь.Если коротенько, то 1. В последних сообщениях топика идёт обсуждение положений и правил работы теста Миллер-Рабина. 2. Любой алгоритм (в данном случае тест Миллер-Рабина) должен быть обязательным для программ, которые ссылаются на этот тест. 3. При этом могут быть отступления от теста Миллер-Рабина, которые отдельно могут быть объяснены. 4. В тесте Миллер-Рабина нет ни слова о "Только для аргументов числа-кандидата больше 2^95". 5. Любой тест желательно проверить на небольших числах. Так удобнее. 6. Уже в который раз прошу дать ссылку на тест Люка, на который Вы регулярно ссылаетесь. Вместе с тем, спасибо за участие в обсуждениях! Со своей стороны, постараюсь подготовить программу для второго условия теста Миллер-Рабина, чтобы сравнивать результаты двух условий. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 17:49 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovЗабыл сказать, что тест Миллера-Раввина может превратиться в тест Ферма при степени 2 только для случая, когда (n - 1) делится только на одну 2. Далее, первая часть теста Миллера-Раввина "не ловит" простые числа 13,17,37,97,113,193, и т.д. При этом первая часть теста Миллера-Раввина принимает за простое число 341.Сделал программу на второе условие теста Миллера-Раввина. Это условие оказалось более сильным, чем первое условие. "Нашлись" потерянные простые числа, которые я ранее "не поймал" с помощью первого условия. При этом пришлось изменить уравнение второго условия теста Миллера-Раввина https://ru.wikipedia.org/wiki/ вместо -1(mod n) "подошло" +1(mod n). ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 18:21 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Хорошо. Я понял. По поводу исходного кода теста Люка-Лемера. Исходники находятся здесь https://github.com/unofficial-openjdk/openjdk/blob/jdk/jdk/src/java.base/share/classes/java/math/BigInteger.java Смотрите процедуры passesLucasLehmer и вспомогательные процедуры jacobiSymbol и lucasLehmerSequence Код: java 1. 2.
Спрашивайте вопросы. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 18:21 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но информация - к сведенью https://rosettacode.org/wiki/Lucas-Lehmer_test#Python ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 18:38 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Полистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде написано то как их правильно называть (Solovey или Solovay?). Зеленым цветом обозначены истинные тесты простоты. Красным - вероятностные. Прочие заметки - серым. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.08.2019, 19:02 |
|
|
start [/forum/topic.php?fid=16&msg=39853558&tid=1339906]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
175ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
57ms |
get tp. blocked users: |
1ms |
others: | 245ms |
total: | 524ms |
0 / 0 |