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

При определении чисел Мерсенна тест Ферма часто показывает, что очередное число из последовательности - простое.
А на самом деле, большое количество чисел Мерсенна, определённых тестом Ферма как простые, не являются простыми числами.

А кроме чисел Мерсенна есть ли ещё примеры «ошибочности» теста Ферма?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825640
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Как известно,тест простоты Ферма для простого числа имеет вид:
.
(в общем виде – основание степени не 2, а произвольное число число а, которое не делится на n.)

Это условие является необходимым условием, но не достаточным.

Данному условию удовлетворяет бесконечное множество целых чисел, среди которых есть подмножество простых чисел.

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

Просто интересная задача.

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

их не так много по понятиям баз данных,
особенно с учётом того что в обычном программировании
есть некоторые ограничения из-за типа данных,
соответственно проще держать список
простых чисел в базе и делать проверку на exists из этого списка,
т.е. необходимость сложно-красивой математической
проверки/вывода/доказательства по всем правилам науки - отпадают.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825721
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825730
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
vikkivGennadiy Usov,
их не так много по понятиям баз данных,
особенно с учётом того что в обычном программировании
есть некоторые ограничения из-за типа данных,
соответственно проще держать список
простых чисел в базе и делать проверку на exists из этого списка,
т.е. необходимость сложно-красивой математической
проверки/вывода/доказательства по всем правилам науки - отпадают.А что, база данных простых чисел существует до ?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825737
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonЯ так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.Размечтались...

Будет топик намного короче.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825834
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.задача 21907153 сформулирована некорректно
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825835
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
SiemarglmaytonЯ так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.задача 21907153 сформулирована некорректноИ в чём некорректность?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825840
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovSynopticКурсовик?Нет.

Просто интересная задача.

Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?Современная математика не знает такого способа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825843
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovПросто интересная задача.
Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?Современная математика не знает такого способа.А как же куча тестов простоты, а как же алгоритм Эратосфена?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825844
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне кажется что вероятностные тесты простоты мы уже обсуждали.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825845
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие?

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

Которое определяет достаточность теста простоты?
Что за условия? Как вы их найдете?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825881
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovSiemarglпропущено...
задача 21907153 сформулирована некорректноИ в чём некорректность?
Ставится задача:
из подмножества простых чисел выделить меньшее подмножество простых чисел, для которых тест Ферма будет достаточным.
То есть, найти новое условие, которое будет достаточным для теста Ферма при определении простых чисел.
Если выбросить тавтологию, то задача в том, что найти
условие, которое будет достаточным для при определении простых чисел.
т.е формулу простых чисел, что невозможно
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825887
Фотография vikkiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemarglт.е формулу простых чисел, что невозможно
какой-то совсем однозначный вывод сбивающий с пути рационального решения вопроса,
ещё раз напомню если то что выше не понято: в бизнес-задачах организаций порядки области значений не настолько большие,
и вот как раз для этих диапазонов в принципе генерация списка (около 10% от всего диапазона) простых чисел - не проблема
так что лучше-бы не отрываться от реалий при разработке систем (помня о заложенных ограничениях) - тогда всё получится.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825888
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vikkiv,

а ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825896
Фотография vikkiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemarglа ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?
предполагаю что сосут из пальцев наверное другие, у кого уже такая привычка сложилась и жестко в терминологию вошло,
у меня выводы по реалиям бизнес задач на собственной практике работы в коммерческих организациях.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825898
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vikkivSiemarglа ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?
предполагаю что сосут из пальцев наверное другие, у кого уже такая привычка сложилась и жестко в терминологию вошло,
у меня выводы по реалиям бизнес задач на собственной практике работы в коммерческих организациях.Единственная бизнес-задача, для которой нужны простые числа - RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825899
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие?

Которое определяет достаточность теста простоты?Ну есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825900
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Современная математика не знает такого способа.А как же куча тестов простоты, а как же алгоритм Эратосфена?Ну там было "быстро". А алгоритм Эратосфена - это совсем не быстро, и вообще по объему требуемой памяти нереализуемо.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825903
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneЕдинственная бизнес-задача, для которой нужны простые числа - RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.А зачем хранить?

По мере нахождения простых чисел, эти числа "сразу поступают в работу".
Или "ждут своей очереди".
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825905
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneНу есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма.Какой?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825907
Фотография vikkiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone..Единственная бизнес-задача, для которой нужны простые числа - RSA шифрование...
ну может быть конечно, однако даже на ближайшее будущее расчётных мощностей
для взлома 128-битных ключей (пи Е38) на период их (короткой) жизни - пока явно не хватает.
в контексте форума о базах данных: для 1024битного ключа (так понимаю ассиметричного, т.к. при симметричном так много не надо)
bigint с их Е63 отпадает так-же как и decimal/real (Е38), разве что float с Е308 наиболее близок и GUID ещё кандидат с их 16ти байтным размером.

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

тынц , может на какие мысли натолкнёт
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39825963
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)Gennadiy Usov,
тынц , может на какие мысли натолкнётДумал об этом.

А как узнать: через какое число не проходит синусоида?
Снова решето?
А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826022
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovkealon(Ruslan)Gennadiy Usov,
тынц , может на какие мысли натолкнётДумал об этом.

А как узнать: через какое число не проходит синусоида?
Снова решето?
А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа.
Без симуляции - никак. Можно предложить сверх-точные эксперименты в области например
физики волн и ждать пока мы поймаем первую производную равную нулю как показано
на картинке. Но это ожидание будет затягиваться пропорционально нашим хотелкам.

Вопрос в том что мы хотим в цифрах. И сколько мы согласны ждать.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826025
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЕсть число (целое, нечётное).
Как быстро определить: простое это число или нет?
например так, если числа до 2000000000(тип long), с проверкой на чет/нечет, без списка простых чисел
Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
Option Explicit
Sub mm()
Dim a As Long
Debug.Print "выбор  простых в интервале=============="
''''''''''''''''''''''''''''''
mm190613a 0, 7
mm190613a 18, 7
mm190613a 550, 7
''''''''''''''''''''''''''''''
a = 10 ^ 6
mm190613a a, 7
''''''''''''''''''''''''''''''
a = 10 ^ 7
mm190613a a, 7

End Sub


Код: vbnet
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.
Sub mm190613a(n1z As Long, n2z As Long)
Dim n0 As Long, j1 As Long, jm As Long, jp As Long, zkol As Long, dt
Dim j2 As Long, j2k As Long

dt = Timer
Debug.Print "выбор от "; n1z; " \требуется чисел= "; n2z;

''Debug.Print 1; 2; 3; 5;
If (n1z Mod 2) = 0 Then
n0 = n1z + 1
Else
n0 = n1z
End If
If n0 < 7 Then
Debug.Print "\1 \2 \3 \5 ";
n0 = 7
End If

    For j1 = n0 To 1000000000 Step 2
    j2k = Sqr(j1)
        For j2 = 3 To j2k Step 2
        If (j1 Mod j2) = 0 Then GoTo nj1
        Next j2
    
    jm = j1 - 1
    jp = j1 + 1
        If (jm Mod 6) = 0 Or (jp Mod 6) = 0 Then
        Debug.Print "\"; j1;
        zkol = zkol + 1
        If zkol > n2z Then Exit For
        End If
    
nj1:
    Next j1
    Debug.Print
 Debug.Print " время в mсек\="; (Timer - dt) * 1000 \ 1

End Sub


'выбор от 0 требуется чисел= 7 1 2 3 5 7 11 13 17 ' время в mсек= 12'выбор от 18 требуется чисел= 7 19 23 29 31 37 41 43 47' время в mсек= 0'выбор от 550 требуется чисел= 7 557 563 569 571 577 587 593 599' время в mсек= 0'выбор от 1000000 требуется чисел= 7 1000003 1000033 1000037 1000039 1000081 1000099 1000117 1000121' время в mсек= 12'выбор от 10000000 требуется чисел= 7 10000019 10000079 10000103 10000121 10000139 10000141 10000169 10000189' время в mсек= 0
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826034
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Бабуля, твой код - ужасен
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826046
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonБабуля, твой код - ужасен

спасибо за комплимент
просто мне хотелось проанализировать время нахождения ПРОСТЫХ чисел в произвольном диапазоне не применяя списка простых чисел
-----
а оформление --это вторично
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826078
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Мы уходим от первого сообщения топика.

Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.

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

Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.

А есть ли ещё простые числа, где этот тест не работает?тест Ферма работает для всех простых чисел :-)

читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинять
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826100
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)Gennadiy UsovМы уходим от первого сообщения топика.
Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.
А есть ли ещё простые числа, где этот тест не работает?тест Ферма работает для всех простых чисел :-)
читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинятьЧитайте сообщения внимательно.

Число 2047 тест Ферма "распознаёт" как простое число.
На самом деле, это число не является простым.

Спрашивается:
а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826102
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovМы уходим от первого сообщения топика.

