powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
25 сообщений из 283, страница 8 из 12
Ещё раз о тесте Ферма
    #39853498
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Каждое целое положительное число, большее 0,
будет считаться псевдопростым или вероятностно простым до тех пор,
пока к этому числу не применили какой-нибудь тест простоты,
и этот тест показал, что проверяемое число является составным числом.

По моему так...

Кстати, название - нечётное число - это то же является самым простым (предварительным) тестом простоты.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853520
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonВобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса. Потом Миллера Раввина в пересечечии с Люка-Лемьером. Причем идет
пересеченеи условий. Необходимое - Миллер. Я бы на 3-ю подзадачу поиска простых чисел на диапазоне очень больших чисел поставил следующую подзадачу:

Подзадача 3. "Применение теста Ферма". (более мелкое решето)

из-за следующего

- тест Ферма позволяет "не забыть" ни одно простое число
(в тесте Миллера-Раввина многое решают случайные числа 21956300 ).

- тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина.

И уже на следующем шаге подключать более сложные тесты.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853522
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov- тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина.
С чего бы быстрее? Возводить в степень (n-1)/2, а потом в квадрат или сразу в (n-1) - по времени никакой разницы.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853523
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov- тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина.
С чего бы быстрее? Возводить в степень (n-1)/2, а потом в квадрат или сразу в (n-1) - по времени никакой разницы.В тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1).

Разница по времени вычисления теста для одного числа n есть?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853524
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Только сейчас заметил, что если для теста Миллера-Раввина получаем случайное число 2,
то тест Миллера-Раввина превращается в тест Ферма.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853535
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Забыл сказать, что тест Миллера-Раввина может превратиться в тест Ферма при степени 2 только для случая, когда (n - 1) делится только на одну 2.

Далее, первая часть теста Миллера-Раввина "не ловит" простые числа 13,17,37,97,113,193, и т.д.

При этом первая часть теста Миллера-Раввина принимает за простое число 341.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853536
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov, что за "первая часть"?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853537
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovВ тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1).

Разница по времени вычисления теста для одного числа n есть?Ну это вообще ерунда, и Ферма можно по разным основаниям считать.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853540
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovВ тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1).
Разница по времени вычисления теста для одного числа n есть?Ну это вообще ерунда, и Ферма можно по разным основаниям считать.Конечно можно.

Только при реальной проверке произвольного числа на простоту сколько оснований закладывается в программу?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853541
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov, что за "первая часть"?У теста Миллера-Раввина есть два условия https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина

Я пока проверяю первое условие (первая часть).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853542
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЯ пока проверяю первое условие (первая часть).Оно так не работает
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853544
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЯ пока проверяю первое условие (первая часть).Оно так не работаетПочему не работает.

Ещё как работает!

Подробности позднее.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853552
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так не работает же
Gennadiy UsovСделал код для теста Миллера — Рабина.

Пока сделал код для первого условия:
.

Оказалось, что для 2047 (составное число) для разного расчета - запуск программы (разные случайные числа) получаю разные данные:
то для числа 2047 - получаю 1 (число простое), то нет 1.

В вики для теста записано:
"выполняется хотя бы одно из условий":

Как быть?В вики написано: "если число простое, то выполняется хотя бы одно из условий". Значит, если не одно из условий не выполняется, число точно составное. Вы проверили только одно. Это не дает ничего. Если первое условие выполнено, число может быть как простым, так и составным. Если первое условие не выполнено, а второе не проверялось, то число тоже может быть как простым, так и составным.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853553
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А в чем проблема то проверить второе условие? У вас есть s - количество младших нулевых битов в n-1. Вы полученное на первом шаге число s-1 раз возводите в квадрат по модулю n и каждый раз сравниваете с n-1.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853554
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneТак не работает жеGennadiy UsovСделал код для теста Миллера — Рабина.
Пока сделал код для первого условия:
.
Оказалось, что для 2047 (составное число) для разного расчета - запуск программы (разные случайные числа) получаю разные данные:
то для числа 2047 - получаю 1 (число простое), то нет 1.
В вики для теста записано:
"выполняется хотя бы одно из условий":
Как быть?В вики написано: "если число простое, то выполняется хотя бы одно из условий". Значит, если не одно из условий не выполняется, число точно составное. Вы проверили только одно. Это не дает ничего. Если первое условие выполнено, число может быть как простым, так и составным. Если первое условие не выполнено, а второе не проверялось, то число тоже может быть как простым, так и составным.Так Вы же всё отметили в сообщении.

