|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Я не буду спорить с википедией. Просто приведу исходник. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 22:44 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Тут дело не в программе. Главное: какие чисел эта программа (тест Люка — Лемера) определила как простые? (кроме чисел Мерсенна) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 07:28 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Кроме того, тест Люка — Лемера работает при использовании степени 2 у выбранного числа (и -1). А как для произвольного числа определить эту степень 2 ? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 07:32 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Тестов много разных... https://ru.wikipedia.org/wiki/Псевдопростое_число_Люка https://ru.wikipedia.org/wiki/Псевдопростое_число https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 10:12 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
По сорцам Люка параметризуется неким загадочным Символом Якоби. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 10:29 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Я нарисую блок-схему. Для Геннадия и для себя тоже. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 10:40 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Нет в символе Якоби ничего загадочного. Это обобщение символа Лежандра на составные числа, и для простых чисел они совпадают. Только вычисляют его (Якоби) не по определению, где нужно разложение на простые, а через квадратичный закон взаимности. Для простого модуля символ Якоби позволяет определить, является ли какое-то число квадратичным вычетом по этому модулю, то есть существует ли квадратный корень из числа по модулю. (Например, 2 - квадратичный вычет по модулю 7, так как 3*3 mod 7 == 2) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 11:41 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneТестов много разных... https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа А данный тест очень интересный. Имеется два теста: тест Ферма и тест Люка (не тест Люка — Лемера). С помощью каждого из этих тестов определяются все простые числа и ещё несколько составных чисел. Причем, для каждого теста составные числа различные. В вики: "Мощность теста состоит в том, что не существует известных пересечений списков псевдопростых чисел Ферма и псевдопростых чисел Люка." Осталось понять: для каких чисел тесты будут разными. Если тесты разные, то число составное. Поскольку привычно работать с тестом Ферма, то сначала находится число, удовлетворяющее тесту Ферма, а затем это число проверяется на тест Люка. Далее осталось найти пример работы теста Люка. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 13:16 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Однако, интерес к этому тесту поубавился. Числа Люка - Vn = { 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... } , это очень малая часть нечётных чисел. Получается, что можно проверить только отдельные числа. Кроме того, для очень больших чисел невозможно (нужно очень много времени) найти последовательность чисел Люка - эти числа определяются от первого числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 13:31 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovПолучается, что можно проверить только отдельные числа. Не так. Последовательность Люка используется для проверки произвольного числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 15:21 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovПолучается, что можно проверить только отдельные числа. Не так. Последовательность Люка используется для проверки произвольного числа.Имеется последовательность Люка: Числа Люка - Vn = { 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... } , Следовательно, в эту последовательность не попадают числа 101, 103, и т.д. То есть, не все числа можно проверить. Или я ошибаюсь? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 15:38 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Множество ненулевых остатков (вычетов) по модулю простого числа N - абелева группа порядка N-1. Что проверяет тест Ферма? Он проверяет, что порядок подгруппы, порожденной некоторым выбранным элементом, делит N-1. Когда он дает ложноположительный результат? Если N составное, то порядок группы будет φ(N). А порядок подгруппы, порожденной неким элементом, будет делителем φ(N). И тест Ферма сфейлится, когда этот делитель φ(N) окажется также и делителем N-1 ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 19:28 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
А такой вопрос: есть простое число N, для которого получаем (N - 1) значений теста Ферма. Эти числа различны или нет? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 19:39 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Кроме мультипликативной группы вычетов по модулю, можно сконструировать и всякие другие группы - матрицы (но она на Абелева - умножение матриц не коммутативно), полиномы, точки на эллиптической кривой , решения уравнения Пелля … Коэффициенты всех этих матриц, полиномов, … можно брать по модулю числа N. И можно несколькими способами сконструировать группу, порядок которой для простого N будет N+1. И вот тут я не совсем уверен, но кажется, тест Люка проверяет, что порядок некой подгруппы такой группы делит N+1. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 19:43 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovА такой вопрос: есть простое число N, для которого получаем (N - 1) значений теста Ферма. Эти числа различны или нет?Для простого N естественно все значения будут 1. Для составного будет 1, если порядок подгруппы делит N-1, и не 1, если не делит :) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 19:47 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Вот смотрите: 21^64 % 65 == 1 - фейл, 65 = 5*13 Смотрим 21^1 % 65 == 21; 21^2 % 65 == 51; 21^3 % 65 == 31; 21^4 % 65 == 1; а дальше пойдет повтор - 21^5 % 65 == 21. То есть порядок подгруппы, порожденной 21, по модулю 65 равен 4. А 65-1 делится на 4. И тест фейлится. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:05 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Наверное, я не так сформулировал задачу. Имелось в виду числа от 2^1 % 65 до 2^64 % 65. Это тоже группа? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:08 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
А, да, φ(65) = 4 * 12 = 48. Кажется, всегда, когда для составного N НОД(φ(N), N-1) > 2 можно найти значение, на котором тест Ферма сфейлится. (Но это не точно, в смысле доказать я сейчас не смогу). ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:09 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovНаверное, я не так сформулировал задачу. Имелось в виду числа от 2^1 % 65 до 2^64 % 65. Это тоже группа?Ну так их же 4 всего разных. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:12 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Ой, не то написал ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:13 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
А если числа от от 2^1 % 59 до 2^58 % 59, то числа будут разные? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:14 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Для двойки (и любого другого числа по модулю 65) порядок группы будет каким-то делителем 48. Если этот делитель будет кратен 3, то он не делит 64, и тест Ферма покажет, что число составное. А если делитель не кратен трем, то в данном случае он будет также делителем 64. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:17 |
|
Ещё раз о тесте Ферма
|
|||
---|---|---|---|
#18+
Gennadiy UsovА если числа от от 2^1 % 59 до 2^58 % 59, то числа будут разные? не обязательно ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 20:19 |
|
|
start [/forum/topic.php?fid=16&msg=39852467&tid=1339906]: |
0ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
172ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
67ms |
get tp. blocked users: |
1ms |
others: | 14ms |
total: | 300ms |
0 / 0 |