powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
25 сообщений из 283, страница 7 из 12
Ещё раз о тесте Ферма
    #39852985
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneПорядок подгруппы может оказаться делителем N-1Для простого N
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852995
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Но при этом может быть несколько одинаковых подгрупп для простого N. (например, 7, 31, 43)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853001
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сделал код для теста Миллера — Рабина.

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

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

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

Как быть?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853044
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,

может у нас разная вики, но в моём варианте написано:
авторЕсли хотя бы одно такое равенство не выполняется, это доказывает что число составное
тынц
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853064
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если тест Ферма для какого-то a mod N говорит, что число N псевдопростое, а тест Миллера — Рабина для этого же a - что N составное, то мы еще и делитель N нашли...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853077
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return this.passesMillerRabin(rounds, random);
        } else {
            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 this.passesMillerRabin(rounds, random) && this.passesLucasLehmer();
        }
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853134
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonГеннадий. Я вижу что недетерминизм не дает тебе спокойно спать.
Делай от 2 до 50 раундов проверки. Здесь дело не в раундах.
Здесь всё сложнее.

Для составного числа 2047 может появиться 1, а может и не появиться, в зависимости от случайного числа.

Тогда что важнее:
- то, что появилась 1
- то, что не появилось 1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853139
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov, важнее то что алгоритм Миллера-Раввина относится к классу bounded error probabalistic,
как и функции хеширования и фильтры Блума. Но ты упорно пытаешся вытащить его из этой классификации
и перетащить в другую.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853165
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Попробовал не останавливать поиск случайного числа для первой части теста Миллера-Раввина,
а насчитать сто вариантов случайных чисел для определения простоты ряда чисел.

Получилось:
- для числа 2047 (составное) из 100 вариантов появлялось 5 – 7 раз число 1 и 2 – 3 раза число 2046,
смотрел несколько вариантов по 100.
- для число 2039 (простое) из 100 вариантов появлялись числа либо 1, либо 2038, других чисел не было.
- для числа 2053 (простое) из 100 вариантов появлялось 34 числа 1, 21 число 2052, остальные – другие числа.

Получается, что числа вида 2039 можно выделить в отдельное достаточное множество простых чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853167
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov, можно задать тебе вопрос?

Как ты себе понимаешь вот этот предикат?
Код: java
1.
this.passesMillerRabin(rounds, random) && this.passesLucasLehmer();


На самом верхнем уровне смыслов. Ну тоесть что делает этот фрагмент кода человеческим языком?

(я дам подсказку. this - это и есть твое число 2047)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853174
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy Usov, можно задать тебе вопрос?
Как ты себе понимаешь вот этот предикат?
Код: java
1.
this.passesMillerRabin(rounds, random) && this.passesLucasLehmer();

На самом верхнем уровне смыслов. Ну тоесть что делает этот фрагмент кода человеческим языком?
(я дам подсказку. this - это и есть твое число 2047)Я почти не работал в JAVA, поэтому трудно ответить на вопрос.

А вопрос не в числе 2047.

Вопрос в действии теста Миллера-Раввина,
чтобы была уверенность, что тест "помогает" находить простые числа.
А 2047 - это тестовый вариант.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853188
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Давай почитаем еще раз описание. (я беру это всё из опенсорцных источников с Гитхаба ссылку на который
я уже приводил если что).

Данная функция 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.
    /**
     * Returns {@code true} if this BigInteger is probably prime,
     * {@code false} if it's definitely composite.
     *
     * This method assumes bitLength > 2.
     *
     * @param  certainty a measure of the uncertainty that the caller is
     *         willing to tolerate: if the call returns {@code true}
     *         the probability that this BigInteger is prime exceeds
     *         {@code (1 - 1/2<sup>certainty</sup>)}.  The execution time of
     *         this method is proportional to the value of this parameter.
     * @return {@code true} if this BigInteger is probably prime,
     *         {@code false} if it's definitely composite.
     */
    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();
    }
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853224
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton Я не изучал эти оба алгоритма внутри и не знаю насколько они сложны.А зря не изучали.maytonПробабалистический Миллер который шумит и даёт иногда в зависимости от состояния датчика случайных чисел разные значения вынесен как первый. Он работает раньше. Его полезный эффект - отбить составные числа. Тоесть - снять нагрузку с Люка. Здесь я точно не уверен возможно это просто моё предположение. Просто практика использования расчетных функций это подскзывает. Тест Миллера не отбивает составные числа!
Он может их выдавать иногда (в зависимости от "настроения" случайных чисел).
Если бы было иначе, то задача поиска простых чисел уже была бы решена.