Там говорится о следующем:
мне известно первое число 2047 (число Мерсенна), которое опровергает тест Ферма.
Далее есть куча чисел Мерсенна, где тест Ферма не работает.

А есть ли ещё простые числа, где этот тест не работает?
2047 --не простое число

в этом диапазоне пустые
\требуется чисел= \ 2039 \ 2053 \ 2063 \ 2069 \ 2081 \ 2083 \ 2087
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826108
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovkealon(Ruslan)пропущено...
тест Ферма работает для всех простых чисел :-)
читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинятьЧитайте сообщения внимательно.

Число 2047 тест Ферма "распознаёт" как простое число.
На самом деле, это число не является простым.

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

Неужели не знаете, что тест Ферма определил для чисел Мерсенна Мр (р-степень) простые числа для тех чисел Мр, у которых р - простое число.
А теперь посчитайте: сколько из чисел Мерсенна действительно являются простыми?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826128
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так что. Я проиграл бутылку Виски?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826131
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,

довольно много(37-- помечены м)
степень двойки минус 1меткаближайшее простое2-е простое31 31 37 63 м 67 71 127 127 131 255 м 257 263 511 (7*73) м 521 523 1023 м 1031 1033 2047 (23*89) м 2053 2063 4095 м 4099 4111 8191 8191 8209 16383 м 16411 16417 32767 м 32771 32779 65535 м 65537 65539 131071 131071 131101 262143 м 262147 262151 524287 524287 524309 1048575 м 1048583 1048589 2097151 м 2097169 2097211 4194303 м 4194319 4194329 8388607 м 8388617 8388619 16777215 м 16777259 16777289 33554431 м 33554467 33554473 67108863 м 67108879 67108913 134217727 м 134217757 134217773 268435455 м 268435459 268435463 536870911 м 536870923 536870951 1073741823 м 1073741827 1073741831
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826133
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonТак что. Я проиграл бутылку Виски?Выиграли!

Вы же спорили на то, что есть ещё такие числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826188
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Нашел в вики число 341=11*31.

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


На самом деле, будет несколько достаточных тестов простоты,
которые применяются к конкретному числу в зависимости от признаков этого числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826260
Фотография vikkiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
на малых числах можно или online таблицы использовать, или online app-сервера расчётов
у меня здесь https://rextester.com/live/QNKB4696
генерирует для всего диапазона/предела в 100 миллионов за <10 секунд
(предел сервера настроенный для пользовательской сессии)
а на домашнем за долю секунды, для 1млрд за от 2х до 20ти сек.,
на выделенном сервере будет ещё быстрее..

получилось количество праймов для предела в 1млрд = 50'847'534
т.е. 5% от верхней границы,
по желанию если таблица в базе становится тяжелой
то для ускорения (table scan) можно разнести по разным
(где логика будет определять с какой таблицей проводить сравнение)

здесь ещё ближайший можно проверить (в т.ч. и для 2^1024):
https://www.wolframalpha.com/input/?i=PrimeQ(2038074743)
https://www.wolframalpha.com/input/?i=PrimeQ(2^1024)
https://www.wolframalpha.com/input/?i=prime(100000000)
а по подписке у них и интеграция через API возможна.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826261
Фотография vikkiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
выше это в смысле ещё раз (надеюсь в последний) вклинюсь - вам шашечки или ехать?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826379
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В сообщении 21908030 говорилось о разложении всех простых чисел на подмножества.

За основу такого разложения можно взять тест Соловея – Штрассена.
https://ru.wikipedia.org/wiki

Если использовать в этом тесте привычную для нас степень 2, то получается следующие выражения:

Имеется число n.
Находим число m = (n – 1)/2
Тогда, если число простое, то
.

Далее тест предполагает рассмотреть другие степени, кроме 2, при этом число m является НОД между значением степени и n.

Получается несколько раундов, и если во многих раундах тест покажет, что число простое, то с этой вероятность число n будет простым.

Всё это создаёт массу вычислений, а также то, что есть вероятность того, что число n не является простым.
Попробуем этот тест доработать.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826407
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Рассматривается следующее изменение теста Соловея – Штрассена 21908306 :

Для степени 2 получается следующие выражения:

Имеется число n.
Находим число m = (n + 1)/2
И определяем число Р
.

Число Р принимает следующие значения:

а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа

б) Р = 1
В этом случае число n будет псевдопростым числом (тест Ферма данное число n определяет как простое число).

в) Р не равно ни 1, ни (n - 1).
В этом случае число n определяем как составное число.

На диапазоне от 1 до 200 данный достаточный тест определяет 26 простых чисел и 18 псевдопростых чисел.

И как следствие, с помощью этого достаточного теста можно точно определить простые числа на любом диапазоне, причем, очень быстро, с помощью одного вычисления по модулю.

Псевдопростые числа будут рассмотрены позднее.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826424
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа


3277, 29341, 49141, 80581, 88357, 104653, ...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826425
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Числа составные, 2 (n-1)/2 == n-1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826461
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа

3277, 29341, 49141, 80581, 88357, 104653, ...Спасибо за подсказку!

Просто у меня нет программы на большие числа.
Работаю в EXCEL, как все уже знают.

Буду рассматривать эту ветку.

Я её уже видел, но думал, что проскочит.
Не получилось.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826462
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вспоминается анекдот. ".... Женится тебе пора, барин".
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826465
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneЧисла составные, 2 (n-1)/2 == n-1Здесь я не понял.

Если n =15, то (n-1)/2 = 7
2^7 = 64

И как получается (n-1)?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826555
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneЧисла составные, 2 (n-1)/2 == n-1Здесь я не понял.

Если n =15, то (n-1)/2 = 7
2^7 = 64

И как получается (n-1)?Ну я там забыл взять остаток. Для 15 и не получается
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826576
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЗдесь я не понял.
Если n =15, то (n-1)/2 = 7
2^7 = 64
И как получается (n-1)?Ну я там забыл взять остаток. Для 15 и не получаетсяА для каких чисел получится?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826583
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone,

А если в сообщение 21908344 добавляется одна строчка в раздел а):

а) Р = n -1
В этом случае число n определяем как простое число.
При этом (n -1) не должно делиться на 6.
Это и есть достаточный тест для определения числа n как простого числа

Что тогда получается?

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 14.
Можно сказать, начинаем формировать первое подмножество простых чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826624
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarlone,

А если в сообщение 21908344 добавляется одна строчка в раздел а):

а) Р = n -1
В этом случае число n определяем как простое число.
При этом (n -1) не должно делиться на 6.
Это и есть достаточный тест для определения числа n как простого числа

Что тогда получается?

1678541, 1811573, 3400013, 3605429
Когда за дело берутся настоящие математики, у них получается лучше -
https://en.wikipedia.org/wiki/Baillie–PSW_primality_test
нет ни одного известного составного числа, походящего тест
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826677
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone,

спасибо за проведённые расчеты!

Кстати, интересная ситуация получается:

для -1 "ошибки варианта а)" начинаются с 3277,
а для +1 "ошибки варианта а)" начинаются с 1678541.

То есть, +1 и -1 не равнозначны!

Не нравится значение 3605429.
Может быть ошибка?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39826711
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarlone,
Не нравится значение 3605429.
Может быть ошибка?
python
Код: plaintext
1.
>>> pow(2,3605429//2,3605429)
3605428
все правильно
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39828988
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone,

Ещё один интересный вариант.

Если в сообщение 21908344 раздел а) будет выглядеть следующим образом:

а) Р = n -1
В этом случае число n определяем как простое число.
При этом Р должно быть простым числом.
Это и есть достаточный тест для определения числа n как простого числа

Что тогда получается?

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 10.
Можно сказать, начинаем формировать первое подмножество простых чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39828990
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Виноват, ошибся.
Надо делить на 2 и ....
Тогда сообщение будет выглядеть следующим образом:

"Barlone,

Ещё один интересный вариант.

Если в сообщение 21908344 раздел а) будет выглядеть следующим образом:

а) Р = n -1
В этом случае число n определяем как простое число.
При этом (n+1)/2-1 должно быть простым числом.
Это и есть достаточный тест для определения числа n как простого числа

Что тогда получается?

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 10.
Можно сказать, начинаем формировать первое подмножество простых чисел."
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39828991
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Или проще - (n-1)/2 - простое число.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39828992
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone,

Аналогично, можно рассмотреть новую версию для раздела б).

А если в сообщение 21908344 добавляются две строчки в раздел б):

б) Р = 1
В этом случае число n будет псевдопростым числом (тест Ферма данное число n определяет как простое число).

При этом (n-1)/2 должно быть простым числом.
Это и есть достаточный тест для определения числа n как простого числа



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

Я изучаю числа, и на основании эвристики делаю некоторые выводы.

Ещё раз напоминаю определение подмножества простых чисел 21908344 :

Имеется число n.
Находим число m = (n + 1)/2
Определяется число Р
.

Если:
число Р = n -1,
и (n1-1)/2 является простым числом, 21912575
то в этом случае число n определяем как простое число.