Число 2047 по первому условию теста Миллера — Рабина может быть признано простым (псевдопростым),
поскольку иногда по случайному числу получаем 1. 21956300
При этом будет цикл из log( n ) случайных чисел.

Если получилась 1, то согласно теста Миллера — Рабина второе условие можно не выполнять.

Вот и вся история с географией.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853556
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneА в чем проблема то проверить второе условие? У вас есть s - количество младших нулевых битов в n-1. Вы полученное на первом шаге число s-1 раз возводите в квадрат по модулю n и каждый раз сравниваете с n-1.А этим нарушаются условия теста Миллера — Рабина:
"выполняется хотя бы одно из условий:"(из вики)

Иначе можно договорить о доработке теста Миллера — Рабина с точки зрения:
выполнения двух условий.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853558
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
С логикой у вас проблемы.
Из того, что число простое, следует, что выполняется хотя бы одно из двух условий.
Из того, что выполняется первое условие, ничего не следует.
Из того, что не выполняется первое условие, тоже ничего не следует.
Из того, что ни одно из двух условий не выполняется, следует, что число составное.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853559
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovИначе можно договорить о доработке теста Миллера — Рабина с точки зрения:
выполнения двух условий. Ну оба условия сразу выполниться никак не могут, сколько единицу в квадрат не возводи, она минус единицей не станет.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853560
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneС логикой у вас проблемы.
Из того, что число простое, следует, что выполняется хотя бы одно из двух условий.
Из того, что выполняется первое условие, ничего не следует.
Из того, что не выполняется первое условие, тоже ничего не следует.
Из того, что ни одно из двух условий не выполняется, следует, что число составное.При чём здесь логика?

Я выполняю правила теста Миллера — Рабина.

Я эти правила нарушил?
Где, в каком месте?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853561
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если обсуждать алгоритм 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.
boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

        // The relationship between the certainty and the number of rounds
        // we perform is given in the draft standard ANSI X9.80, "PRIME
        // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
        int sizeInBits = this.bitLength();
        if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return passesMillerRabin(rounds, random);
        }

        if (sizeInBits < 256) {
            rounds = 27;
        } else if (sizeInBits < 512) {
            rounds = 15;
        } else if (sizeInBits < 768) {
            rounds = 8;
        } else if (sizeInBits < 1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }
        rounds = n < rounds ? n : rounds;

        return passesMillerRabin(rounds, random) && passesLucasLehmer();
    }


    /**
     * Returns true iff this BigInteger passes the specified number of
     * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
     * 186-2).
     *
     * The following assumptions are made:
     * This BigInteger is a positive, odd number greater than 2.
     * iterations<=50.
     */
    private boolean passesMillerRabin(int iterations, Random rnd) {
        // Find a and m such that m is odd and this == 1 + 2**a * m
        BigInteger thisMinusOne = this.subtract(ONE);
        BigInteger m = thisMinusOne;
        int a = m.getLowestSetBit();
        m = m.shiftRight(a);

        // Do the tests
        if (rnd == null) {
            rnd = ThreadLocalRandom.current();
        }
        for (int i=0; i < iterations; i++) {
            // Generate a uniform random on (1, this)
            BigInteger b;
            do {
                b = new BigInteger(this.bitLength(), rnd);
            } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);

            int j = 0;
            BigInteger z = b.modPow(m, this);
            while (!((j == 0 && z.equals(ONE)) || z.equals(thisMinusOne))) {
                if (j > 0 && z.equals(ONE) || ++j == a)
                    return false;
                z = z.modPow(TWO, this);
            }
        }
        return true;
    }