А насчет Люка, Вы 21955051 уже ответили, что не знаете как работает этот тест с обычным числом (не числом Мерсенна).
maytonПускай Барлон подскажет так оно или нет. Одна надежда на Барлона
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853228
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovТест Миллера не отбивает составные числа!
А ну-ка нука.

Что-же он делает?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853245
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovТест Миллера не отбивает составные числа!А ну-ка нука.
Что-же он делает?Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые.

Поэтому, фраза "Его полезный эффект - отбить составные числа" можно отнести к любому тесту простоты. Чем тогда тест Миллера лучше других тестов.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853257
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovmaytonпропущено...
А ну-ка нука.
Что-же он делает?Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые.

Поэтому, фраза "Его полезный эффект - отбить составные числа" можно отнести к любому тесту простоты. Чем тогда тест Миллера лучше других тестов.
Например какой тест?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853283
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЧем тогда тест Миллера лучше других тестов.Тем, что оставляет меньше псевдопростых.
https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853289
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я прошу прощения. Во избежание кривотолков я буду писать фактическое название функции
как это записано в исходниках JDK. Интерпретация - это будет второй вопрос.
passesMillerRabinpassesLucasLehmerResultfalsefalsefalsefalsetruefalsetruefalsefalsetruetruetrue
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853317
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЧем тогда тест Миллера лучше других тестов.Тем, что оставляет меньше псевдопростых.
https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел) Согласен!

Это я и хотел сказать, но высказался некорректно.

Теперь осталось найти следующий тест, который оставит ещё меньше псевдопростых.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853355
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Просьба помочь!
Код: sql
1.
2.
3.
4.
5.
pp = 55
p = pow(2, pp) - 1
t = p - 1
t = t / 2;
print (t)

На питоне число t становится действительным.

А как сделать так, чтобы оно было целым?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853378
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я не разбираюсь в Питоне. Но скорее всего виновата функция pow() она возвращает другой тип.

Попробуй две звездочки.

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec  5 2015, 20:40:30) [MSC v.1500 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>>
>>> pp = 55
>>> p = 2*pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
54
>>>
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853384
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Блин... Вот так.

Код: python
1.
2.
3.
4.
5.
6.
>>> pp = 55
>>> p = 2**pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
18014398509481983
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853396
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonБлин... Вот так.
Код: python
1.
2.
3.
4.
5.
6.
>>> pp = 55
>>> p = 2**pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
18014398509481983

Спасибо!

(p = 2**pp - 1) - это понравилось!

В то же время, нашел t = t // 2.
Знал об этом, и забыл.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853477
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В сообщении 21952153 говорилось о подзадаче 1. "Выбор последовательности целых чисел".

Следующей подзадачей поиска простых чисел на диапазоне очень больших чисел будет следующая подзадача:

Подзадача 2. "Построение решета для определения псевдопростых чисел". (перечень делителей)

В сообщении 21954266 говорилось о соотношении времени на проведения операций теста Ферма и деления на множители.

Поэтому для каждого диапазона необходимо проводить, помимо определённого шага,
ещё и проверку чисел на делители (как более быстрая операция)
перед применением теста Ферма (как более медленная операция).

И в каждом диапазоне должно быть своё количество проверяемых делителей.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853483
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Напомню что я приводил исходники функции nextProbablePrime() название
которой буквально переводится как "следующее вероятно-простое число".

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


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