|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonСогласен. Кстати я бы поднял отдельный топик. Быстрое умножение и быстрое возведение в квадрат для arbitary precision. Просто для того чтобы провести ревизию текущих API и библиотек. Используют они эти методы или нет. А то меня терзают смутные сомнения. https://ru.wikipedia.org/wiki/Умножение_Карацубы ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 05:15 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonGennadiy UsovЯ уже приводил чередование 4 и 2 21952153 . Накопление простых в массиве может когда-то прекратиться.(на больших числах)А тебе много и не надо. Накопи простых хотя-бы тыщу. Большая часть делителей отбивается на самых ранних шагах.Можно применить "ленивый алгоритм накопленных простых чисел". О нём уже было сказано 21954752 . Поскольку там ошибка, привожу ещё раз (без ошибки) Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9.
В массив можно записать хоть 1000 чисел. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 07:50 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonВ своих экспериментах я выкидывал квадратный корень и заменял его на линейную функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет любая легко-вычислимая функция которая заведомо выше чем p для любых p.По этому поводу можно рассмотреть такой вариант. Квадраты последовательных чисел N и (N + 1) отстоят друг от друга на (2*N+1). Поскольку делители - только нечётные числа, то N и (N + 2) отстоят друг от друга на (4*N+4). Итак, в начале находим корень минимума диапазона, от целого этого числа получаем "квадрат N", и это будет точкой отсчета по смене величины, которая ограничивает количество делителей. Осталось проверять расстояние исследуемого числа от предыдущего "квадрата N", и если получаемое расстояние превышает (4*N+4) от этого "квадрата N", то определяется новый "квадрат N+1", равный увеличению предыдущего "квадрата N" на (4*N+4). ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 13:14 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonПочему 22 ?Очень удобно в одном массиве в ячейке [0] помещать длину массива данных, и "работать" с массивом, начиная с ячейки [1]. Мы ведь привыкли считать: 1,2,,,,,,n, а не 0,1,2,,,,,(n-1) И притом, нужна будет отдельная переменная для хранения количества данных в массиве. Кстати, я уже это демонстрировал на предыдущих топиках. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 13:19 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Почитал про Питон. Длину массива берут так. Код: python 1. 2. 3. 4.
Только в интенсивных циклах я-бы все равно поместил это число в отдельную переменную. Просто так и яснее и не будет потенциальных проблем с перформансом. Мы ведь не знаем как дорого для питона стоит эта операция взятия длины. Для С++ ASCIIZ-массивов она стоила линейно от длины самой строчки. Тоесть чем длиннее строка тем дольше ждать. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 14:12 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Решил ещё раз поработать с тестом Миллера-Рабина с точки зрения: какой перечень остатков выдаёт этот тест. Пока поработал с числами до 115. Есть простые числа, для которых только 1 или n-1 по двум условиям теста: 7, 11,19,23,31,43,47,59,67,71,79,83,103,107 Есть простые числа, для которых только 1 или n-1 по двум условиям теста не для всех случайных чисел: 29,37,41,61,73,89,101,109,113 Есть простые числа, для которых только 1 или n-1 только по второму условию: 5,13,17(не все),53,97(не все), Есть составные числа, для которых только 1 только по второму условию: 39, 105. Поэтому по второму условию значение 1 не подходит. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 18:17 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, Выпишите несколько табличек для разных простых n: в первый столбец все числа от 1 до n-1, а в строку их степени по модулю n. Например для 5 так Код: plaintext 1. 2. 3. 4.
А потом выпишите такую же табличку для составного числа. Только надо как-то еще мелкими циферками в каждую клеточку дописать остатки по каждому сомножителю этого числа. Прочитайте про китайскую теорему об остатках . А чтобы понять, как получаются псевдопростые, надо сделать такую табличку для составного числа, у которого большой НОД(φ(n), n-1). Ну например 91=7*13, НОД(90, 72)=18. Правда, табличка большая получится, но если над ней помедитировать, то озарение обязательно придет. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 20:35 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Barlone, Вопрос не в том, как получаются псевдопростые числа. Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках. Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 21:16 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Если бы мы знали как разделить область определения Миллера-Раввина на детерминированную и случайную то получили бы две функции. Причем одна из них была бы строго детерминирована по определению. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 21:23 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 21:25 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarlone, Вопрос не в том, как получаются псевдопростые числа. Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках. Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.Вопрос как раз в том, как получаются псевдопростые. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 21:34 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Я могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :) ... |
|||
:
Нравится:
Не нравится:
|
|||
27.08.2019, 21:38 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonЕсли бы мы знали как разделить область определения Миллера-Раввина на детерминированную и случайную то получили бы две функции. Причем одна из них была бы строго детерминирована по определению.Пример 21957887 показал, что тест Миллера-Раввина находит среди чисел Мерсенна только простые числа без пропусков, причем только с помощью первого условия. Правда, медленнее теста Люка-Лемера раза в 2-3. Это уже область применения без появления составных чисел.BarloneGennadiy Usov, Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.Увеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример - 21956300 ), из-за которых эти числа принимаются тестом как простые.BarloneGennadiy UsovBarlone, Вопрос не в том, как получаются псевдопростые числа. Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках. Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.Вопрос как раз в том, как получаются псевдопростые.При исследовании теста Миллера-Рабина (может быть и других тестов) необходимо для каждого составного небольшого числа (как примера) отследить появление условий 1 или (n - 1), частоту их появления и тогда принимать какие-то решения по этим результатам. Например, есть числа 21958523 , для которых тест Миллера-Рабина показывает только 1 или (n - 1) по двум условиям. Здесь можно говорить о подмножестве простых чисел, для которых существует достаточное условие (примерно как в 21907153 ).BarloneЯ могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)С удовольствием прочитаю. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 07:01 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovУвеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример - 21956300 ), из-за которых эти числа принимаются тестом как простые.Не так это работает. Каждый раунд говорит либо "число точно составное", либо "не уверен, может быть простым." Если хотя бы один из раундов сказал, что число точно составное - то оно таки составное. А чтобы доказать, что число простое, надо очень много раундов, порядка log(n) - это уже детерминированный вариант теста. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 07:58 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov, Ты как то по своему понял смысл раунда. Там нет голосования. Там - право вето. Первый раунд который детектировал составное - отменяет все результаты до этого. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 08:01 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
У меня 2 вопроса ( с учетом примера 21956300 ) для чисел 2047 и 2053: Пока для первого условия теста Миллера-Рабина: для числа 2047 (составное) после нескольких раундов (выбор случайного числа) появляется 1. Это означает, что число 2047 псевдопростое? для числа 2053 (простое) в течении нескольких раундов (выбор случайного числа) не будет появляться 1. Это означает, что число 2053 составное? ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 09:01 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Решил "отбросить" поиск случайного числа для первого условия теста Миллера-Рабина и заменил этот поиск на перебор вариантов от 2 до (n - 2). Для чисел до 115 - не так много информации. Оказалось, что: 1. Есть числа, у которых в остатке (по модулю) получается только 1 и (n - 1). Множество таких чисел уже может быть подмножеством простых чисел. 2. Есть числа, которые мы считаем простыми, у которых в остатке (по модулю) значения 1 и (n - 1) составляют от 70% до 5% от общего перечня остатков. Для некоторых из этих чисел трудно будет найти значение 1. 3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается только 1. В разных числах 1, 2, 5 значений. 4. Есть числа, у которых при переборе от 2 до (n - 2) остатки (по модулю) то же плавно возрастают от 2 до (n - 2). ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 13:31 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Ошибся. пункт 3 предыдущего сообщения надо читать так: 3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается иногда 1. В разных числах 1, 2, 5 значений. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 13:38 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Я давно наблюдаю за форумом. И заметил что программисты очень не любят читать прозу. Зато исходник вызывает у них живой интерес. Если ты просто опубликуешь работающий код на Питоне то ты имеешь шанс получить ответ на твой вопрос. Поэтому код с комментариями эффективнее чем просто текст который все не поняли или интерпретировали по разному. Вот такие они... программисты. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 16:15 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonЯ давно наблюдаю за форумом. И заметил что программисты очень не любят читать прозу. Зато исходник вызывает у них живой интерес. Если ты просто опубликуешь работающий код на Питоне то ты имеешь шанс получить ответ на твой вопрос. Поэтому код с комментариями эффективнее чем просто текст который все не поняли или интерпретировали по разному. Вот такие они... программисты.А как они пишут новую программу? По другому коду или по алгоритму? ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 16:20 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Не могу сказать. Это очень творческий процесс. Впрочем как и всё чем мы тут занимаемся. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 16:25 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
maytonЕсли ты просто опубликуешь работающий код на Питоне то ты имеешь шанс получить ответ на твой вопрос.Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне: Код: python 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24.
... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 19:19 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy Usov Код: python 1. 2. 3.
Мне кажется тут ослаблен контроль над типами. Кажется что натуральный логарифм и степень возвращают число с плавающей точкой. А это не очень согласуется с решаемой задачей где везде и всегда будут целые числа произвольной точности (arbitrary precision). ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 23:34 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Почитал Википедию. Этот исходник 21954899 - это не Люка-Лемьер. Это Люка-Лемьер-Ризель (LLT) предположительно. Поэтому все что я писал надо читать с поправкой по этому названию. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.08.2019, 23:45 |
|
|
start [/forum/topic.php?fid=16&msg=39853975&tid=1339906]: |
0ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
170ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
61ms |
get tp. blocked users: |
1ms |
others: | 256ms |
total: | 534ms |
0 / 0 |