Тоесть если вы хотите показать что он работает неверно то нужно оперировать
формулами вероятности и учесть условные вероятности ложно-позитивного срабатывания
Миллера с учотом того что Люка тоже дал ложное срабатывание и не заметил что число составное.
Что там? Формулы Бернулли кажется. Я не помню.

Я прошу прощения я не сильно навязываюсь? Просто у меня ощущение что я влез со своим исходником
в ваш топик и как-будто бы внёс другую повестку дня.

Если я мешаю - то скажите и я не буду больше писать. Просто мне кажется что вы "ломитесь" в открытую дверь.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853563
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonЕсли обсуждать алгоритм nextProbablePrime который я приводил то Миллер-Рабин срабатывает

1) Только для аргументов числа-кандидата больше 2^95. Это видно в исходном коде.
2) Выполняется числом раундов от 27 до 2 в зависимости от разрядности сетки. Это сделано ради экономии ресурсов скорее всего (число 2).

Тоесть если вы хотите показать что он работает неверно то нужно оперировать
формулами вероятности и учесть условные вероятности ложно-позитивного срабатывания
Миллера с учотом того что Люка тоже дал ложное срабатывание и не заметил что число составное.
Что там? Формулы Бернулли кажется. Я не помню.

Я прошу прощения я не сильно навязываюсь? Просто у меня ощущение что я влез со своим исходником
в ваш топик и как-будто бы внёс другую повестку дня.

Если я мешаю - то скажите и я не буду больше писать. Просто мне кажется что вы "ломитесь" в открытую дверь.Если коротенько, то
1. В последних сообщениях топика идёт обсуждение положений и правил работы теста Миллер-Рабина.
2. Любой алгоритм (в данном случае тест Миллер-Рабина) должен быть обязательным для программ, которые ссылаются на этот тест.
3. При этом могут быть отступления от теста Миллер-Рабина, которые отдельно могут быть объяснены.
4. В тесте Миллер-Рабина нет ни слова о "Только для аргументов числа-кандидата больше 2^95".
5. Любой тест желательно проверить на небольших числах. Так удобнее.
6. Уже в который раз прошу дать ссылку на тест Люка, на который Вы регулярно ссылаетесь.

Вместе с тем, спасибо за участие в обсуждениях!

Со своей стороны, постараюсь подготовить программу для второго условия теста Миллер-Рабина,
чтобы сравнивать результаты двух условий.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853566
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Gennadiy UsovЗабыл сказать, что тест Миллера-Раввина может превратиться в тест Ферма при степени 2 только для случая, когда (n - 1) делится только на одну 2.
Далее, первая часть теста Миллера-Раввина "не ловит" простые числа 13,17,37,97,113,193, и т.д.
При этом первая часть теста Миллера-Раввина принимает за простое число 341.Сделал программу на второе условие теста Миллера-Раввина.
Это условие оказалось более сильным, чем первое условие.

"Нашлись" потерянные простые числа, которые я ранее "не поймал" с помощью первого условия.

При этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853567
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хорошо. Я понял.

По поводу исходного кода теста Люка-Лемера.

Исходники находятся здесь https://github.com/unofficial-openjdk/openjdk/blob/jdk/jdk/src/java.base/share/classes/java/math/BigInteger.java
Смотрите процедуры passesLucasLehmer и вспомогательные процедуры jacobiSymbol и lucasLehmerSequence
Код: java
1.
2.
private boolean passesLucasLehmer() {
.....


Спрашивайте вопросы.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853569
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853573
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Полистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?).

Зеленым цветом обозначены истинные тесты простоты. Красным - вероятностные. Прочие заметки - серым.
...
Рейтинг: 0 / 0
25 сообщений из 283, страница 8 из 12
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]