|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneПорядок подгруппы может оказаться делителем N-1Для простого N ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:21 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Но при этом может быть несколько одинаковых подгрупп для простого N. (например, 7, 31, 43) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:36 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Сделал код для теста Миллера — Рабина. Пока сделал код для первого условия: . Оказалось, что для 2047 (составное число) для разного расчета - запуск программы (разные случайные числа) получаю разные данные: то для числа 2047 - получаю 1 (число простое), то нет 1. В вики для теста записано: "выполняется хотя бы одно из условий": Как быть? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:48 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, может у нас разная вики, но в моём варианте написано: авторЕсли хотя бы одно такое равенство не выполняется, это доказывает что число составное тынц ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 00:16 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Если тест Ферма для какого-то a mod N говорит, что число N псевдопростое, а тест Миллера — Рабина для этого же a - что N составное, то мы еще и делитель N нашли... ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 05:35 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovСделал код для теста Миллера — Рабина. Пока сделал код для первого условия: . Оказалось, что для 2047 (составное число) для разного расчета - запуск программы (разные случайные числа) получаю разные данные: то для числа 2047 - получаю 1 (число простое), то нет 1. В вики для теста записано: "выполняется хотя бы одно из условий": Как быть? Геннадий. Я вижу что недетерминизм не дает тебе спокойно спать. Делай от 2 до 50 раундов проверки. Как здесь. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 07:51 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonГеннадий. Я вижу что недетерминизм не дает тебе спокойно спать. Делай от 2 до 50 раундов проверки. Здесь дело не в раундах. Здесь всё сложнее. Для составного числа 2047 может появиться 1, а может и не появиться, в зависимости от случайного числа. Тогда что важнее: - то, что появилась 1 - то, что не появилось 1 ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 10:22 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, важнее то что алгоритм Миллера-Раввина относится к классу bounded error probabalistic, как и функции хеширования и фильтры Блума. Но ты упорно пытаешся вытащить его из этой классификации и перетащить в другую. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 10:31 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Попробовал не останавливать поиск случайного числа для первой части теста Миллера-Раввина, а насчитать сто вариантов случайных чисел для определения простоты ряда чисел. Получилось: - для числа 2047 (составное) из 100 вариантов появлялось 5 – 7 раз число 1 и 2 – 3 раза число 2046, смотрел несколько вариантов по 100. - для число 2039 (простое) из 100 вариантов появлялись числа либо 1, либо 2038, других чисел не было. - для числа 2053 (простое) из 100 вариантов появлялось 34 числа 1, 21 число 2052, остальные – другие числа. Получается, что числа вида 2039 можно выделить в отдельное достаточное множество простых чисел. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 11:04 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, можно задать тебе вопрос? Как ты себе понимаешь вот этот предикат? Код: java 1.
На самом верхнем уровне смыслов. Ну тоесть что делает этот фрагмент кода человеческим языком? (я дам подсказку. this - это и есть твое число 2047) ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 11:11 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonGennadiy Usov, можно задать тебе вопрос? Как ты себе понимаешь вот этот предикат? Код: java 1.
На самом верхнем уровне смыслов. Ну тоесть что делает этот фрагмент кода человеческим языком? (я дам подсказку. this - это и есть твое число 2047)Я почти не работал в JAVA, поэтому трудно ответить на вопрос. А вопрос не в числе 2047. Вопрос в действии теста Миллера-Раввина, чтобы была уверенность, что тест "помогает" находить простые числа. А 2047 - это тестовый вариант. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 11:27 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Давай почитаем еще раз описание. (я беру это всё из опенсорцных источников с Гитхаба ссылку на который я уже приводил если что). Данная функция primeToCertainty(int certainty, Random random) возвращает true, если число вероятно-простое. И возвращает false если оно ТОЧНО составное. (Точно-точно. 100% составное!) Внизу - пересечение двух предикатов Миллера и Люка. МиллерЛюкаРезультатfalsefalsefalsefalsetruefalsetruefalsefalsetruetruetrue Пробабалистический Миллер который шумит и даёт иногда в зависимости от состояния датчика случайных чисел разные значения вынесен как первый. Он работает раньше. Его полезный эффект - отбить составные числа. Тоесть - снять нагрузку с Люка. Здесь я точно не уверен возможно это просто моё предположение. Просто практика использования расчетных функций это подскзывает. Пускай Барлон подскажет так оно или нет. Я не изучал эти оба алгоритма внутри и не знаю насколько они сложны. Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 11:47 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
mayton Я не изучал эти оба алгоритма внутри и не знаю насколько они сложны.А зря не изучали.maytonПробабалистический Миллер который шумит и даёт иногда в зависимости от состояния датчика случайных чисел разные значения вынесен как первый. Он работает раньше. Его полезный эффект - отбить составные числа. Тоесть - снять нагрузку с Люка. Здесь я точно не уверен возможно это просто моё предположение. Просто практика использования расчетных функций это подскзывает. Тест Миллера не отбивает составные числа! Он может их выдавать иногда (в зависимости от "настроения" случайных чисел). Если бы было иначе, то задача поиска простых чисел уже была бы решена. А насчет Люка, Вы 21955051 уже ответили, что не знаете как работает этот тест с обычным числом (не числом Мерсенна). maytonПускай Барлон подскажет так оно или нет. Одна надежда на Барлона ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 13:03 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovТест Миллера не отбивает составные числа! А ну-ка нука. Что-же он делает? ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 13:08 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonGennadiy UsovТест Миллера не отбивает составные числа!А ну-ка нука. Что-же он делает?Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые. Поэтому, фраза "Его полезный эффект - отбить составные числа" можно отнести к любому тесту простоты. Чем тогда тест Миллера лучше других тестов. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 13:36 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usovmaytonпропущено... А ну-ка нука. Что-же он делает?Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые. Поэтому, фраза "Его полезный эффект - отбить составные числа" можно отнести к любому тесту простоты. Чем тогда тест Миллера лучше других тестов. Например какой тест? ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 14:04 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovЧем тогда тест Миллера лучше других тестов.Тем, что оставляет меньше псевдопростых. https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел) ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 14:41 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Я прошу прощения. Во избежание кривотолков я буду писать фактическое название функции как это записано в исходниках JDK. Интерпретация - это будет второй вопрос. passesMillerRabinpassesLucasLehmerResultfalsefalsefalsefalsetruefalsetruefalsefalsetruetruetrue ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 14:45 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovЧем тогда тест Миллера лучше других тестов.Тем, что оставляет меньше псевдопростых. https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел) Согласен! Это я и хотел сказать, но высказался некорректно. Теперь осталось найти следующий тест, который оставит ещё меньше псевдопростых. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 15:41 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Просьба помочь! Код: sql 1. 2. 3. 4. 5.
На питоне число t становится действительным. А как сделать так, чтобы оно было целым? ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 16:16 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Я не разбираюсь в Питоне. Но скорее всего виновата функция pow() она возвращает другой тип. Попробуй две звездочки. Код: python 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 17:18 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Блин... Вот так. Код: python 1. 2. 3. 4. 5. 6.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 17:28 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonБлин... Вот так. Код: python 1. 2. 3. 4. 5. 6.
Спасибо! (p = 2**pp - 1) - это понравилось! В то же время, нашел t = t // 2. Знал об этом, и забыл. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.08.2019, 17:51 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
В сообщении 21952153 говорилось о подзадаче 1. "Выбор последовательности целых чисел". Следующей подзадачей поиска простых чисел на диапазоне очень больших чисел будет следующая подзадача: Подзадача 2. "Построение решета для определения псевдопростых чисел". (перечень делителей) В сообщении 21954266 говорилось о соотношении времени на проведения операций теста Ферма и деления на множители. Поэтому для каждого диапазона необходимо проводить, помимо определённого шага, ещё и проверку чисел на делители (как более быстрая операция) перед применением теста Ферма (как более медленная операция). И в каждом диапазоне должно быть своё количество проверяемых делителей. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.08.2019, 13:13 |
|
|
start [/forum/topic.php?fid=16&msg=39853228&tid=1339906]: |
0ms |
get settings: |
10ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
171ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
69ms |
get tp. blocked users: |
2ms |
others: | 14ms |
total: | 302ms |
0 / 0 |