Это и есть достаточный тест для определения числа n как простого числа.


Следует помнить, что обратное положение (если (n-1)/ 2 – простое, то и n – простое) не всегда работает.

В диапазоне от 1 до 200 получаем следующее подмножество простых чисел, удовлетворяющих выше указанному определению:
11 (5), 59 (23), 107 (53), 179 (89),…

При этом отвергаются числа, показанные в 21908441 и в 21908732
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39829817
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 2 1024 , то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39829935
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 2 1024 , то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка Спасибо за сообщение о частном случае теста Люка!

Да, много простых чисел не рассматривается, но зато есть механизм определения подмножества простых чисел (где-то около 8% от общего количества простых чисел).

И зто гарантировано!

Осталось разобраться с простыми числами, для которых
Р = n -1.
и для которых нет простых чисел (n-1)/2.

И заодно определить простые числа (n-1)/2.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39830117
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 2 1024 , то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка Вот появился ещё один тест.

Но этот тест не упоминается в вики в разделе простые числа.
Получается, что по версии авторов раздела про простые числа этот тест не подходит для поиска простых чисел.

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

В сообщении 21914187 , которое говорит о достаточности для подмножества простых чисел,
основным камнем преткновения является простота чисел (n-1)/2.

Данная задача решается.

Имеется число n, которое больше 2^m и меньше 2^(m+1).

Тогда с помощью m вычислений по модулю можно определить: является ли число n простым числом.

Спрашивается: количество m вычислений по модулю не является слишком большим?
(с точки зрения проведения расчетов на компьютере в разумное время)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39830289
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Gennadiy UsovBarloneGennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 2 1024 , то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка Вот появился ещё один тест.
Но этот тест не упоминается в вики в разделе простые числа.
Получается, что по версии авторов раздела про простые числа этот тест не подходит для поиска простых чисел.
И спрашивается: почему?А тест Люка, оказывается, то же "неподъёмный" для больших чисел n.

Ведь надо найти все множители числа n - 1.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39841239
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone,

что означает данный оператор python ( не нашел описания по 4-м параметрам)Barlonepython
Код: plaintext
1.
>>> pow(2,3605429//2,3605429)
3605428
Он определяет простоту числа?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39841640
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarlone,

что означает данный оператор python ( не нашел описания по 4-м параметрам)Barlonepython
Код: plaintext
1.
>>> pow(2,3605429//2,3605429)
3605428
Он определяет простоту числа?Там три параметра, // - целочисленное деление
2 3605429/2 %3605429
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39841772
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneBarlonepython
Код: plaintext
1.
>>> pow(2,3605429//2,3605429)
3605428
Там три параметра, // - целочисленное деление
2 3605429/2 %3605429Спасибо!

Ещё вопрос:
а в python есть функция поиска простоты числа, или надо определять простоту числа обычным "дедовским" способом?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39841807
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть статья которая описывает библиотеку SymPy

https://www.geeksforgeeks.org/prime-functions-python-sympy/
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39842050
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonЕсть статья которая описывает библиотеку SymPy
https://www.geeksforgeeks.org/prime-functions-python-sympy/ Спасибо!

А как эту библиотеку подцепить к https://ideone.com/?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39842056
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм... да. Действительно Идеоновская сборка не знает эту библиотечку.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39843697
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Поскольку пока отсутствуют процедуры определения простоты числа для https://ideone.com/,
приходится обращаться к калькуляторам в "ручном режиме".

И то, только до 2^200.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39843789
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Продолжил построение различных множеств простых чисел.

В сообщениях 21908344 и 21913903 говорилось о построении одного из таких множеств.

Можно построить одно из подмножеств данного множества: простые числа после 2^198.

В результате за 0,7 секунд на компьютере определились 64 числа, большие 2^198 на следующие величины:

277, 693, 763, 1165, 1395, 1723, 2157, 2349, 2613, 3067, 3397, 3637, и т.д.

Эти числа проверены на факторизаторе чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39844469
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Так никто не ответил на первое сообщение топика:
"А кроме чисел Мерсенна есть ли ещё примеры «ошибочности» теста Ферма?"

Покопался в вики и нашел:
https://ru.wikipedia.org/wiki/Псевдопростое_число

Существует последовательность A001567 в https://oeis.org/A001567

где есть числа:
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681,
5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491,
15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341

2047 - число Мерсенна
3277, 29341 - из сообщения 21908370

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

Во многих науках решается не прямая задача (в нашем случае определение простых чисел),
а обратная задача - рассмотрение случаев "сбоев" в решении прямой задачи.

Например, есть тест Ферма, и у этого теста есть "сбои", пусть немного, но есть.
Что не позволяет "доверять" тесту Ферма для всех случаев.

Если получится понять поведение последовательности 21940432 ,
то задача определения простых чисел с помощью теста Ферма (и ещё чего-нибудь) будет решена.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39844918
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил сам определить последовательность чисел,
полученных в результате «ошибочности» теста Ферма.

За 4 сек. нашел 148 чисел из первых 500000 чисел, начиная с 1.
Шаг был, начиная с 1, сначала 4, затем 2, затем 4, и т.д.

Получилось, что при шаге 2 получилось 123 составных числа.
А при шаге 4 получилось 25 составных чисел.

В последовательности 21940432 рассматривались все нечётные числа.
В этом случае получается 172 составных числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39845430
ёёёёё
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone...RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.

Числа есть, а хранить их негде. Бардак.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39845452
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
ёёёёёBarlone...RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.Числа есть, а хранить их негде. Бардак.А зачем хранить?

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

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

Малые простые числа - не интересны. Их можно найти в реальное время.

Представляют интерес простые числа, связанные с криптографикой.

Поскольку на имеющихся ЭВМ, в реальное время, можно найти очень небольшое количество простых чисел,
"пригодных" для криптографии, то и воображаемая библиотека найденных больших простых чисел будет небольшой.

В реальности представляет интерес разработка программ,
позволяющих определять простые числа на "высоте" чисел 2^1024 или на "высоте" 2^2048.

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

Для начала - 21940591
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39847952
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonЕсть статья которая описывает библиотеку SymPy

https://www.geeksforgeeks.org/prime-functions-python-sympy/ Просьба: можно получить часть кода, где эта библиотека подключается.

Например, вместе с isprime (n)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39849420
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Важно рассмотреть ещё один вопрос.

В сообщении 21939419 говорилось о найденной последовательности простых чисел.

Допустим, на отрезке от 2^1023 до 2^1023 + 10000000 на домашнем компьютере за несколько минут
найдено несколько простых чисел.

Насколько полученная последовательность простых чисел может помочь
в решении задачи поиска простых чисел в районе 2^1024?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39849501
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Первые несколько штук (probable prime).

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39849572
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПервые несколько штук (probable prime).

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989

И сколько времени ушло на поиск этих чисел?
И с помощью какого теста простоты?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39849597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Несколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.

Но в JDK-11 как мне показалось поменялся исходных код этого теста. Я где-то привдил сорцы с 8 версии
там отчотливо был видел тест Люка в совокупности с Миллером. Сейчас я не дам гарантий. Надо смотреть и изучать.

Код: 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.
import java.math.BigInteger

object Main {

  def bigPower(x : Int, y : Int) : BigInt = {
    var product : BigInt = 1
    for(k <- 1 to y) {
      product = product * x
    }
    product
  }

  def main(arg : Array[String]) : Unit = {
    val x : BigInt = bigPower(2, 1023)
    var javaBigint = new BigInteger(x.toString(10))
    javaBigint = javaBigint.nextProbablePrime()
    do {
      javaBigint = javaBigint.nextProbablePrime()
      println(javaBigint)
      println(" ")
    } while(javaBigint.compareTo( x + BigInt(2000)) < 0) // while(javaBigInt < x + 2000) 

  }

}



Еще есть забавный косяк. Я написал за пару минут функцию bigPower для встроенного в Scala типа BigInt, полагая
что это бридж к java-шному BigInteger. Дальше обнаружил что bigInt не работает с функциями простоты и добавил
java-шный тип BigInteger. Поэтому в исходнике есть два разных типа от двух разных языков.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39849599
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Щас качнул снова зеркало исходников JDK чтоб посмотреть историю.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39849616
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Второте и третье число - близнецы кстати.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850019
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonНесколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.А есть ли такая же программа на питоне?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850524
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПервые несколько штук (probable prime).

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989

Было бы интереснее по другому представить информацию по поиску простых чисел (пример - 21939419 ):
в начале - исходное число, лучше в виде 2^1023 (именно так!),
а далее - разность между очередным простым числом и исходным числом.

Так более читаемо.
И можно зрительно отследить интервалы между найденными простыми числами.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850589
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonНесколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.А есть ли такая же программа на питоне?
Я не специалист в Питоне. Но я думаю что тест Люка и Ребе-Миллера там должен быть. И длинная арифметика должна тоже
быть.

Есть Питонщики?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850595
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.

Код: sql
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.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
518
282
78
1212
772
1298
826
212
654
258
750
22
264
1020
84
168
600
554
168
340
450
1190
1030
260
366
2094
3222
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850623
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.
Код: sql
1.
2.
3.
4.
5.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178

Насколько я понял, здесь показаны расстояния между числами.

В дальнейшем, было бы удобнее вести отсчет от первого числа, чтобы показать числовой ряд.

Например: 2^1023, 1155, 1463,1553, 1655,1833 и т.д.

или
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
428
530
708
1226 и тд.

Спасибо за информацию!
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850730
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В префиксном коде.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
(8(9(8(8(4(6(5(6(7(4(3(1(1(5(7(9(5(3(8(6(4(6(5(2(5(9(5(3(9(4(5(1(2(3(6(6(8(0(8(9(8(8(4(8(9(4(7(1(1(5(3(2(8(6(3
(6(7(1(5(0(4(0(5(7(8(8(6(6(3(3(7(9(0(2(7(5(0(4(8(1(5(6(6(3(5(4(2(3(8(6(6(1(2(0(3(7(6(8(0(1(0(5(6(0(0(5(6(9(3(9
(9(3(5(6(9(6(6(7(8(8(2(9(3(9(4(8(8(4(4(0(7(2(0(8(3(1(1(2(4(6(4(2(3(7(1(5(3(1(9(7(3(7(0(6(2(1(8(8(8(8(3(9(4(6(7
(1(2(4(3(2(7(4(2(6(3(8(1(5(1(1(0(9(8(0(0(6(2(3(0(4(7(0(5(9(7(2(6(5(4(1(4(7(6(0(4(2(5(0(2(8(8(4(4(1(9(0(7(5(3(4
(1(1(7(1(2(3(1(4(4(0(7(3(6(9(5(6(5(5(5(2(7(0(4(1(3(6(1(8(5(8(1(6(7(5(2(5(5(3(4(2(2(9(3(1(4(9(1(1(9(9(7(3(6(2(2
(9(6(9(2(3(9(8(5(8(1(5(2(4(1(7(6(7(8(1(6(4(8(1(2(1(1(2(0(7(0(1(0(1)9(1))2(9(3))4(7(1))9(8(9)))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850789
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
518
282
78  и т.д

Но это всё числа, полученные с помощью теста Ферма.

А если среди них есть составные числа, как иногда бывает с тестом Ферма?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850804
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не знаю. Как это проверить?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850812
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Исходный код который (предположительно) работает. Я использую JDK-11.
Исходники брал от OpenJDK. Текущая версия мастер-бранча примерно ей
соответсвует. Я говорю это просто просмотрев активность по изменениям
в модуле BigInteger. Этот модуль стабилен и менялся редко. Особенно в части алгоритма.
Основную его (ядерную часть) закоммитил некто Duke в 2007 году.

Я кажется уже где-то его постил. Запощу еще раз.

Специально для вас прокомментирую. Текущее число это "this". Это функция которая проверяет
объект (метод объекта). Поэтому если вы проверяете число к пример 1999987 то
следует читать this.add(ONE) как 1999987 + ONE или 1999987 + 1.

Здесь ONE, TWO просто константы типа длинное целое. Такой вот он некрасивый язык Java при работе
с объектными (не примитивными) типами.


Код: 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.
    public BigInteger nextProbablePrime() {
        if (this.signum < 0)
            throw new ArithmeticException("start < 0: " + this);

        // Handle trivial cases
        if ((this.signum == 0) || this.equals(ONE))
            return TWO;

        BigInteger result = this.add(ONE);

        // Fastpath for small numbers
        if (result.bitLength() < SMALL_PRIME_THRESHOLD) {

            // Ensure an odd number
            if (!result.testBit(0))
                result = result.add(ONE);

            while (true) {
                // Do cheap "pre-test" if applicable
                if (result.bitLength() > 6) {
                    long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
                    if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
                        (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
                        (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                        result = result.add(TWO);
                        continue; // Candidate is composite; try another
                    }
                }

                // All candidates of bitLength 2 and 3 are prime by this point
                if (result.bitLength() < 4)
                    return result;

                // The expensive test
                if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                    return result;

                result = result.add(TWO);
            }
        }


Код: 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.
    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
Ещё раз о тесте Ферма
    #39850813
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Полностью исходники (зеркало) OpenJDK можно скачать здесь https://github.com/unofficial-openjdk/openjdk
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850814
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В код также забито много некрасивых и математически неясных "гвоздей".
Это связано с тем что создатели этого BitInteger беспокоились лишь о том
чтобы код работал быстро. Ясность чтения исходника их не беспокоила.

Вот данное выражение

Код: java
1.
result.bitLength() > 6



следует читать так.

Если переменная result имеет разрядную сетку больше чем 6 бит. По сути 6 бит это число более чем 64.
Еще аналог - целое логарифмирование по основанию 2.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850859
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В питоне запустил программу по поиску составных чисел, удовлетворяющих тесту Ферма.

Рассмотрено 10 000 007 чисел.

Из них - 664575 простых чисел.

Тесту Ферма удовлетворяют 685 составных чисел.

Где-то 1 : 100

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

Вобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса. Потом Миллера Раввина в пересечечии с Люка-Лемьером. Причем идет
пересеченеи условий. Необходимое - Миллер. Достаточное - Люка. Насколько я понимаю
здесь должен быть 100% детерминимзм. Не зря они сетку ограничивали.

Если разрядность числа выше 95 бит то дальше создается битовое решето (BitSieve). Как оно работает
в данном алгоритме я не изучал. Что это за метод? Эратосфен или нет не знаю.

Алгоритм искусственно останавливается когда разрядная решетка достигает 500000000 бит и выдает ошибку.
Это ограничение было введено в 2013 году.

Далее эта формула.

Код: sql
1.
int searchLen = getPrimeSearchLen(result.bitLength());



Это что-то типа шага по решетке. Вычисляется как bitLength / 20 * 64.



Код: 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.
    public BigInteger nextProbablePrime() {
        if (this.signum < 0)
            throw new ArithmeticException("start < 0: " + this);

        // Handle trivial cases
        if ((this.signum == 0) || this.equals(ONE))
            return TWO;

        BigInteger result = this.add(ONE);

        // Fastpath for small numbers
        if (result.bitLength() < SMALL_PRIME_THRESHOLD) {

            // Ensure an odd number
            if (!result.testBit(0))
                result = result.add(ONE);

            while (true) {
                // Do cheap "pre-test" if applicable
                if (result.bitLength() > 6) {
                    long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
                    if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
                        (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
                        (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                        result = result.add(TWO);
                        continue; // Candidate is composite; try another
                    }
                }

                // All candidates of bitLength 2 and 3 are prime by this point
                if (result.bitLength() < 4)
                    return result;

                // The expensive test
                if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                    return result;

                result = result.add(TWO);
            }
        }

        // Start at previous even number
        if (result.testBit(0))
            result = result.subtract(ONE);

        // Looking for the next large prime
        int searchLen = getPrimeSearchLen(result.bitLength());

        while (true) {
           BitSieve searchSieve = new BitSieve(result, searchLen);
           BigInteger candidate = searchSieve.retrieve(result,
                                                 DEFAULT_PRIME_CERTAINTY, null);
           if (candidate != null)
               return candidate;
           result = result.add(BigInteger.valueOf(2 * searchLen));
        }
    }

...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850899
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonТак я самый первый исходник не до конца скопипастил.
Вобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса. Потом Миллера Раввина в пересечечии с Люка-Лемьером. Причем идет
пересеченеи условий. Необходимое - Миллер. Достаточное - Люка. Насколько я понимаю
здесь должен быть 100% детерминимзм. Не зря они сетку ограничивали.
Если разрядность числа выше 95 бит то дальше создается битовое решето (BitSieve). Как оно работает
в данном алгоритме я не изучал. Что это за метод? Эратосфен или нет не знаю.
Алгоритм искусственно останавливается когда разрядная решетка достигает 500000000 бит и выдает ошибку.
Это ограничение было введено в 2013 году.Я так понимаю, что есть интерес разобраться с диапазоном целых чисел.

А задача будет выглядеть так:

На произвольном диапазоне определить простые числа
(или определить составные числа из определённой последовательности целых чисел).


Если рассматривать такую задачу, то необходимо задачу разделить на подзадачи, и рассматривать постепенно эти подзадачи.

Подзадача 1. Выбор последовательности целых чисел.

Возможны следующие варианты:
- нечётные числа;
- числа 6К+-1
- числа из блоков 21812001 :30, 210, 2310, и т.д.
(о таких блоках известно из вики, при этом считается,
что блок 210 и более не несёт существеного убыстрения работы программы)

То есть, такими блоками ограничивается количества перебираемых целых чисел.

Я использовал в 21952070 2-й вариант
Код: sql
1.
2.
3.
4.
5.
6.
d = 2							
p = 7							
P = p + 1000000							
while p <= P: 							
	d = 6 - d						
	p = p + d
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850902
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не особо. Я просто комментирую то как nextPrime уже реализован в языковых библиотеках.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850904
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonНе особо. Я просто комментирую то как nextPrime уже реализован в языковых библиотеках..... и пишу простенькие программы в порядке комментария
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39850912
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Меня интересовал Radix tree/trie. И всякие сжатые форматы хранения аналитики.

А простые числа просто под руку подвернулись.
Как хороший источник шума со свойствами.

Вот такой вот загадочный мотиватор.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39851900
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В продолжение сообщения 21952153 привожу код по перебору целых чисел с помощью массива
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
my_list = [30, 8, 1, 7, 11, 13, 17, 19, 23, 29]	
nm = my_list [0]		
em = my_list [1] - 1		
p0 = 0		
w = 0		
P = 10000007		
w1 = P//nm		
while w <= w1:		
	we = 1	
	we1 = we + em	
	while we <= we1:	
		p = p0 + (w-1) * nm +my_list [we + 1]
		
		we += 1
	w += 1	
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39851904
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonВобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса. Вопрос:

а зачем нам нужны числа, меньше SMALL_PRIME_THRESHOLD (95 бит)?

Например, факторизатор "Империя чисел" работает с числами 10^60
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39851944
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonВобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса. Вопрос:

а зачем нам нужны числа, меньше SMALL_PRIME_THRESHOLD (95 бит)?

Например, факторизатор "Империя чисел" работает с числами 10^60
Не знаю. Могу предположить что эта точка была выбрана на графике экспериментально.
Эта точка делит множество чисел на два направления. Первое - это брутфорс + миллер-рабин + люка лемьер.
Второе это Решето неизвестного типа. Экперимент мог заключаться в выборе наименьшего времени отклика.
Там где два графика отклика пересеклись - там и взяли эту точку. Поскольку Люка Лемьер как самый главный
точный и детерминированный алгоритм имеет комплексность порядка O(n^3) то график мог вырасти быстро
до времени неприемлимого для человеческого ожидания.

Хотя... могли брать по другому принципу.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39851948
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovНапример, факторизатор "Империя чисел" работает с числами 10^60
Что такое империя чисел - понятия не имею. Не слыхал. Сколько она потребляет памяти.
И каких вычислительных ресурсов ей надо. Может ей нужен дата-центр с 1000 процессорами
и пета-байтом кеша расчётных чисел. Можем ли мы это применить в быту? Или в рамках наших
скромных задач на sql.ru?

И не забывайте что факторизация и тест на простоту это всё-таки не совсем одно и то-же.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39851970
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovНапример, факторизатор "Империя чисел" работает с числами 10^60
Что такое империя чисел - понятия не имею. Не слыхал. Сколько она потребляет памяти.
И каких вычислительных ресурсов ей надо. Может ей нужен дата-центр с 1000 процессорами
и пета-байтом кеша расчётных чисел. Можем ли мы это применить в быту? Или в рамках наших
скромных задач на sql.ru?Факторизатор "Империя чисел" - это :
https://ru.numberempire.com/

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

Что такое империя чисел - понятия не имею. Не слыхал. Сколько она потребляет памяти.
И каких вычислительных ресурсов ей надо. Может ей нужен дата-центр с 1000 процессорами
и пета-байтом кеша расчётных чисел. Можем ли мы это применить в быту? Или в рамках наших
скромных задач на sql.ru?Факторизатор "Империя чисел" - это :
https://ru.numberempire.com/

Этот факторизатор удобен только для отдельных чисел.maytonИ не забывайте что факторизация и тест на простоту это всё-таки не совсем одно и то-же.Но у них общие "корни".
Ну ты видел что поиск следующего простого содержит как минимум бутерброд из 4х разных алгоритмов?

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

Скорее всего, здесь имеет место скорость вычислений: когда удобно так, а когда удобнее этак.

Сейчас попробую проверить на 1000... повторных вычислений скорость определения:
- остатка по тесту Ферма для большого числа
- остатка после деления этого большого числа на серию произвольных чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39851986
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonИ не забывайте что факторизация и тест на простоту это всё-таки не совсем одно и то-же.Но у них общие "корни".
maytonНу ты видел что поиск следующего простого содержит как минимум бутерброд из 4х разных алгоритмов?
Зачем ты говоришь про общие корни? Как мы твои корни натянем на эту практическую реализацию.
Я понимаю ты идеалист. Я тебе еще в ферзевой задаче говорил что мы должны подходить очень
селективно к алгоритму основываясь на разной природе входных данных. Серебрянной пули не будет.
У нас будет десяток бронзовых пуль каждая из которых хорошо работает в данном диапазоне чисел
или ферзей или вектора входных данных и очень-очень плохо работаает на другом векторе входа.А кто сказал, что будет один алгоритм?

Для поиска простых чисел и факторизации чисел используются одни и те же алгоритмы.

Или разные?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39851997
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Рабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852011
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonРабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.А если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852019
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonРабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.А если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.
Геннадий. Я вас уже считаю разработчиком. Читайте код. Последний делитель который мы делим методом грубой силы это число 41.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
 while (true) {
                // Do cheap "pre-test" if applicable
                if (result.bitLength() > 6) {
                    long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
                    if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
                        (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
                        (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                        result = result.add(TWO);
                        continue; // Candidate is composite; try another
                    }
                }

                // All candidates of bitLength 2 and 3 are prime by this point
                if (result.bitLength() < 4)
                    return result;

                // The expensive test
                if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                    return result;

                result = result.add(TWO);
            }
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852027
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovА если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.
Геннадий. Я вас уже считаю разработчиком. Читайте код. Последний делитель который мы делим методом грубой силы это число 41.
Спасибо за доверие!

А почему 41, а не 43, а не 61, а не ....?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852058
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил сравнить время на проведение операция для большого числа в двух вариантах:
- тест Ферма
- деление на множество делителей.

Получилось, что за 3 сек. можно найти для числа p = pow(2, 1023) + 345 :
- 1000 тестов Ферма
- 5 000 000 делений на делители.

Получилось, что за 3 сек. можно найти для другого числа p = pow(2, 2023) + 89 :
- 150 тестов Ферма
- 3 000 000 делений на делители.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852314
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovmaytonпропущено...

Геннадий. Я вас уже считаю разработчиком. Читайте код. Последний делитель который мы делим методом грубой силы это число 41.
Спасибо за доверие!

А почему 41, а не 43, а не 61, а не ....?

Я всё таки еще упрощу этот цикл. Как я уже говорил Java не годится для работы с длинными целыми. Разверну эти
толстые функции типа reminder. Под капотом у нее бутерброд из двух алгоритмов remainderKnuth и remainderBurnikelZiegler.
Надеюсь это просто какие-то оптимизации быстрого остатка от деления. Первый из них носит гордую фамилию Кнута.
Это радует.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
 while (true) {
                // Do cheap "pre-test" if applicable
                if (result.bitLength() > 6) {
                    long r = result % (3*5*7*11*13*17*19*23*29*31*37*41);
                    if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
                        (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
                        (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                        result = result.add(TWO);
                        continue; // Candidate is composite; try another
                    }
                }

                // All candidates of bitLength 2 and 3 are prime by this point
                if (result.bitLength() < 4)
                    return result;

                // The expensive test (здесь Миллер-Раввин и Люка Лемьер)
                if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                    return result;

                result = result.add(TWO);
            }
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852331
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovА почему 41, а не 43, а не 61, а не ....?Я всё таки еще упрощу этот цикл. Как я уже говорил Java не годится для работы с длинными целыми. Разверну эти
толстые функции типа reminder. Под капотом у нее бутерброд из двух алгоритмов remainderKnuth и remainderBurnikelZiegler.
Надеюсь это просто какие-то оптимизации быстрого остатка от деления. Первый из них носит гордую фамилию Кнута.
Это радует.Вы не ответили на вопрос: почему последнее простое число 41.

Я попробую представить свой вариант части кода (начало цикла, остальное - в зависимости от применения)
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
#p - исходное число			
prost_list = [23,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]			
s1 = 1			
sn = prost_list[0]			
while s1 <= sn:			
	q = prost_list[s1]		
	w2 = p % q		
		if w2 == 0:	
			 и т.д.

Количество простых чисел в массиве можно увеличить
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852334
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я не знаю почему 41. Я просто разворачиваю вложенность сорца и представляю его на суд в форуме
в читабельном виде.

Предположительно это другая экспериментальная константа которая была забита в код на основании
замеров времени как оптимум.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852352
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПотом Миллера Раввина в пересечечии с Люка-Лемьером. Причем идет
пересеченеи условий. Необходимое - Миллер. Достаточное - Люка. Насколько я понимаю
здесь должен быть 100% детерминимзм. Не зря они сетку ограничивали.В вики записано:

"Тест Люка — Лемера — полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез)
тест простоты для чисел Мерсенна ."
(или для чисел, расположенных рядом с числами Мерсенна)

Для остальных чисел этот тест не подходит.

Если это не так, то приведите пример, желательно, на небольших числах.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852409
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я не буду спорить с википедией. Просто приведу исходник.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
    /**
     * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
     *
     * The following assumptions are made:
     * This BigInteger is a positive, odd number.
     */
    private boolean passesLucasLehmer() {
        BigInteger thisPlusOne = this.add(ONE);

        // Step 1
        int d = 5;
        while (jacobiSymbol(d, this) != -1) {
            // 5, -7, 9, -11, ...
            d = (d < 0) ? Math.abs(d)+2 : -(d+2);
        }

        // Step 2
        BigInteger u = lucasLehmerSequence(d, thisPlusOne, this);

        // Step 3
        return u.mod(this).equals(ZERO);
    }
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852465
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Тут дело не в программе.

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

А как для произвольного числа определить эту степень 2 ?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852497
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не знаю.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852537
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852554
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По сорцам Люка параметризуется неким загадочным Символом Якоби.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852562
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я нарисую блок-схему. Для Геннадия и для себя тоже.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852587
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нет в символе Якоби ничего загадочного. Это обобщение символа Лежандра на составные числа, и для простых чисел они совпадают.
Только вычисляют его (Якоби) не по определению, где нужно разложение на простые, а через квадратичный закон взаимности.
Для простого модуля символ Якоби позволяет определить, является ли какое-то число квадратичным вычетом по этому модулю, то есть существует ли квадратный корень из числа по модулю. (Например, 2 - квадратичный вычет по модулю 7, так как 3*3 mod 7 == 2)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852678
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneТестов много разных...
https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа А данный тест очень интересный.

Имеется два теста: тест Ферма и тест Люка (не тест Люка — Лемера).

С помощью каждого из этих тестов определяются все простые числа и ещё несколько составных чисел.
Причем, для каждого теста составные числа различные.
В вики:
"Мощность теста состоит в том, что не существует известных пересечений списков псевдопростых чисел Ферма и псевдопростых чисел Люка."

Осталось понять: для каких чисел тесты будут разными.
Если тесты разные, то число составное.

Поскольку привычно работать с тестом Ферма,
то сначала находится число, удовлетворяющее тесту Ферма,
а затем это число проверяется на тест Люка.

Далее осталось найти пример работы теста Люка.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852697
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Однако, интерес к этому тесту поубавился.

Числа Люка - Vn = { 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... } , это очень малая часть нечётных чисел.

Получается, что можно проверить только отдельные числа.

Кроме того, для очень больших чисел невозможно (нужно очень много времени) найти последовательность чисел Люка
- эти числа определяются от первого числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852809
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovПолучается, что можно проверить только отдельные числа.
Не так. Последовательность Люка используется для проверки произвольного числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852830
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovПолучается, что можно проверить только отдельные числа.
Не так. Последовательность Люка используется для проверки произвольного числа.Имеется последовательность Люка:
Числа Люка - Vn = { 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... } ,

Следовательно, в эту последовательность не попадают числа 101, 103, и т.д.
То есть, не все числа можно проверить.

Или я ошибаюсь?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852955
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Множество ненулевых остатков (вычетов) по модулю простого числа N - абелева группа порядка N-1. Что проверяет тест Ферма? Он проверяет, что порядок подгруппы, порожденной некоторым выбранным элементом, делит N-1. Когда он дает ложноположительный результат? Если N составное, то порядок группы будет φ(N). А порядок подгруппы, порожденной неким элементом, будет делителем φ(N). И тест Ферма сфейлится, когда этот делитель φ(N) окажется также и делителем N-1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852958
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
А такой вопрос:

есть простое число N, для которого получаем (N - 1) значений теста Ферма.
Эти числа различны или нет?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852960
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кроме мультипликативной группы вычетов по модулю, можно сконструировать и всякие другие группы - матрицы (но она на Абелева - умножение матриц не коммутативно), полиномы, точки на эллиптической кривой , решения уравнения Пелля
Коэффициенты всех этих матриц, полиномов, … можно брать по модулю числа N. И можно несколькими способами сконструировать группу, порядок которой для простого N будет N+1. И вот тут я не совсем уверен, но кажется, тест Люка проверяет, что порядок некой подгруппы такой группы делит N+1.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852963
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА такой вопрос:

есть простое число N, для которого получаем (N - 1) значений теста Ферма.
Эти числа различны или нет?Для простого N естественно все значения будут 1. Для составного будет 1, если порядок подгруппы делит N-1, и не 1, если не делит :)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852968
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот смотрите: 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. И тест фейлится.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852971
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Наверное, я не так сформулировал задачу.

Имелось в виду числа от 2^1 % 65 до 2^64 % 65.
Это тоже группа?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852973
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А, да, φ(65) = 4 * 12 = 48. Кажется, всегда, когда для составного N НОД(φ(N), N-1) > 2 можно найти значение, на котором тест Ферма сфейлится. (Но это не точно, в смысле доказать я сейчас не смогу).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852975
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovНаверное, я не так сформулировал задачу.

Имелось в виду числа от 2^1 % 65 до 2^64 % 65.
Это тоже группа?Ну так их же 4 всего разных.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852977
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ой, не то написал
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852978
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
А если числа от от 2^1 % 59 до 2^58 % 59,
то числа будут разные?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852980
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Для двойки (и любого другого числа по модулю 65) порядок группы будет каким-то делителем 48. Если этот делитель будет кратен 3, то он не делит 64, и тест Ферма покажет, что число составное. А если делитель не кратен трем, то в данном случае он будет также делителем 64.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852982
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА если числа от от 2^1 % 59 до 2^58 % 59,
то числа будут разные? не обязательно
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39852983
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Порядок подгруппы может оказаться делителем N-1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #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
Ещё раз о тесте Ферма
    #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
Ещё раз о тесте Ферма
    #39853574
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853575
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПолистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)Схема красивая!

14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?

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

При таком раскладе Миллер+Люка будут выгоднее. Никто не хочет ждать годы для проверки числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853577
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?
Алгоритм - перед вами. Реверс-инжинеринг - это процесс извлечения алгоритма из кода.
Он - тоже работает. А вот за уточняющими вопросами типа показателей степени надо
читать книжки. Я так думаю.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853621
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovПри этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).Ерунду вы написали. Вообще-то, если в математической формуле написано "a эквивалентно минус единице по модулю N" (значок такой ≡ из трех черточек), то в программе это будет выглядеть как "a % N == N-1", потому что -1 и N-1 попадают в один класс эквивалентности по модулю N.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853622
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Возьмем например простое число N=13, N-1 = 4*3. d=3, s=2
Взяв a=3, получим 2^3 % 13 == 1 - выполнилось первое условие.
Взяв a=10, получим 10^3 % 13 == 12 это минус единица :) и тут сразу выполнилось второе условие, при r==0.
Взяв а=2, получим 2^3 %13 == 8. Надо возводить в квадрат. 8^2 % 13 == 12 вот она минус единица при r==1.

А если у нас составное число, например N=21, N-1 = 4*5, d=5, s=2
Берем а=8, 8^5 % 21 == 8. Первое не выполнено. Берем квадрат 8^2 % 21 == 1. И второе условие не выполнено, значит число составное.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853623
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Последний случай кстати самый интересный - когда для какого-то числа а ≠ ±1 mod N оказывается что a² ≡ 1 mod N , то gcd(a+1, N) и gcd(a-1, N) дадут нам делители N.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853636
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853640
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonПолистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)Схема красивая!

14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?ты же сам ответ дал 21957011
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853678
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)Gennadiy Usov14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?
Все эти тесты использовать?
Или всё-таки остановиться на некоторых?ты же сам ответ дал 21957011 Спасибо, что нашли мою цитату!

Но эта цитата только о " псевдопростых или вероятностно простых" числах.

Нам же нужно повысить степень, так называемой, "псевдопростоты",
которая должна, по каким-нибудь своим законам, стремиться к простоте.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853685
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarlonemaytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m Но это очень сложно.

Чтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!

То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853702
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarlonemaytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m
ОК. Спасибо. Может вы знаете готовую имплементацию подобного метода nextProbablePrime для Python?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853749
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЧтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!

То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!Ага, и чтобы повести тест Ферма для этого числа, надо посчитать а (21024 -2) но это же не значит, что нужно 2 1024 -3 умножений на а.

BarloneЕстественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853848
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЧтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!Ага, и чтобы повести тест Ферма для этого числа, надо посчитать а (21024 -2) но это же не значит, что нужно 2 1024 -3 умножений на а.
BarloneЕстественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m Если я правильно понял, числа V 2^1024-1 и U 2^1024-1 нужно разложить на V и U.
А эти V и U разложить на следующие V и U. И т.д.

И сколько будет чисел в этой цепочке, пока мы не "дойдём" до вычисляемых чисел Люка?

Кстати, хорошо делить число, когда оно чётное. А если очередное число нечётное?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853856
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,
да всё так же, как с возведением в степень
Из U1,V1 получаем U2,V2, из них U4,V4, … и дальше по степеням двойки. Ну и по двоичному представлению нужного значения собираем результат - например, комбинируя пару U1,V1 c U4,V4 - получим U5,V5.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853860
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Формулы есть в английской вики
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853876
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Спасибо за программу!

Есть, правда одно ограничение:
maximum requested number of decimal places of 2 ** MP-1 #

Это ограничение для Python?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853882
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не знаю. Давайте Python-специфичные вопросы задавать тут https://www.sql.ru/forum/php-perl
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853888
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonВот Люка-Лемер на Питоне. https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Запустил программу на своём стареньком компьютере (лет 10), и нашел все числа Мерсенна до 9941 где-то за 40 минут.

Перед этим запустил программу с тестом Миллера-Рабина, и оказалось, что этот тест хорошо подходит для определения чисел Мерсенна.
На своём стареньком компьютере нашел все числа Мерсенна до 9941 где-то за 2 часа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853893
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
from sys import stdout
from math import sqrt, log
 
def is_prime ( p ):
  if p == 2: return True # Lucas-Lehmer test only works on odd primes
  elif p <= 1 or p % 2 == 0: return False
  else:
    for i in range(3, int(sqrt(p))+1, 2 ): 
      if p % i == 0: return False
    return True



Это знакомый мне фрагмент. Это брут-форс. Самый медленный и бестолковый алгоритм.
Мы с Димой его оптимизировали его добавляя переменный шаг.


Код: plaintext
1.
2.
3.
4.
5.
       uint64_t step = 4;
        

        for (uint64_t c1 = min_prime; c1 <= max_prime; c1 += step) {
                step^=0x0006;



На первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853901
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853904
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonНа первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.Я уже приводил чередование 4 и 2 21952153 .

Накопление простых в массиве может когда-то прекратиться.(на больших числах)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853906
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonНа первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.Я уже приводил чередование 4 и 2 21952153 .

Накопление простых в массиве может когда-то прекратиться.(на больших числах)
А тебе много и не надо. Накопи простых хотя-бы тыщу. Большая часть делителей
отбивается на самых ранних шагах.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853909
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВ своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.
Лучше переиначить алгоритм чтобы вместо извлечения корня было возведение в квадрат. Умножение намного быстрее происходит.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853920
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Согласен. Кстати я бы поднял отдельный топик. Быстрое умножение и быстрое возведение в квадрат
для arbitary precision. Просто для того чтобы провести ревизию текущих API и библиотек. Используют
они эти методы или нет.

А то меня терзают смутные сомнения.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853975
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonСогласен. Кстати я бы поднял отдельный топик. Быстрое умножение и быстрое возведение в квадрат
для arbitary precision. Просто для того чтобы провести ревизию текущих API и библиотек. Используют
они эти методы или нет.

А то меня терзают смутные сомнения. https://ru.wikipedia.org/wiki/Умножение_Карацубы
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39853987
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovЯ уже приводил чередование 4 и 2 21952153 .
Накопление простых в массиве может когда-то прекратиться.(на больших числах)А тебе много и не надо. Накопи простых хотя-бы тыщу.
Большая часть делителей отбивается на самых ранних шагах.Можно применить "ленивый алгоритм накопленных простых чисел".
О нём уже было сказано 21954752 .
Поскольку там ошибка, привожу ещё раз (без ошибки)
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
#p - исходное число			
prost_list = [22,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]			
s1 = 1			
sn = prost_list[0]			
while s1 <= sn:			
	q = prost_list[s1]		
	w2 = p % q		
		if w2 == 0:	
			 и т.д.

В массив можно записать хоть 1000 чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854157
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почему 22 ?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854160
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854163
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПочему 22 ?Очень удобно в одном массиве в ячейке [0] помещать длину массива данных,
и "работать" с массивом, начиная с ячейки [1].

Мы ведь привыкли считать: 1,2,,,,,,n,
а не 0,1,2,,,,,(n-1)

И притом, нужна будет отдельная переменная для хранения количества данных в массиве.

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

Длину массива берут так.
Код: python
1.
2.
3.
4.
>>> prost_list = [22,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]
>>> len(prost_list)
23
>>>


Только в интенсивных циклах я-бы все равно поместил это число в отдельную переменную.
Просто так и яснее и не будет потенциальных проблем с перформансом. Мы ведь не знаем
как дорого для питона стоит эта операция взятия длины. Для С++ ASCIIZ-массивов она стоила
линейно от длины самой строчки. Тоесть чем длиннее строка тем дольше ждать.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854344
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил ещё раз поработать с тестом Миллера-Рабина с точки зрения:
какой перечень остатков выдаёт этот тест.

Пока поработал с числами до 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 не подходит.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854382
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,

Выпишите несколько табличек для разных простых n: в первый столбец все числа от 1 до n-1, а в строку их степени по модулю n.
Например для 5 так
Код: plaintext
1.
2.
3.
4.
1 1 1 1 1
2 4 3 1 2
3 4 2 1 3
4 1 4 1 4 
Почитайте про первообразный корень .

А потом выпишите такую же табличку для составного числа. Только надо как-то еще мелкими циферками в каждую клеточку дописать остатки по каждому сомножителю этого числа. Прочитайте про китайскую теорему об остатках .
А чтобы понять, как получаются псевдопростые, надо сделать такую табличку для составного числа, у которого большой НОД(φ(n), n-1). Ну например 91=7*13, НОД(90, 72)=18. Правда, табличка большая получится, но если над ней помедитировать, то озарение обязательно придет.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854393
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone,

Вопрос не в том, как получаются псевдопростые числа.

Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.

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

Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854398
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarlone,

Вопрос не в том, как получаются псевдопростые числа.

Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.Вопрос как раз в том, как получаются псевдопростые.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854400
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854441
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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 тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)С удовольствием прочитаю.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854454
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovУвеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример - 21956300 ),
из-за которых эти числа принимаются тестом как простые.Не так это работает. Каждый раунд говорит либо "число точно составное", либо "не уверен, может быть простым." Если хотя бы один из раундов сказал, что число точно составное - то оно таки составное.
А чтобы доказать, что число простое, надо очень много раундов, порядка log(n) - это уже детерминированный вариант теста.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854455
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,

Ты как то по своему понял смысл раунда.
Там нет голосования. Там - право вето.

Первый раунд который детектировал составное - отменяет все результаты до этого.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854470
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
У меня 2 вопроса ( с учетом примера 21956300 ) для чисел 2047 и 2053:

Пока для первого условия теста Миллера-Рабина:

для числа 2047 (составное) после нескольких раундов (выбор случайного числа) появляется 1.
Это означает, что число 2047 псевдопростое?

для числа 2053 (простое) в течении нескольких раундов (выбор случайного числа) не будет появляться 1.
Это означает, что число 2053 составное?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854621
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил "отбросить" поиск случайного числа для первого условия теста Миллера-Рабина
и заменил этот поиск на перебор вариантов от 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).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854625
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ошибся.
пункт 3 предыдущего сообщения надо читать так:

3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается иногда 1.
В разных числах 1, 2, 5 значений.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854745
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я давно наблюдаю за форумом. И заметил что программисты очень не любят читать прозу.
Зато исходник вызывает у них живой интерес. Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.

Поэтому код с комментариями эффективнее чем просто текст который все не поняли
или интерпретировали по разному. Вот такие они... программисты.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854748
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonЯ давно наблюдаю за форумом. И заметил что программисты очень не любят читать прозу.
Зато исходник вызывает у них живой интерес. Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.
Поэтому код с комментариями эффективнее чем просто текст который все не поняли
или интерпретировали по разному. Вот такие они... программисты.А как они пишут новую программу?

По другому коду или по алгоритму?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854753
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не могу сказать. Это очень творческий процесс. Впрочем как и всё чем мы тут занимаемся.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854855
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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.
import random					
import math					
aaa1 = 0					
aaa2 = 0					
p =5					
P = p + 110					
while p <=P:					
	print (p)				
	t = p - 1				
	s = 0				
	while (t % 2 == 0):				
		t //= 2;			
		s += 1;			
	t1 = t//1				
	y = math.log( p )				
	#print (t,s)				
	y1 = 2				
	while y1 <= p-2:				
		#c = random.randint(2, p-2)			
		#print (c,y1)			
		x = pow(y1, t1, p)			
		print ("y",x,t1,y1)			
		y1 +=1			
	p +=2		
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854899
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov
Код: python
1.
2.
3.
	y = math.log( p )				

		x = pow(y1, t1, p)			


Мне кажется тут ослаблен контроль над типами. Кажется что натуральный логарифм и степень
возвращают число с плавающей точкой. А это не очень согласуется с решаемой задачей где
везде и всегда будут целые числа произвольной точности (arbitrary precision).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854903
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почитал Википедию.

Этот исходник 21954899 - это не Люка-Лемьер.

Это Люка-Лемьер-Ризель (LLT) предположительно. Поэтому все что я писал надо читать с поправкой по этому названию.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854930
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonЕсли ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.Для сообщения 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.
import random					
import math					
aaa1 = 0					
aaa2 = 0					
p =5					
P = p + 110					
while p <=P:					
	print (p)				
	t = p - 1				
	s = 0				
	while (t % 2 == 0):				
		t //= 2;			
		s += 1;			
	t1 = t//1				
	y = math.log( p )				
	#print (t,s)				
	y1 = 2				
	while y1 <= p-2:				
		#c = random.randint(2, p-2)			
		#print (c,y1)			
		x = pow(y1, t1, p)			
		print ("y",x,t1,y1)			
		y1 +=1			
	p +=2		

Код недоделанный.
После x = pow(y1, t1, p) надо еще
Код: plaintext
1.
2.
z = 0
while z < s and x != 1 and x != p-1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854931
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x = x*x % p
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854932
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Недописанное ушло, 2 раза
Код: plaintext
1.
2.
3.
4.
z = 0
while z < s and x != 1 and x != p-1
   x = x*x % p 
   z = z + 1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855147
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneКод недоделанный.
После x = pow(y1, t1, p) надо еще
Код: plaintext
1.
2.
3.
4.
z = 0
while z < s and x != 1 and x != p-1
   x = x*x % p 
   z = z + 1
Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Этот код необходим для оценки показаний остатков по модулю после применения различных случайных чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855160
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855223
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЭто второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855251
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЭто второе условие теста Миллера-Рабина?
В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.Как в том анекдоте:
хрень, не хрень, а работает.

Я просто спросил, а тут такие выводы...

Я предупреждал, что в сообщении 21958523 рассматриваю только первое условие теста Миллера-Рабина,
причем было оговорено: "какой перечень остатков выдаёт этот тест".

Поскольку случайное число получается от 2 до (n - 2 ),
то, естественно, было интересно:
а что получится, если все случайные числа 2 до (n - 2 ) будут "применены".

Таким образом, я посчитал все остатки по модулю при подстановке всех возможных случайных чисел для чисел от 5 до 115.

Была составлена программа, были получены результаты, в сообщении 21958523 показаны основные выводы,
а в сообщении 21959374 показан код такой программы на Питоне.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855256
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry SibiryakovGennadiy UsovА как они пишут новую программу?Подавляющее большинство делает это копипастом с гугля.То есть, основополагающие алгоритмы никто не читает?

Была такая игра: каждый в цепочке на ухо сообщает другому в цепочке слово, и какое слово пролучается в конце цепочки.
Или что-то похожее...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855370
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Основные алгоритмы описаны в Википедии.

Но этот форум обычно обсуждает их реализации на конкретных языках и конфигурациях.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855401
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovDimitry Sibiryakovпропущено...
Подавляющее большинство делает это копипастом с гугля.То есть, основополагающие алгоритмы никто не читает?очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчас
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855430
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovGennadiy UsovА как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.Некоторые тут и даже и копипаст не могут.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855434
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчасНу конечно, не рационально каждый раз писать всё с нуля. Есть готовые библиотеки, в том числе с открытыми исходниками. Можно посмотреть, оценить удобство api и качество кода, выбрать подходящее решение.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855535
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Геннадий любит лично все обследовать.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855606
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonГеннадий любит лично все обследовать. Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855614
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonГеннадий любит лично все обследовать. Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855636
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.
Может быть, что-то и найдётся...Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.И что увидели на всей матрице? Жду ответа.

А можно посмотреть на отдельные столбцы матрицы. Найти логику и выработать эвристическое решение
(с проверкой на деление на сколько хватит мощности компьютера).

А насчет "кривого недотеста"? Кажется, это похвала в квадрате.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855935
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Зашел в вики на https://ru.wikipedia.org/wiki/ - криптографический алгоритм RSA.
Для этого алгоритма требуются случайные простые числа.
Ищу https://ru.wikipedia.org/wiki/ , где указывается количество раундов k для теста Миллера–Рабина при поиске простых случайных чисел :
k – количество битов в двоичной записи проверяемого числа n.
С другой стороны, в тесте Миллера–Рабина количество раундов оговаривается log (n).

Так какое количество раундов выбрать?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855950
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил проверить с помощью простенькой программы на Питоне:
Код: python
1.
2.
3.
4.
iimport math
x = pow(2, 1024)
y = math.log( x )
print y

Получилось
709.782712893

И 1024 и 709 - числа большие.

А если уменьшить количество раундов в 2, 3, 4 раза?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855955
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Усов. У меня идея появилась.

Есть формула которая оценивает количество простых на интервале от 2 до n. Разумеется приближенная.
От нее легко перейти к любому интервалу.

Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etc
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855959
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonУсов. У меня идея появилась.
Есть формула которая оценивает количество простых на интервале от 2 до n. Разумеется приближенная.
От нее легко перейти к любому интервалу.
Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etcМонте-Карло - это случайность, вероятность.
Конечно, можно оценить с помощью перебора случайных чисел любой процесс, но это будет вероятностное определение.

Я же хочу иметь достаточный тест на определение простых чисел.
Пусть это будут не все простые числа, а, например, половина всех простых чисел (подмножество простых чисел).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855961
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЯ же хочу иметь достаточный тест на определение простых чисел.
К слову "достаточный" требуется уточнение "для чего".
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855962
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry SibiryakovGennadiy UsovЯ же хочу иметь достаточный тест на определение простых чисел.К слову "достаточный" требуется уточнение "для чего".Рассмотрим небольшую задачу.

Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.

Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.

Пусть имеется подмножество простых чисел, которые определяются с помощью 100 раундов теста Миллера–Рабина (а может быть и меньше). Причем, числа этого подмножества имеют достаточное условие для простых чисел. Количество элементов в подмножестве в 2 раза меньше, чем количество простых чисел (для определённого N рассматриваемых чисел).

Элементы подмножества встречаются реже, чем элементы множества, но зато за определённый промежуток времени можно проверить в несколько раз больше чисел.

Главное, мы получаем не псевдопростые числа, а простые числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855972
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovНадо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.

Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.

Почему 2000 ?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855975
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovНадо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.
Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.Почему 2000 ?В вики записано про случайные простые числа для RSA:

"В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов k...
...
Выполнить тест Миллера — Рабина с количеством раундов не меньше k.".

У нас либо 1024, либо 2048
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855981
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov, будет детерминизм?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855982
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy Usov, будет детерминизм?А куда он денется?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855984
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonGennadiy Usov, будет детерминизм?А куда он денется?
А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855988
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonА ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.Где-то надо черпать информацию...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855991
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonGennadiy Usovпропущено...
А куда он денется?
А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.
В продолжение детерминизма и куда он денется. Я просто поставлю вопрос.

Какие требования мы выдвинем к датчику случайных чисел?
Можем ли мы его при таком раскладе заменить на последовательность

0..1023

или на последовательность с более длинным шагом?

0,1023,2047,3071....2^1023

Как это повлияет на результат повторного эксперимента? Зачем вообще случайность при полном покрытии?
Код: 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.
    
    /**
     * Constructs a randomly generated BigInteger, uniformly distributed over
     * the range 0 to (2<sup>{@code numBits}</sup> - 1), inclusive.
     * The uniformity of the distribution assumes that a fair source of random
     * bits is provided in {@code rnd}.  Note that this constructor always
     * constructs a non-negative BigInteger.
     *
     * @param  numBits maximum bitLength of the new BigInteger.
     * @param  rnd source of randomness to be used in computing the new
     *         BigInteger.
     * @throws IllegalArgumentException {@code numBits} is negative.
     * @see #bitLength()
     */
    public BigInteger(int numBits, Random rnd) {
        this(1, randomBits(numBits, rnd));
    }

/**
     * 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
Ещё раз о тесте Ферма
    #39855993
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonВ продолжение детерминизма и куда он денется. Я просто поставлю вопрос.
Какие требования мы выдвинем к датчику случайных чисел?
.....
Как я сказал ранее, меня мало интересует датчик случайных чисел.

Почти у всех целых чисел,
имеются остатки по mod, равные 1 (первое условие теста М-Р), и не 1, а много раз.
В результате, почти все из этих чисел, в случае "удачной" комбинации случайных чисел,
можно назвать псевдопростыми.

Поэтому желательно иметь другой принцип поиска остатков по mod.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39856033
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovдопустим для RSA.
Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39856063
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry SibiryakovGennadiy Usovдопустим для RSA.Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.Простоту полученных чисел может подтвердить только алгоритм Эратосфена - полный перебор всех делителей от 3 до ...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39862965
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Gennadiy UsovDimitry SibiryakovДля "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.Простоту полученных чисел может подтвердить только алгоритм Эратосфена - полный перебор всех делителей от 3 до ...Простоту полученных чисел может подтвердить ещё новый эвристический алгоритм 21968895 .

Сейчас ещё раз прочитал об известных последовательностях простых чисел.
Каждая из этих последовательностей состоит из некоторых простых чисел (не всех).

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


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