Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8 9 10 .. 12      [все]
 Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
В вики говорится о том, что к вероятностным тестам простоты относят тест Ферма.

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

А кроме чисел Мерсенна есть ли ещё примеры «ошибочности» теста Ферма?
11 июн 19, 20:11    [21907037]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Как известно,тест простоты Ферма для простого числа имеет вид:
.
(в общем виде – основание степени не 2, а произвольное число число а, которое не делится на n.)

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

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

Ставится задача:
из подмножества простых чисел выделить меньшее подмножество простых чисел, для которых тест Ферма будет достаточным.
То есть, найти новое условие, которое будет достаточным для теста Ферма при определении простых чисел.
12 июн 19, 06:47    [21907153]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Synoptic
Member

Откуда:
Сообщений: 97
Курсовик?
12 июн 19, 09:41    [21907178]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Synoptic
Курсовик?
Нет.

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

Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?
12 июн 19, 11:15    [21907214]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
vikkiv
Member

Откуда: London
Сообщений: 2399
Gennadiy Usov,

их не так много по понятиям баз данных,
особенно с учётом того что в обычном программировании
есть некоторые ограничения из-за типа данных,
соответственно проще держать список
простых чисел в базе и делать проверку на exists из этого списка,
т.е. необходимость сложно-красивой математической
проверки/вывода/доказательства по всем правилам науки - отпадают.
12 июн 19, 11:27    [21907222]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.
12 июн 19, 12:18    [21907262]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
vikkiv
Gennadiy Usov,
их не так много по понятиям баз данных,
особенно с учётом того что в обычном программировании
есть некоторые ограничения из-за типа данных,
соответственно проще держать список
простых чисел в базе и делать проверку на exists из этого списка,
т.е. необходимость сложно-красивой математической
проверки/вывода/доказательства по всем правилам науки - отпадают.
А что, база данных простых чисел существует до ?
12 июн 19, 12:30    [21907274]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Я так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.
Размечтались...

Будет топик намного короче.
12 июн 19, 13:16    [21907284]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6269
mayton
Я так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.
задача 21907153 сформулирована некорректно
12 июн 19, 19:46    [21907430]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Siemargl
mayton
Я так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.
задача 21907153 сформулирована некорректно
И в чём некорректность?
12 июн 19, 19:50    [21907431]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Synoptic
Курсовик?
Нет.

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

Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?
Современная математика не знает такого способа.
12 июн 19, 20:29    [21907436]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Просто интересная задача.
Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?
Современная математика не знает такого способа.
А как же куча тестов простоты, а как же алгоритм Эратосфена?
12 июн 19, 20:35    [21907441]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Мне кажется что вероятностные тесты простоты мы уже обсуждали.
12 июн 19, 20:37    [21907442]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Мне кажется что вероятностные тесты простоты мы уже обсуждали.
А если для вероятностного теста простоты появляется дополнительное условие?

Которое определяет достаточность теста простоты?
12 июн 19, 20:45    [21907446]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Мне кажется что вероятностные тесты простоты мы уже обсуждали.
А если для вероятностного теста простоты появляется дополнительное условие?

Которое определяет достаточность теста простоты?

Что за условия? Как вы их найдете?
12 июн 19, 21:50    [21907471]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6269
Gennadiy Usov
Siemargl
пропущено...
задача 21907153 сформулирована некорректно
И в чём некорректность?

Ставится задача:
из подмножества простых чисел выделить меньшее подмножество простых чисел, для которых тест Ферма будет достаточным.
То есть, найти новое условие, которое будет достаточным для теста Ферма при определении простых чисел.

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

т.е формулу простых чисел, что невозможно
13 июн 19, 00:18    [21907525]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
vikkiv
Member

Откуда: London
Сообщений: 2399
Siemargl
т.е формулу простых чисел, что невозможно

какой-то совсем однозначный вывод сбивающий с пути рационального решения вопроса,
ещё раз напомню если то что выше не понято: в бизнес-задачах организаций порядки области значений не настолько большие,
и вот как раз для этих диапазонов в принципе генерация списка (около 10% от всего диапазона) простых чисел - не проблема
так что лучше-бы не отрываться от реалий при разработке систем (помня о заложенных ограничениях) - тогда всё получится.
13 июн 19, 01:33    [21907537]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6269
vikkiv,

а ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?
13 июн 19, 01:39    [21907538]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
vikkiv
Member

Откуда: London
Сообщений: 2399
Siemargl
а ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?

предполагаю что сосут из пальцев наверное другие, у кого уже такая привычка сложилась и жестко в терминологию вошло,
у меня выводы по реалиям бизнес задач на собственной практике работы в коммерческих организациях.
13 июн 19, 04:59    [21907553]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
vikkiv
Siemargl
а ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?

предполагаю что сосут из пальцев наверное другие, у кого уже такая привычка сложилась и жестко в терминологию вошло,
у меня выводы по реалиям бизнес задач на собственной практике работы в коммерческих организациях.
Единственная бизнес-задача, для которой нужны простые числа - RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.
13 июн 19, 05:37    [21907563]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
mayton
Мне кажется что вероятностные тесты простоты мы уже обсуждали.
А если для вероятностного теста простоты появляется дополнительное условие?

Которое определяет достаточность теста простоты?
Ну есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма.
13 июн 19, 05:45    [21907564]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Barlone
пропущено...
Современная математика не знает такого способа.
А как же куча тестов простоты, а как же алгоритм Эратосфена?
Ну там было "быстро". А алгоритм Эратосфена - это совсем не быстро, и вообще по объему требуемой памяти нереализуемо.
13 июн 19, 05:48    [21907565]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Единственная бизнес-задача, для которой нужны простые числа - RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.
А зачем хранить?

По мере нахождения простых чисел, эти числа "сразу поступают в работу".
Или "ждут своей очереди".
13 июн 19, 06:15    [21907570]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Ну есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма.
Какой?
13 июн 19, 06:16    [21907572]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
vikkiv
Member

Откуда: London
Сообщений: 2399
Barlone
..Единственная бизнес-задача, для которой нужны простые числа - RSA шифрование...

ну может быть конечно, однако даже на ближайшее будущее расчётных мощностей
для взлома 128-битных ключей (пи Е38) на период их (короткой) жизни - пока явно не хватает.
в контексте форума о базах данных: для 1024битного ключа (так понимаю ассиметричного, т.к. при симметричном так много не надо)
bigint с их Е63 отпадает так-же как и decimal/real (Е38), разве что float с Е308 наиболее близок и GUID ещё кандидат с их 16ти байтным размером.

за сим общество криптологов покину т.к. явно не моя тема..
13 июн 19, 06:19    [21907574]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov,

тынц, может на какие мысли натолкнёт
13 июн 19, 07:48    [21907608]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
kealon(Ruslan)
Gennadiy Usov,
тынц, может на какие мысли натолкнёт
Думал об этом.

А как узнать: через какое число не проходит синусоида?
Снова решето?
А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа.
13 июн 19, 09:05    [21907653]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
kealon(Ruslan)
Gennadiy Usov,
тынц, может на какие мысли натолкнёт
Думал об этом.

А как узнать: через какое число не проходит синусоида?
Снова решето?
А решето работает только с 1-ого числа. Его нельзя применить с К-ого числа.

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

Вопрос в том что мы хотим в цифрах. И сколько мы согласны ждать.
13 июн 19, 11:04    [21907749]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
ПЕНСИОНЕРКА
Member

Откуда: Владимирская обл
Сообщений: 4592
Gennadiy Usov
Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?

например так, если числа до 2000000000(тип long), с проверкой на чет/нечет, без списка простых чисел
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

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
13 июн 19, 11:17    [21907755]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Бабуля, твой код - ужасен
13 июн 19, 11:30    [21907766]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
ПЕНСИОНЕРКА
Member

Откуда: Владимирская обл
Сообщений: 4592
mayton
Бабуля, твой код - ужасен Картинка с другого сайта.

спасибо за комплимент
просто мне хотелось проанализировать время нахождения ПРОСТЫХ чисел в произвольном диапазоне не применяя списка простых чисел
-----
а оформление --это вторично
13 июн 19, 11:48    [21907786]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Мы уходим от первого сообщения топика.

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

А есть ли ещё простые числа, где этот тест не работает?
13 июн 19, 12:39    [21907836]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov
Мы уходим от первого сообщения топика.

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

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

читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинять
13 июн 19, 12:42    [21907844]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

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

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

Спрашивается:
а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)?
13 июн 19, 12:52    [21907859]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
ПЕНСИОНЕРКА
Member

Откуда: Владимирская обл
Сообщений: 4592
Gennadiy Usov
Мы уходим от первого сообщения топика.

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

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

2047 --не простое число

в этом диапазоне пустые
\требуется чисел= \ 2039 \ 2053 \ 2063 \ 2069 \ 2081 \ 2083 \ 2087
13 июн 19, 12:53    [21907861]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
kealon(Ruslan)
пропущено...
тест Ферма работает для всех простых чисел :-)
читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинять
Читайте сообщения внимательно.

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

Спрашивается:
а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)?

Ну... должны-быть. Я-бы спорил на виски что есть. Можем заключить пари.
По математической индукции - должны быть. С чего-бы ему быть одному этому числу?
13 июн 19, 12:56    [21907868]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton,
Вы меня удивляете насчет одного числа!

Неужели не знаете, что тест Ферма определил для чисел Мерсенна Мр (р-степень) простые числа для тех чисел Мр, у которых р - простое число.
А теперь посчитайте: сколько из чисел Мерсенна действительно являются простыми?
13 июн 19, 13:04    [21907881]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Так что. Я проиграл бутылку Виски?
13 июн 19, 13:16    [21907899]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
ПЕНСИОНЕРКА
Member

Откуда: Владимирская обл
Сообщений: 4592
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
13 июн 19, 13:18    [21907904]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Так что. Я проиграл бутылку Виски?
Выиграли!

Вы же спорили на то, что есть ещё такие числа.
13 июн 19, 13:20    [21907906]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Нашел в вики число 341=11*31.

Это число удовлетворяет тесту Ферма
13 июн 19, 15:18    [21908000]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Есть предложение:
нужно разделить все простые числа на подмножества, для каждого из которых будет существовать свой тест простоты, причём, достаточный.
То есть, если число проходит один из таких тестов простоты, то оно является простым числом.


На самом деле, будет несколько достаточных тестов простоты,
которые применяются к конкретному числу в зависимости от признаков этого числа.
13 июн 19, 15:55    [21908030]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
vikkiv
Member

Откуда: London
Сообщений: 2399
на малых числах можно или 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 возможна.
13 июн 19, 16:56    [21908090]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
vikkiv
Member

Откуда: London
Сообщений: 2399
выше это в смысле ещё раз (надеюсь в последний) вклинюсь - вам шашечки или ехать?
13 июн 19, 16:57    [21908092]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
В сообщении 21908030 говорилось о разложении всех простых чисел на подмножества.

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

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

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

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

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

Всё это создаёт массу вычислений, а также то, что есть вероятность того, что число n не является простым.
Попробуем этот тест доработать.
14 июн 19, 06:17    [21908306]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Рассматривается следующее изменение теста Соловея – Штрассена 21908306:

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

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

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

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

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

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

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

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

Псевдопростые числа будут рассмотрены позднее.
14 июн 19, 09:04    [21908344]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа


3277, 29341, 49141, 80581, 88357, 104653, ...
14 июн 19, 09:43    [21908370]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Числа составные, 2(n-1)/2 == n-1
14 июн 19, 09:46    [21908374]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
а) Р = n -1
В этом случае число n определяем как простое число.
Это и есть достаточный тест для определения числа n как простого числа

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

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

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

Я её уже видел, но думал, что проскочит.
Не получилось.
14 июн 19, 10:45    [21908441]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Вспоминается анекдот. ".... Женится тебе пора, барин".
14 июн 19, 10:46    [21908442]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Числа составные, 2(n-1)/2 == n-1
Здесь я не понял.

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

И как получается (n-1)?
14 июн 19, 10:50    [21908446]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Barlone
Числа составные, 2(n-1)/2 == n-1
Здесь я не понял.

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

И как получается (n-1)?
Ну я там забыл взять остаток. Для 15 и не получается
14 июн 19, 12:52    [21908601]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Здесь я не понял.
Если n =15, то (n-1)/2 = 7
2^7 = 64
И как получается (n-1)?
Ну я там забыл взять остаток. Для 15 и не получается
А для каких чисел получится?
14 июн 19, 13:23    [21908648]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone,

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

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

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

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 14.
Можно сказать, начинаем формировать первое подмножество простых чисел.
14 июн 19, 13:36    [21908661]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Barlone,

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

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

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

1678541, 1811573, 3400013, 3605429
Когда за дело берутся настоящие математики, у них получается лучше -
https://en.wikipedia.org/wiki/Baillie–PSW_primality_test
нет ни одного известного составного числа, походящего тест
14 июн 19, 14:36    [21908732]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone,

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

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

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

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

Не нравится значение 3605429.
Может быть ошибка?
14 июн 19, 16:34    [21908838]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Barlone,
Не нравится значение 3605429.
Может быть ошибка?

python
>>> pow(2,3605429//2,3605429)
3605428
все правильно
14 июн 19, 17:28    [21908902]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone,

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

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

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

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

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 10.
Можно сказать, начинаем формировать первое подмножество простых чисел.
21 июн 19, 06:33    [21912572]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Виноват, ошибся.
Надо делить на 2 и ....
Тогда сообщение будет выглядеть следующим образом:

"Barlone,

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

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

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

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

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 10.
Можно сказать, начинаем формировать первое подмножество простых чисел."
21 июн 19, 06:41    [21912574]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Или проще - (n-1)/2 - простое число.
21 июн 19, 06:43    [21912575]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone,

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

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

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

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



Что тогда получается?
21 июн 19, 07:03    [21912576]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Что тогда получается?
Пока получается, что вы берете гипотезы с потолка, без обоснований их правильности.
23 июн 19, 19:37    [21913679]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy 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
24 июн 19, 10:55    [21913903]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 21024, то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка
24 июн 19, 13:33    [21914029]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 21024, то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка
Спасибо за сообщение о частном случае теста Люка!

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

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

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

И заодно определить простые числа (n-1)/2.
24 июн 19, 15:45    [21914187]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 21024, то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка
Вот появился ещё один тест.

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

И спрашивается: почему?
25 июн 19, 06:56    [21914490]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
С другой стороны, основным критерием любого теста является достаточность.

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

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

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

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

Спрашивается: количество m вычислений по модулю не является слишком большим?
(с точки зрения проведения расчетов на компьютере в разумное время)
25 июн 19, 07:07    [21914494]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Gennadiy Usov
Barlone
Gennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 21024, то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
Ну так то оно работает, тут угадали, это частный случай теста Люка
Вот появился ещё один тест.
Но этот тест не упоминается в вики в разделе простые числа.
Получается, что по версии авторов раздела про простые числа этот тест не подходит для поиска простых чисел.
И спрашивается: почему?
А тест Люка, оказывается, то же "неподъёмный" для больших чисел n.

Ведь надо найти все множители числа n - 1.
25 июн 19, 12:26    [21914752]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone,

что означает данный оператор python ( не нашел описания по 4-м параметрам)
Barlone
python
>>> pow(2,3605429//2,3605429)
3605428
Он определяет простоту числа?
25 июл 19, 10:14    [21934070]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Barlone,

что означает данный оператор python ( не нашел описания по 4-м параметрам)
Barlone
python
>>> pow(2,3605429//2,3605429)
3605428
Он определяет простоту числа?
Там три параметра, // - целочисленное деление
23605429/2%3605429
25 июл 19, 20:38    [21934809]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Barlone
python
>>> pow(2,3605429//2,3605429)
3605428
Там три параметра, // - целочисленное деление
23605429/2%3605429
Спасибо!

Ещё вопрос:
а в python есть функция поиска простоты числа, или надо определять простоту числа обычным "дедовским" способом?
26 июл 19, 10:27    [21935083]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Есть статья которая описывает библиотеку SymPy

https://www.geeksforgeeks.org/prime-functions-python-sympy/
26 июл 19, 11:25    [21935176]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Есть статья которая описывает библиотеку SymPy
https://www.geeksforgeeks.org/prime-functions-python-sympy/
Спасибо!

А как эту библиотеку подцепить к https://ideone.com/?
26 июл 19, 18:35    [21935686]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Хм... да. Действительно Идеоновская сборка не знает эту библиотечку.
26 июл 19, 18:40    [21935692]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Поскольку пока отсутствуют процедуры определения простоты числа для https://ideone.com/,
приходится обращаться к калькуляторам в "ручном режиме".

И то, только до 2^200.
31 июл 19, 20:00    [21939280]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Продолжил построение различных множеств простых чисел.

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

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

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

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

Эти числа проверены на факторизаторе чисел.
1 авг 19, 07:28    [21939419]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Так никто не ответил на первое сообщение топика:
"А кроме чисел Мерсенна есть ли ещё примеры «ошибочности» теста Ферма?"

Покопался в вики и нашел:
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

В эту последовательность войдут все составные числа Мерсенна - Мр, у которых р - простое число.
2 авг 19, 10:25    [21940432]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
А далее - самое интересное!

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

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

Если получится понять поведение последовательности 21940432,
то задача определения простых чисел с помощью теста Ферма (и ещё чего-нибудь) будет решена.
2 авг 19, 12:44    [21940591]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Решил сам определить последовательность чисел,
полученных в результате «ошибочности» теста Ферма.

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

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

В последовательности 21940432 рассматривались все нечётные числа.
В этом случае получается 172 составных числа.
3 авг 19, 12:55    [21941147]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
ёёёёё
Member

Откуда:
Сообщений: 689
Barlone
...RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.


Числа есть, а хранить их негде. Бардак.
5 авг 19, 15:27    [21942160]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
ёёёёё
Barlone
...RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.
Числа есть, а хранить их негде. Бардак.
А зачем хранить?

Если есть такое хранилище, то оно доступно как криптографикам, так и криптоаналитикам.
5 авг 19, 16:03    [21942199]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
ёёёёё
Member

Откуда:
Сообщений: 689
Gennadiy Usov
ёёёёё
пропущено...
Числа есть, а хранить их негде. Бардак.
А зачем хранить?

Если есть такое хранилище, то оно доступно как криптографикам, так и криптоаналитикам.

В параллельной вселенной?
5 авг 19, 17:09    [21942258]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
ёёёёё
Gennadiy Usov
А зачем хранить?
Если есть такое хранилище, то оно доступно как криптографикам, так и криптоаналитикам.
В параллельной вселенной?
Зачем так далеко забираться?

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

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

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

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

Например, поиск простых чисел, аналогичный поиску 21939419
5 авг 19, 18:07    [21942348]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
mayton
Мне кажется что вероятностные тесты простоты мы уже обсуждали.
А если для вероятностного теста простоты появляется дополнительное условие?
Которое определяет достаточность теста простоты?
Что за условия? Как вы их найдете?
Просто никто не рассматривал составные числа, которые "проходят" тест Ферма.
Этих чисел немного, поэтому их можно анализировать.

Для начала - 21940591
11 авг 19, 09:31    [21946356]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Есть статья которая описывает библиотеку SymPy

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

Например, вместе с isprime (n)
11 авг 19, 16:37    [21946499]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Важно рассмотреть ещё один вопрос.

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

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

Насколько полученная последовательность простых чисел может помочь
в решении задачи поиска простых чисел в районе 2^1024?
14 авг 19, 18:17    [21949539]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Первые несколько штук (probable prime).

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989
14 авг 19, 21:38    [21949643]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Первые несколько штук (probable prime).

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989
И сколько времени ушло на поиск этих чисел?
И с помощью какого теста простоты?
15 авг 19, 07:16    [21949743]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Несколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.

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

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. Поэтому в исходнике есть два разных типа от двух разных языков.
15 авг 19, 09:28    [21949809]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Щас качнул снова зеркало исходников JDK чтоб посмотреть историю.
15 авг 19, 09:41    [21949813]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Второте и третье число - близнецы кстати.
15 авг 19, 10:29    [21949843]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Несколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.
А есть ли такая же программа на питоне?
15 авг 19, 19:48    [21950471]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Первые несколько штук (probable prime).

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

Так более читаемо.
И можно зрительно отследить интервалы между найденными простыми числами.
16 авг 19, 18:35    [21951358]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Несколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.
А есть ли такая же программа на питоне?

Я не специалист в Питоне. Но я думаю что тест Люка и Ребе-Миллера там должен быть. И длинная арифметика должна тоже
быть.

Есть Питонщики?
16 авг 19, 23:03    [21951509]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.

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
16 авг 19, 23:24    [21951523]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
Насколько я понял, здесь показаны расстояния между числами.

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

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

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

Спасибо за информацию!
17 авг 19, 06:30    [21951603]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
В префиксном коде.
(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)))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
)
17 авг 19, 23:49    [21951868]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
518
282
78  и т.д
Но это всё числа, полученные с помощью теста Ферма.

А если среди них есть составные числа, как иногда бывает с тестом Ферма?
18 авг 19, 12:49    [21951951]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Не знаю. Как это проверить?
18 авг 19, 13:42    [21951974]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Исходный код который (предположительно) работает. Я использую JDK-11.
Исходники брал от OpenJDK. Текущая версия мастер-бранча примерно ей
соответсвует. Я говорю это просто просмотрев активность по изменениям
в модуле BigInteger. Этот модуль стабилен и менялся редко. Особенно в части алгоритма.
Основную его (ядерную часть) закоммитил некто Duke в 2007 году.

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

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

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

+

    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);
            }
        }

+
    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();
    }
18 авг 19, 14:44    [21951985]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Полностью исходники (зеркало) OpenJDK можно скачать здесь https://github.com/unofficial-openjdk/openjdk
18 авг 19, 14:46    [21951986]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
В код также забито много некрасивых и математически неясных "гвоздей".
Это связано с тем что создатели этого BitInteger беспокоились лишь о том
чтобы код работал быстро. Ясность чтения исходника их не беспокоила.

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

result.bitLength() > 6


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

Если переменная result имеет разрядную сетку больше чем 6 бит. По сути 6 бит это число более чем 64.
Еще аналог - целое логарифмирование по основанию 2.
18 авг 19, 14:51    [21951990]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
В питоне запустил программу по поиску составных чисел, удовлетворяющих тесту Ферма.

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

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

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

Где-то 1 : 100

Максимальный из минимальных множителей составных чисел - 2971.
18 авг 19, 20:40    [21952070]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Так я самый первый исходник не до конца скопипастил.

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

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

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

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

int searchLen = getPrimeSearchLen(result.bitLength());


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


+

    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));
        }
    }
19 авг 19, 00:53    [21952124]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

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

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

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


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

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

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

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

Я использовал в 21952070 2-й вариант
d = 2							
p = 7							
P = p + 1000000							
while p <= P: 							
	d = 6 - d						
	p = p + d
19 авг 19, 07:27    [21952153]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Не особо. Я просто комментирую то как nextPrime уже реализован в языковых библиотеках.
19 авг 19, 07:33    [21952156]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Не особо. Я просто комментирую то как nextPrime уже реализован в языковых библиотеках.
.... и пишу простенькие программы в порядке комментария
19 авг 19, 07:38    [21952158]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Меня интересовал Radix tree/trie. И всякие сжатые форматы хранения аналитики.

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

Вот такой вот загадочный мотиватор.
19 авг 19, 07:58    [21952166]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
В продолжение сообщения 21952153 привожу код по перебору целых чисел с помощью массива
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	
21 авг 19, 07:38    [21953930]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Вобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса.
Вопрос:

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

Например, факторизатор "Империя чисел" работает с числами 10^60
21 авг 19, 08:00    [21953944]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Вобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса.
Вопрос:

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

Например, факторизатор "Империя чисел" работает с числами 10^60

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

Хотя... могли брать по другому принципу.
21 авг 19, 10:10    [21954024]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
Например, факторизатор "Империя чисел" работает с числами 10^60

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

И не забывайте что факторизация и тест на простоту это всё-таки не совсем одно и то-же.
21 авг 19, 10:14    [21954029]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
Например, факторизатор "Империя чисел" работает с числами 10^60

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

Этот факторизатор удобен только для отдельных чисел.
mayton
И не забывайте что факторизация и тест на простоту это всё-таки не совсем одно и то-же.
Но у них общие "корни".
21 авг 19, 10:36    [21954070]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
пропущено...

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

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

Ну ты видел что поиск следующего простого содержит как минимум бутерброд из 4х разных алгоритмов?

Зачем ты говоришь про общие корни? Как мы твои корни натянем на эту практическую реализацию.
Я понимаю ты идеалист. Я тебе еще в ферзевой задаче говорил что мы должны подходить очень
селективно к алгоритму основываясь на разной природе входных данных. Серебрянной пули не будет.
У нас будет десяток бронзовых пуль каждая из которых хорошо работает в данном диапазоне чисел
или ферзей или вектора входных данных и очень-очень плохо работаает на другом векторе входа.
21 авг 19, 10:39    [21954074]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
Вопрос:
а зачем нам нужны числа, меньше SMALL_PRIME_THRESHOLD (95 бит)?
Не знаю. Могу предположить что эта точка была выбрана на графике экспериментально.
....
Хотя... могли брать по другому принципу.
Могу предположить, что число SMALL_PRIME_THRESHOLD (95 бит) не связано с исследуемым числом.

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

Сейчас попробую проверить на 1000... повторных вычислений скорость определения:
- остатка по тесту Ферма для большого числа
- остатка после деления этого большого числа на серию произвольных чисел.
21 авг 19, 10:44    [21954080]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
И не забывайте что факторизация и тест на простоту это всё-таки не совсем одно и то-же.
Но у них общие "корни".
mayton
Ну ты видел что поиск следующего простого содержит как минимум бутерброд из 4х разных алгоритмов?
Зачем ты говоришь про общие корни? Как мы твои корни натянем на эту практическую реализацию.
Я понимаю ты идеалист. Я тебе еще в ферзевой задаче говорил что мы должны подходить очень
селективно к алгоритму основываясь на разной природе входных данных. Серебрянной пули не будет.
У нас будет десяток бронзовых пуль каждая из которых хорошо работает в данном диапазоне чисел
или ферзей или вектора входных данных и очень-очень плохо работаает на другом векторе входа.
А кто сказал, что будет один алгоритм?

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

Или разные?
21 авг 19, 10:50    [21954091]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Рабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.
21 авг 19, 11:00    [21954108]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Рабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.
А если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.
21 авг 19, 11:18    [21954134]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Рабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.
А если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.

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

 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);
            }
21 авг 19, 11:32    [21954149]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
А если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.

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

А почему 41, а не 43, а не 61, а не ....?
21 авг 19, 11:43    [21954170]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Решил сравнить время на проведение операция для большого числа в двух вариантах:
- тест Ферма
- деление на множество делителей.

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

Получилось, что за 3 сек. можно найти для другого числа p = pow(2, 2023) + 89 :
- 150 тестов Ферма
- 3 000 000 делений на делители.
21 авг 19, 12:38    [21954266]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
пропущено...

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

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


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

 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);
            }
21 авг 19, 18:05    [21954724]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
А почему 41, а не 43, а не 61, а не ....?
Я всё таки еще упрощу этот цикл. Как я уже говорил Java не годится для работы с длинными целыми. Разверну эти
толстые функции типа reminder. Под капотом у нее бутерброд из двух алгоритмов remainderKnuth и remainderBurnikelZiegler.
Надеюсь это просто какие-то оптимизации быстрого остатка от деления. Первый из них носит гордую фамилию Кнута.
Это радует.
Вы не ответили на вопрос: почему последнее простое число 41.

Я попробую представить свой вариант части кода (начало цикла, остальное - в зависимости от применения)
#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:	
			 и т.д.
Количество простых чисел в массиве можно увеличить
21 авг 19, 18:36    [21954752]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я не знаю почему 41. Я просто разворачиваю вложенность сорца и представляю его на суд в форуме
в читабельном виде.

Предположительно это другая экспериментальная константа которая была забита в код на основании
замеров времени как оптимум.
21 авг 19, 18:39    [21954756]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Потом Миллера Раввина в пересечечии с Люка-Лемьером. Причем идет
пересеченеи условий. Необходимое - Миллер. Достаточное - Люка. Насколько я понимаю
здесь должен быть 100% детерминимзм. Не зря они сетку ограничивали.
В вики записано:

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

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

Если это не так, то приведите пример, желательно, на небольших числах.
21 авг 19, 20:03    [21954798]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я не буду спорить с википедией. Просто приведу исходник.
    /**
     * 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);
    }
21 авг 19, 22:44    [21954899]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Тут дело не в программе.

Главное:
какие чисел эта программа (тест Люка — Лемера) определила как простые?
(кроме чисел Мерсенна)
22 авг 19, 07:28    [21954999]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Кроме того, тест Люка — Лемера работает при использовании степени 2 у выбранного числа (и -1).

А как для произвольного числа определить эту степень 2?
22 авг 19, 07:32    [21955002]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Не знаю.
22 авг 19, 09:09    [21955051]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Тестов много разных...
https://ru.wikipedia.org/wiki/Псевдопростое_число_Люка
https://ru.wikipedia.org/wiki/Псевдопростое_число
https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа
22 авг 19, 10:12    [21955124]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
По сорцам Люка параметризуется неким загадочным Символом Якоби.
22 авг 19, 10:29    [21955154]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я нарисую блок-схему. Для Геннадия и для себя тоже.
22 авг 19, 10:40    [21955165]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Нет в символе Якоби ничего загадочного. Это обобщение символа Лежандра на составные числа, и для простых чисел они совпадают.
Только вычисляют его (Якоби) не по определению, где нужно разложение на простые, а через квадратичный закон взаимности.
Для простого модуля символ Якоби позволяет определить, является ли какое-то число квадратичным вычетом по этому модулю, то есть существует ли квадратный корень из числа по модулю. (Например, 2 - квадратичный вычет по модулю 7, так как 3*3 mod 7 == 2)
22 авг 19, 11:41    [21955237]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Тестов много разных...
https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа
А данный тест очень интересный.

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

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

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

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

Далее осталось найти пример работы теста Люка.
22 авг 19, 13:16    [21955379]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Однако, интерес к этому тесту поубавился.

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

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

Кроме того, для очень больших чисел невозможно (нужно очень много времени) найти последовательность чисел Люка
- эти числа определяются от первого числа.
22 авг 19, 13:31    [21955412]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Получается, что можно проверить только отдельные числа.
Не так. Последовательность Люка используется для проверки произвольного числа.
22 авг 19, 15:21    [21955618]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Получается, что можно проверить только отдельные числа.
Не так. Последовательность Люка используется для проверки произвольного числа.
Имеется последовательность Люка:
Числа Люка - Vn = { 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... } ,

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

Или я ошибаюсь?
22 авг 19, 15:38    [21955643]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Множество ненулевых остатков (вычетов) по модулю простого числа N - абелева группапорядка N-1. Что проверяет тест Ферма? Он проверяет, что порядок подгруппы, порожденной некоторым выбранным элементом, делит N-1. Когда он дает ложноположительный результат? Если N составное, то порядок группы будет φ(N). А порядок подгруппы, порожденной неким элементом, будет делителем φ(N). И тест Ферма сфейлится, когда этот делитель φ(N) окажется также и делителем N-1
22 авг 19, 19:28    [21955908]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
А такой вопрос:

есть простое число N, для которого получаем (N - 1) значений теста Ферма.
Эти числа различны или нет?
22 авг 19, 19:39    [21955919]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Кроме мультипликативной группы вычетов по модулю, можно сконструировать и всякие другие группы - матрицы (но она на Абелева - умножение матриц не коммутативно), полиномы, точки на эллиптической кривой, решения уравнения Пелля
Коэффициенты всех этих матриц, полиномов, … можно брать по модулю числа N. И можно несколькими способами сконструировать группу, порядок которой для простого N будет N+1. И вот тут я не совсем уверен, но кажется, тест Люка проверяет, что порядок некой подгруппы такой группы делит N+1.
22 авг 19, 19:43    [21955925]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
А такой вопрос:

есть простое число N, для которого получаем (N - 1) значений теста Ферма.
Эти числа различны или нет?
Для простого N естественно все значения будут 1. Для составного будет 1, если порядок подгруппы делит N-1, и не 1, если не делит :)
22 авг 19, 19:47    [21955929]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Вот смотрите: 21^64 % 65 == 1 - фейл, 65 = 5*13
Смотрим 21^1 % 65 == 21; 21^2 % 65 == 51; 21^3 % 65 == 31; 21^4 % 65 == 1; а дальше пойдет повтор - 21^5 % 65 == 21. То есть порядок подгруппы, порожденной 21, по модулю 65 равен 4. А 65-1 делится на 4. И тест фейлится.
22 авг 19, 20:05    [21955941]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Наверное, я не так сформулировал задачу.

Имелось в виду числа от 2^1 % 65 до 2^64 % 65.
Это тоже группа?
22 авг 19, 20:08    [21955945]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
А, да, φ(65) = 4 * 12 = 48. Кажется, всегда, когда для составного N НОД(φ(N), N-1) > 2 можно найти значение, на котором тест Ферма сфейлится. (Но это не точно, в смысле доказать я сейчас не смогу).
22 авг 19, 20:09    [21955947]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Наверное, я не так сформулировал задачу.

Имелось в виду числа от 2^1 % 65 до 2^64 % 65.
Это тоже группа?
Ну так их же 4 всего разных.
22 авг 19, 20:12    [21955950]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Ой, не то написал
22 авг 19, 20:13    [21955952]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
А если числа от от 2^1 % 59 до 2^58 % 59,
то числа будут разные?
22 авг 19, 20:14    [21955954]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Для двойки (и любого другого числа по модулю 65) порядок группы будет каким-то делителем 48. Если этот делитель будет кратен 3, то он не делит 64, и тест Ферма покажет, что число составное. А если делитель не кратен трем, то в данном случае он будет также делителем 64.
22 авг 19, 20:17    [21955957]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
А если числа от от 2^1 % 59 до 2^58 % 59,
то числа будут разные?
не обязательно
22 авг 19, 20:19    [21955960]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Порядок подгруппы может оказаться делителем N-1
22 авг 19, 20:21    [21955962]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Barlone
Порядок подгруппы может оказаться делителем N-1
Для простого N
22 авг 19, 20:21    [21955964]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Но при этом может быть несколько одинаковых подгрупп для простого N. (например, 7, 31, 43)
22 авг 19, 20:36    [21955976]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Сделал код для теста Миллера — Рабина.

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

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

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

Как быть?
22 авг 19, 20:48    [21955985]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov,

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

тынц
23 авг 19, 00:16    [21956111]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Если тест Ферма для какого-то a mod N говорит, что число N псевдопростое, а тест Миллера — Рабина для этого же a - что N составное, то мы еще и делитель N нашли...
23 авг 19, 05:35    [21956139]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
Сделал код для теста Миллера — Рабина.

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

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

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

Как быть?

Геннадий. Я вижу что недетерминизм не дает тебе спокойно спать.

Делай от 2 до 50 раундов проверки. Как здесь.
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();
        }
23 авг 19, 07:51    [21956163]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Геннадий. Я вижу что недетерминизм не дает тебе спокойно спать.
Делай от 2 до 50 раундов проверки.
Здесь дело не в раундах.
Здесь всё сложнее.

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

Тогда что важнее:
- то, что появилась 1
- то, что не появилось 1
23 авг 19, 10:22    [21956242]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov, важнее то что алгоритм Миллера-Раввина относится к классу bounded error probabalistic,
как и функции хеширования и фильтры Блума. Но ты упорно пытаешся вытащить его из этой классификации
и перетащить в другую.
23 авг 19, 10:31    [21956251]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Попробовал не останавливать поиск случайного числа для первой части теста Миллера-Раввина,
а насчитать сто вариантов случайных чисел для определения простоты ряда чисел.

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

Получается, что числа вида 2039 можно выделить в отдельное достаточное множество простых чисел.
23 авг 19, 11:04    [21956300]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov, можно задать тебе вопрос?

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

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

(я дам подсказку. this - это и есть твое число 2047)
23 авг 19, 11:11    [21956304]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov, можно задать тебе вопрос?
Как ты себе понимаешь вот этот предикат?
this.passesMillerRabin(rounds, random) && this.passesLucasLehmer();
На самом верхнем уровне смыслов. Ну тоесть что делает этот фрагмент кода человеческим языком?
(я дам подсказку. this - это и есть твое число 2047)
Я почти не работал в JAVA, поэтому трудно ответить на вопрос.

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

Вопрос в действии теста Миллера-Раввина,
чтобы была уверенность, что тест "помогает" находить простые числа.
А 2047 - это тестовый вариант.
23 авг 19, 11:27    [21956319]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Давай почитаем еще раз описание. (я беру это всё из опенсорцных источников с Гитхаба ссылку на который
я уже приводил если что).

Данная функция primeToCertainty(int certainty, Random random) возвращает true, если число вероятно-простое.
И возвращает false если оно ТОЧНО составное. (Точно-точно. 100% составное!)

Внизу - пересечение двух предикатов Миллера и Люка.
МиллерЛюкаРезультат
falsefalsefalse
falsetruefalse
truefalsefalse
truetruetrue

Пробабалистический Миллер который шумит и даёт иногда в зависимости от состояния датчика
случайных чисел разные значения вынесен как первый. Он работает раньше. Его полезный
эффект - отбить составные числа. Тоесть - снять нагрузку с Люка. Здесь я точно не уверен
возможно это просто моё предположение. Просто практика использования расчетных функций
это подскзывает. Пускай Барлон подскажет так оно или нет. Я не изучал эти оба алгоритма внутри
и не знаю насколько они сложны.

    /**
     * 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();
    }
23 авг 19, 11:47    [21956341]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Я не изучал эти оба алгоритма внутри и не знаю насколько они сложны.
А зря не изучали.
mayton
Пробабалистический Миллер который шумит и даёт иногда в зависимости от состояния датчика случайных чисел разные значения вынесен как первый. Он работает раньше. Его полезный эффект - отбить составные числа. Тоесть - снять нагрузку с Люка. Здесь я точно не уверен возможно это просто моё предположение. Просто практика использования расчетных функций это подскзывает.
Тест Миллера не отбивает составные числа!
Он может их выдавать иногда (в зависимости от "настроения" случайных чисел).
Если бы было иначе, то задача поиска простых чисел уже была бы решена.

А насчет Люка, Вы 21955051 уже ответили, что не знаете как работает этот тест с обычным числом (не числом Мерсенна).
mayton
Пускай Барлон подскажет так оно или нет.
Одна надежда на Барлона
23 авг 19, 13:03    [21956407]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
Тест Миллера не отбивает составные числа!

А ну-ка нука.

Что-же он делает?
23 авг 19, 13:08    [21956412]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
Тест Миллера не отбивает составные числа!
А ну-ка нука.
Что-же он делает?
Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые.

Поэтому, фраза "Его полезный эффект - отбить составные числа" можно отнести к любому тесту простоты. Чем тогда тест Миллера лучше других тестов.
23 авг 19, 13:36    [21956446]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
пропущено...
А ну-ка нука.
Что-же он делает?
Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые.

Поэтому, фраза "Его полезный эффект - отбить составные числа" можно отнести к любому тесту простоты. Чем тогда тест Миллера лучше других тестов.

Например какой тест?
23 авг 19, 14:04    [21956473]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Чем тогда тест Миллера лучше других тестов.
Тем, что оставляет меньше псевдопростых.
https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел)
23 авг 19, 14:41    [21956521]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я прошу прощения. Во избежание кривотолков я буду писать фактическое название функции
как это записано в исходниках JDK. Интерпретация - это будет второй вопрос.
passesMillerRabinpassesLucasLehmerResult
falsefalsefalse
falsetruefalse
truefalsefalse
truetruetrue
23 авг 19, 14:45    [21956529]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Чем тогда тест Миллера лучше других тестов.
Тем, что оставляет меньше псевдопростых.
https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел)
Согласен!

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

Теперь осталось найти следующий тест, который оставит ещё меньше псевдопростых.
23 авг 19, 15:41    [21956569]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Просьба помочь!
pp = 55
p = pow(2, pp) - 1
t = p - 1
t = t / 2;
print (t)
На питоне число t становится действительным.

А как сделать так, чтобы оно было целым?
23 авг 19, 16:16    [21956614]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я не разбираюсь в Питоне. Но скорее всего виновата функция pow() она возвращает другой тип.

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

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
>>>
23 авг 19, 17:18    [21956654]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Блин... Вот так.

>>> pp = 55
>>> p = 2**pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
18014398509481983
23 авг 19, 17:28    [21956667]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Блин... Вот так.
>>> pp = 55
>>> p = 2**pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
18014398509481983
Спасибо!

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

В то же время, нашел t = t // 2.
Знал об этом, и забыл.
23 авг 19, 17:51    [21956679]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
В сообщении 21952153 говорилось о подзадаче 1. "Выбор последовательности целых чисел".

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

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

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

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

И в каждом диапазоне должно быть своё количество проверяемых делителей.
24 авг 19, 13:13    [21956946]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Напомню что я приводил исходники функции nextProbablePrime() название
которой буквально переводится как "следующее вероятно-простое число".

Никаких бОльших смыслов здесь не было добавлено.
24 авг 19, 14:36    [21956961]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Каждое целое положительное число, большее 0,
будет считаться псевдопростым или вероятностно простым до тех пор,
пока к этому числу не применили какой-нибудь тест простоты,
и этот тест показал, что проверяемое число является составным числом.

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

Кстати, название - нечётное число - это то же является самым простым (предварительным) тестом простоты.
24 авг 19, 18:23    [21957011]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Вобщем если длина числа меньше SMALL_PRIME_THRESHOLD (95 бит) то в бой идут алгоритмы
прямого брутфорса. Потом Миллера Раввина в пересечечии с Люка-Лемьером. Причем идет
пересеченеи условий. Необходимое - Миллер.
Я бы на 3-ю подзадачу поиска простых чисел на диапазоне очень больших чисел поставил следующую подзадачу:

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

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

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

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

И уже на следующем шаге подключать более сложные тесты.
25 авг 19, 05:59    [21957112]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
- тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина.
С чего бы быстрее? Возводить в степень (n-1)/2, а потом в квадрат или сразу в (n-1) - по времени никакой разницы.
25 авг 19, 07:51    [21957117]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
- тест Ферма для одного числа выполняется намного быстрее, чем тест Миллера-Раввина.
С чего бы быстрее? Возводить в степень (n-1)/2, а потом в квадрат или сразу в (n-1) - по времени никакой разницы.
В тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1).

Разница по времени вычисления теста для одного числа n есть?
25 авг 19, 08:55    [21957122]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Только сейчас заметил, что если для теста Миллера-Раввина получаем случайное число 2,
то тест Миллера-Раввина превращается в тест Ферма.
25 авг 19, 08:59    [21957124]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Забыл сказать, что тест Миллера-Раввина может превратиться в тест Ферма при степени 2 только для случая, когда (n - 1) делится только на одну 2.

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

При этом первая часть теста Миллера-Раввина принимает за простое число 341.
25 авг 19, 13:30    [21957184]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov, что за "первая часть"?
25 авг 19, 13:36    [21957189]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
В тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1).

Разница по времени вычисления теста для одного числа n есть?
Ну это вообще ерунда, и Ферма можно по разным основаниям считать.
25 авг 19, 13:39    [21957190]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
В тесте Ферма основание степени 2, в тесте Миллера-Раввина основание степени - случайное число из диапазона (2, n-1).
Разница по времени вычисления теста для одного числа n есть?
Ну это вообще ерунда, и Ферма можно по разным основаниям считать.
Конечно можно.

Только при реальной проверке произвольного числа на простоту сколько оснований закладывается в программу?
25 авг 19, 13:48    [21957198]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov, что за "первая часть"?
У теста Миллера-Раввина есть два условия https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина

Я пока проверяю первое условие (первая часть).
25 авг 19, 13:52    [21957201]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Я пока проверяю первое условие (первая часть).
Оно так не работает
25 авг 19, 13:57    [21957202]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Я пока проверяю первое условие (первая часть).
Оно так не работает
Почему не работает.

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

Подробности позднее.
25 авг 19, 14:14    [21957207]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Так не работает же
Gennadiy Usov
Сделал код для теста Миллера — Рабина.

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

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

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

Как быть?
В вики написано: "если число простое, то выполняется хотя бы одно из условий". Значит, если не одно из условий не выполняется, число точно составное. Вы проверили только одно. Это не дает ничего. Если первое условие выполнено, число может быть как простым, так и составным. Если первое условие не выполнено, а второе не проверялось, то число тоже может быть как простым, так и составным.
25 авг 19, 15:54    [21957224]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
А в чем проблема то проверить второе условие? У вас есть s - количество младших нулевых битов в n-1. Вы полученное на первом шаге число s-1 раз возводите в квадрат по модулю n и каждый раз сравниваете с n-1.
25 авг 19, 16:07    [21957227]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Так не работает же
Gennadiy Usov
Сделал код для теста Миллера — Рабина.
Пока сделал код для первого условия:
.
Оказалось, что для 2047 (составное число) для разного расчета - запуск программы (разные случайные числа) получаю разные данные:
то для числа 2047 - получаю 1 (число простое), то нет 1.
В вики для теста записано:
"выполняется хотя бы одно из условий":
Как быть?
В вики написано: "если число простое, то выполняется хотя бы одно из условий". Значит, если не одно из условий не выполняется, число точно составное. Вы проверили только одно. Это не дает ничего. Если первое условие выполнено, число может быть как простым, так и составным. Если первое условие не выполнено, а второе не проверялось, то число тоже может быть как простым, так и составным.
Так Вы же всё отметили в сообщении.

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

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

Вот и вся история с географией.
25 авг 19, 16:08    [21957228]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
А в чем проблема то проверить второе условие? У вас есть s - количество младших нулевых битов в n-1. Вы полученное на первом шаге число s-1 раз возводите в квадрат по модулю n и каждый раз сравниваете с n-1.
А этим нарушаются условия теста Миллера — Рабина:
"выполняется хотя бы одно из условий:"(из вики)

Иначе можно договорить о доработке теста Миллера — Рабина с точки зрения:
выполнения двух условий.
25 авг 19, 16:12    [21957230]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
С логикой у вас проблемы.
Из того, что число простое, следует, что выполняется хотя бы одно из двух условий.
Из того, что выполняется первое условие, ничего не следует.
Из того, что не выполняется первое условие, тоже ничего не следует.
Из того, что ни одно из двух условий не выполняется, следует, что число составное.
25 авг 19, 16:33    [21957232]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Иначе можно договорить о доработке теста Миллера — Рабина с точки зрения:
выполнения двух условий.
Ну оба условия сразу выполниться никак не могут, сколько единицу в квадрат не возводи, она минус единицей не станет.
25 авг 19, 16:44    [21957234]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
С логикой у вас проблемы.
Из того, что число простое, следует, что выполняется хотя бы одно из двух условий.
Из того, что выполняется первое условие, ничего не следует.
Из того, что не выполняется первое условие, тоже ничего не следует.
Из того, что ни одно из двух условий не выполняется, следует, что число составное.
При чём здесь логика?

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

Я эти правила нарушил?
Где, в каком месте?
25 авг 19, 16:54    [21957237]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Если обсуждать алгоритм nextProbablePrime который я приводил то Миллер-Рабин срабатывает

1) Только для аргументов числа-кандидата больше 2^95. Это видно в исходном коде.
2) Выполняется числом раундов от 27 до 2 в зависимости от разрядности сетки. Это сделано ради экономии ресурсов скорее всего (число 2).
3) Внутри параметризируется встроенным генератором случайных чисел на который мы извне не влияем. Этот датчик
практически не должен дать два подряд одинаковых случайных числа в таком юзкейсе b = new BigInteger(this.bitLength(), rnd);



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;
    }



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

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

Если я мешаю - то скажите и я не буду больше писать. Просто мне кажется что вы "ломитесь" в открытую дверь.
25 авг 19, 17:18    [21957238]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Если обсуждать алгоритм nextProbablePrime который я приводил то Миллер-Рабин срабатывает

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

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

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

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

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

Со своей стороны, постараюсь подготовить программу для второго условия теста Миллер-Рабина,
чтобы сравнивать результаты двух условий.
25 авг 19, 17:49    [21957247]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

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

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

При этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).
25 авг 19, 18:21    [21957256]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Хорошо. Я понял.

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

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

Спрашивайте вопросы.
25 авг 19, 18:21    [21957257]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
25 авг 19, 18:38    [21957260]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Полистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?).

Зеленым цветом обозначены истинные тесты простоты. Красным - вероятностные. Прочие заметки - серым.

К сообщению приложен файл. Размер - 96Kb
25 авг 19, 19:02    [21957274]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?
25 авг 19, 19:03    [21957275]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Полистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)
Схема красивая!

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

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?
25 авг 19, 19:07    [21957281]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Надо рисовать матрицу. Например имя теста. Его асимптоматика. И практическое время работы на
небольшой выборке чисел. На разрых порядках. На миллиардах. На триллионах. И так далее.
И есть у меня предположение что истинные тесты простоты слишком долго работают.
Может долгие часы. Или дни. Или годы.

При таком раскладе Миллер+Люка будут выгоднее. Никто не хочет ждать годы для проверки числа.
25 авг 19, 19:17    [21957285]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?

Алгоритм - перед вами. Реверс-инжинеринг - это процесс извлечения алгоритма из кода.
Он - тоже работает. А вот за уточняющими вопросами типа показателей степени надо
читать книжки. Я так думаю.
25 авг 19, 19:19    [21957286]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
При этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).
Ерунду вы написали. Вообще-то, если в математической формуле написано "a эквивалентно минус единице по модулю N" (значок такой ≡ из трех черточек), то в программе это будет выглядеть как "a % N == N-1", потому что -1 и N-1 попадают в один класс эквивалентности по модулю N.
26 авг 19, 04:34    [21957420]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Возьмем например простое число 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. И второе условие не выполнено, значит число составное.
26 авг 19, 04:53    [21957423]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Последний случай кстати самый интересный - когда для какого-то числа а ≠ ±1 mod N оказывается что a² ≡ 1 mod N, то gcd(a+1, N) и gcd(a-1, N) дадут нам делители N.
26 авг 19, 05:11    [21957424]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
26 авг 19, 08:21    [21957453]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov
mayton
Полистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)
Схема красивая!

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

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?
ты же сам ответ дал 21957011
26 авг 19, 08:36    [21957460]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
kealon(Ruslan)
Gennadiy Usov
14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?
Все эти тесты использовать?
Или всё-таки остановиться на некоторых?
ты же сам ответ дал 21957011
Спасибо, что нашли мою цитату!

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

Нам же нужно повысить степень, так называемой, "псевдопростоты",
которая должна, по каким-нибудь своим законам, стремиться к простоте.
26 авг 19, 11:17    [21957531]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
Но это очень сложно.

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

То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!
26 авг 19, 11:25    [21957540]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Barlone
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um

ОК. Спасибо. Может вы знаете готовую имплементацию подобного метода nextProbablePrime для Python?
26 авг 19, 12:30    [21957583]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

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

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

Barlone
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
26 авг 19, 14:56    [21957686]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Чтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!
Ага, и чтобы повести тест Ферма для этого числа, надо посчитать а(21024-2) но это же не значит, что нужно 21024-3 умножений на а.
Barlone
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
Если я правильно понял, числа V2^1024-1 и U2^1024-1 нужно разложить на V и U.
А эти V и U разложить на следующие V и U. И т.д.

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

Кстати, хорошо делить число, когда оно чётное. А если очередное число нечётное?
26 авг 19, 18:07    [21957827]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov,
да всё так же, как с возведением в степень
Из U1,V1 получаем U2,V2, из них U4,V4, … и дальше по степеням двойки. Ну и по двоичному представлению нужного значения собираем результат - например, комбинируя пару U1,V1 c U4,V4 - получим U5,V5.
26 авг 19, 18:32    [21957840]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Формулы есть в английской вики
Картинка с другого сайта.
26 авг 19, 18:39    [21957848]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Спасибо за программу!

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

Это ограничение для Python?
26 авг 19, 19:16    [21957872]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Не знаю. Давайте Python-специфичные вопросы задавать тут https://www.sql.ru/forum/php-perl
26 авг 19, 19:35    [21957880]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Вот Люка-Лемер на Питоне. https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Запустил программу на своём стареньком компьютере (лет 10), и нашел все числа Мерсенна до 9941 где-то за 40 минут.

Перед этим запустил программу с тестом Миллера-Рабина, и оказалось, что этот тест хорошо подходит для определения чисел Мерсенна.
На своём стареньком компьютере нашел все числа Мерсенна до 9941 где-то за 2 часа.
26 авг 19, 19:51    [21957887]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
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


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


       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. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
26 авг 19, 20:17    [21957894]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
В своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.
26 авг 19, 20:45    [21957909]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
На первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
Я уже приводил чередование 4 и 2 21952153.

Накопление простых в массиве может когда-то прекратиться.(на больших числах)
26 авг 19, 20:51    [21957913]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
На первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
Я уже приводил чередование 4 и 2 21952153.

Накопление простых в массиве может когда-то прекратиться.(на больших числах)

А тебе много и не надо. Накопи простых хотя-бы тыщу. Большая часть делителей
отбивается на самых ранних шагах.
26 авг 19, 20:54    [21957917]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dima T
Member

Откуда:
Сообщений: 13916
mayton
В своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.

Лучше переиначить алгоритм чтобы вместо извлечения корня было возведение в квадрат. Умножение намного быстрее происходит.
26 авг 19, 20:56    [21957920]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Согласен. Кстати я бы поднял отдельный топик. Быстрое умножение и быстрое возведение в квадрат
для arbitary precision. Просто для того чтобы провести ревизию текущих API и библиотек. Используют
они эти методы или нет.

А то меня терзают смутные сомнения.
26 авг 19, 21:50    [21957937]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
mayton
Согласен. Кстати я бы поднял отдельный топик. Быстрое умножение и быстрое возведение в квадрат
для arbitary precision. Просто для того чтобы провести ревизию текущих API и библиотек. Используют
они эти методы или нет.

А то меня терзают смутные сомнения.
https://ru.wikipedia.org/wiki/Умножение_Карацубы
27 авг 19, 05:15    [21958018]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
Я уже приводил чередование 4 и 2 21952153.
Накопление простых в массиве может когда-то прекратиться.(на больших числах)
А тебе много и не надо. Накопи простых хотя-бы тыщу.
Большая часть делителей отбивается на самых ранних шагах.
Можно применить "ленивый алгоритм накопленных простых чисел".
О нём уже было сказано21954752.
Поскольку там ошибка, привожу ещё раз (без ошибки)
#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 чисел.
27 авг 19, 07:50    [21958033]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Почему 22 ?
27 авг 19, 13:05    [21958260]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
В своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.
По этому поводу можно рассмотреть такой вариант.

Квадраты последовательных чисел N и (N + 1) отстоят друг от друга на (2*N+1).
Поскольку делители - только нечётные числа, то N и (N + 2) отстоят друг от друга на (4*N+4).

Итак, в начале находим корень минимума диапазона, от целого этого числа получаем "квадрат N",
и это будет точкой отсчета по смене величины, которая ограничивает количество делителей.

Осталось проверять расстояние исследуемого числа от предыдущего "квадрата N",
и если получаемое расстояние превышает (4*N+4) от этого "квадрата N",
то определяется новый "квадрат N+1", равный увеличению предыдущего "квадрата N" на (4*N+4).
27 авг 19, 13:14    [21958264]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Почему 22 ?
Очень удобно в одном массиве в ячейке [0] помещать длину массива данных,
и "работать" с массивом, начиная с ячейки [1].

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

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

Кстати, я уже это демонстрировал на предыдущих топиках.
27 авг 19, 13:19    [21958268]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Почитал про Питон.

Длину массива берут так.
>>> 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-массивов она стоила
линейно от длины самой строчки. Тоесть чем длиннее строка тем дольше ждать.
27 авг 19, 14:12    [21958333]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Решил ещё раз поработать с тестом Миллера-Рабина с точки зрения:
какой перечень остатков выдаёт этот тест.

Пока поработал с числами до 115.

Есть простые числа, для которых только 1 или n-1 по двум условиям теста:
7, 11,19,23,31,43,47,59,67,71,79,83,103,107

Есть простые числа, для которых только 1 или n-1 по двум условиям теста не для всех случайных чисел:
29,37,41,61,73,89,101,109,113

Есть простые числа, для которых только 1 или n-1 только по второму условию:
5,13,17(не все),53,97(не все),

Есть составные числа, для которых только 1 только по второму условию:
39, 105.
Поэтому по второму условию значение 1 не подходит.
27 авг 19, 18:17    [21958523]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov,

Выпишите несколько табличек для разных простых n: в первый столбец все числа от 1 до n-1, а в строку их степени по модулю n.
Например для 5 так
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. Правда, табличка большая получится, но если над ней помедитировать, то озарение обязательно придет.
27 авг 19, 20:35    [21958576]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone,

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

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

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.
27 авг 19, 21:16    [21958593]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Если бы мы знали как разделить область определения Миллера-Раввина на детерминированную и случайную то получили бы две функции. Причем одна из них была бы строго детерминирована по определению.
27 авг 19, 21:23    [21958596]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov,

Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.
27 авг 19, 21:25    [21958598]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Barlone,

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

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

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.
Вопрос как раз в том, как получаются псевдопростые.
27 авг 19, 21:34    [21958599]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Я могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)
27 авг 19, 21:38    [21958601]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Если бы мы знали как разделить область определения Миллера-Раввина на детерминированную и случайную то получили бы две функции.
Причем одна из них была бы строго детерминирована по определению.
Пример 21957887 показал, что тест Миллера-Раввина находит среди чисел Мерсенна только простые числа без пропусков,
причем только с помощью первого условия.
Правда, медленнее теста Люка-Лемера раза в 2-3.
Это уже область применения без появления составных чисел.
Barlone
Gennadiy Usov,
Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.
Увеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример -21956300),
из-за которых эти числа принимаются тестом как простые.
Barlone
Gennadiy Usov
Barlone,
Вопрос не в том, как получаются псевдопростые числа.
Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.
Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.
Вопрос как раз в том, как получаются псевдопростые.
При исследовании теста Миллера-Рабина (может быть и других тестов)
необходимо для каждого составного небольшого числа (как примера) отследить появление условий 1 или (n - 1),
частоту их появления и тогда принимать какие-то решения по этим результатам.
Например, есть числа 21958523, для которых тест Миллера-Рабина показывает только 1 или (n - 1) по двум условиям.

Здесь можно говорить о подмножестве простых чисел, для которых существует достаточное условие (примерно как в 21907153).
Barlone
Я могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)
С удовольствием прочитаю.
28 авг 19, 07:01    [21958707]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Увеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример -21956300),
из-за которых эти числа принимаются тестом как простые.
Не так это работает. Каждый раунд говорит либо "число точно составное", либо "не уверен, может быть простым." Если хотя бы один из раундов сказал, что число точно составное - то оно таки составное.
А чтобы доказать, что число простое, надо очень много раундов, порядка log(n) - это уже детерминированный вариант теста.
28 авг 19, 07:58    [21958728]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov,

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

Первый раунд который детектировал составное - отменяет все результаты до этого.
28 авг 19, 08:01    [21958731]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
У меня 2 вопроса ( с учетом примера 21956300) для чисел 2047 и 2053:

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

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

для числа 2053 (простое) в течении нескольких раундов (выбор случайного числа) не будет появляться 1.
Это означает, что число 2053 составное?
28 авг 19, 09:01    [21958763]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Решил "отбросить" поиск случайного числа для первого условия теста Миллера-Рабина
и заменил этот поиск на перебор вариантов от 2 до (n - 2). Для чисел до 115 - не так много информации.

Оказалось, что:

1. Есть числа, у которых в остатке (по модулю) получается только 1 и (n - 1).
Множество таких чисел уже может быть подмножеством простых чисел.

2. Есть числа, которые мы считаем простыми,
у которых в остатке (по модулю) значения 1 и (n - 1) составляют от 70% до 5% от общего перечня остатков.
Для некоторых из этих чисел трудно будет найти значение 1.

3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается только 1.
В разных числах 1, 2, 5 значений.

4. Есть числа, у которых при переборе от 2 до (n - 2) остатки (по модулю) то же плавно возрастают от 2 до (n - 2).
28 авг 19, 13:31    [21959038]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Ошибся.
пункт 3 предыдущего сообщения надо читать так:

3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается иногда 1.
В разных числах 1, 2, 5 значений.
28 авг 19, 13:38    [21959044]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я давно наблюдаю за форумом. И заметил что программисты очень не любят читать прозу.
Зато исходник вызывает у них живой интерес. Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.

Поэтому код с комментариями эффективнее чем просто текст который все не поняли
или интерпретировали по разному. Вот такие они... программисты.
28 авг 19, 16:15    [21959227]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Я давно наблюдаю за форумом. И заметил что программисты очень не любят читать прозу.
Зато исходник вызывает у них живой интерес. Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.
Поэтому код с комментариями эффективнее чем просто текст который все не поняли
или интерпретировали по разному. Вот такие они... программисты.
А как они пишут новую программу?

По другому коду или по алгоритму?
28 авг 19, 16:20    [21959233]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Не могу сказать. Это очень творческий процесс. Впрочем как и всё чем мы тут занимаемся.
28 авг 19, 16:25    [21959240]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.
Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне:
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		
28 авг 19, 19:19    [21959374]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
	y = math.log( p )				

		x = pow(y1, t1, p)			

Мне кажется тут ослаблен контроль над типами. Кажется что натуральный логарифм и степень
возвращают число с плавающей точкой. А это не очень согласуется с решаемой задачей где
везде и всегда будут целые числа произвольной точности (arbitrary precision).
28 авг 19, 23:34    [21959443]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Почитал Википедию.

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

Это Люка-Лемьер-Ризель (LLT) предположительно. Поэтому все что я писал надо читать с поправкой по этому названию.
28 авг 19, 23:45    [21959450]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
mayton
Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.
Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне:
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) надо еще
z = 0
while z < s and x != 1 and x != p-1
29 авг 19, 06:16    [21959501]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
x = x*x % p
29 авг 19, 06:17    [21959502]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Недописанное ушло, 2 раза

z = 0
while z < s and x != 1 and x != p-1
x = x*x % p
z = z + 1
29 авг 19, 06:18    [21959503]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Код недоделанный.
После x = pow(y1, t1, p) надо еще
z = 0
while z < s and x != 1 and x != p-1
x = x*x % p
z = z + 1
Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Этот код необходим для оценки показаний остатков по модулю после применения различных случайных чисел.
29 авг 19, 13:51    [21959832]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
Gennadiy Usov
А как они пишут новую программу?

Подавляющее большинство делает это копипастом с гугля.
29 авг 19, 14:06    [21959848]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.
29 авг 19, 15:18    [21959927]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Это второе условие теста Миллера-Рабина?
В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.
Как в том анекдоте:
хрень, не хрень, а работает.

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

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

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

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

Была составлена программа, были получены результаты, в сообщении 21958523 показаны основные выводы,
а в сообщении 21959374 показан код такой программы на Питоне.
29 авг 19, 15:55    [21959963]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Dimitry Sibiryakov
Gennadiy Usov
А как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.
То есть, основополагающие алгоритмы никто не читает?

Была такая игра: каждый в цепочке на ухо сообщает другому в цепочке слово, и какое слово пролучается в конце цепочки.
Или что-то похожее...
29 авг 19, 16:00    [21959971]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Основные алгоритмы описаны в Википедии.

Но этот форум обычно обсуждает их реализации на конкретных языках и конфигурациях.
29 авг 19, 21:40    [21960154]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov
Dimitry Sibiryakov
пропущено...
Подавляющее большинство делает это копипастом с гугля.
То есть, основополагающие алгоритмы никто не читает?
очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчас
30 авг 19, 00:18    [21960200]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Dimitry Sibiryakov
Gennadiy Usov
А как они пишут новую программу?

Подавляющее большинство делает это копипастом с гугля.
Некоторые тут и даже и копипаст не могут.
30 авг 19, 08:34    [21960247]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
kealon(Ruslan)
очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчас
Ну конечно, не рационально каждый раз писать всё с нуля. Есть готовые библиотеки, в том числе с открытыми исходниками. Можно посмотреть, оценить удобство api и качество кода, выбрать подходящее решение.
30 авг 19, 08:45    [21960251]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Геннадий любит лично все обследовать.
30 авг 19, 11:19    [21960385]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Геннадий любит лично все обследовать.
Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...
30 авг 19, 12:35    [21960478]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
mayton
Геннадий любит лично все обследовать.
Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...
Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.
30 авг 19, 12:47    [21960489]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Barlone
Gennadiy Usov
Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.
Может быть, что-то и найдётся...
Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.
И что увидели на всей матрице? Жду ответа.

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

А насчет "кривого недотеста"? Кажется, это похвала в квадрате.
30 авг 19, 13:25    [21960519]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Зашел в вики на https://ru.wikipedia.org/wiki/ - криптографический алгоритм RSA.
Для этого алгоритма требуются случайные простые числа.
Ищу https://ru.wikipedia.org/wiki/ , где указывается количество раундов k для теста Миллера–Рабина при поиске простых случайных чисел :
k – количество битов в двоичной записи проверяемого числа n.
С другой стороны, в тесте Миллера–Рабина количество раундов оговаривается log (n).

Так какое количество раундов выбрать?
31 авг 19, 11:44    [21961058]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Решил проверить с помощью простенькой программы на Питоне:
iimport math
x = pow(2, 1024)
y = math.log( x )
print y
Получилось
709.782712893

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

А если уменьшить количество раундов в 2, 3, 4 раза?
31 авг 19, 12:48    [21961079]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Усов. У меня идея появилась.

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

Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etc
31 авг 19, 13:00    [21961088]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

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

Я же хочу иметь достаточный тест на определение простых чисел.
Пусть это будут не все простые числа, а, например, половина всех простых чисел (подмножество простых чисел).
31 авг 19, 13:21    [21961108]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
Gennadiy Usov
Я же хочу иметь достаточный тест на определение простых чисел.

К слову "достаточный" требуется уточнение "для чего".
31 авг 19, 13:39    [21961112]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Dimitry Sibiryakov
Gennadiy Usov
Я же хочу иметь достаточный тест на определение простых чисел.
К слову "достаточный" требуется уточнение "для чего".
Рассмотрим небольшую задачу.

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

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

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

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

Главное, мы получаем не псевдопростые числа, а простые числа.
31 авг 19, 13:55    [21961117]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.

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

Почему 2000 ?
31 авг 19, 15:57    [21961176]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov
Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.
Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.
Почему 2000 ?
В вики записано про случайные простые числа для RSA:

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

У нас либо 1024, либо 2048
31 авг 19, 16:10    [21961179]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov, будет детерминизм?
31 авг 19, 16:44    [21961192]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Gennadiy Usov, будет детерминизм?
А куда он денется?
31 авг 19, 16:48    [21961193]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Gennadiy Usov, будет детерминизм?
А куда он денется?

А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.
31 авг 19, 16:58    [21961195]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.
Где-то надо черпать информацию...
31 авг 19, 17:20    [21961204]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
mayton
Gennadiy Usov
пропущено...
А куда он денется?

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

В продолжение детерминизма и куда он денется. Я просто поставлю вопрос.

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

0..1023

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

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

Как это повлияет на результат повторного эксперимента? Зачем вообще случайность при полном покрытии?
+
    
    /**
     * 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;
    }
31 авг 19, 17:34    [21961209]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
В продолжение детерминизма и куда он денется. Я просто поставлю вопрос.
Какие требования мы выдвинем к датчику случайных чисел?
.....
Как я сказал ранее, меня мало интересует датчик случайных чисел.

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

Поэтому желательно иметь другой принцип поиска остатков по mod.
31 авг 19, 17:59    [21961216]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
Gennadiy Usov
допустим для RSA.

Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.
31 авг 19, 22:09    [21961318]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Dimitry Sibiryakov
Gennadiy Usov
допустим для RSA.
Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.
Простоту полученных чисел может подтвердить только алгоритм Эратосфена - полный перебор всех делителей от 3 до ...
1 сен 19, 05:18    [21961378]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8 9 10 .. 12      [все]
Все форумы / Программирование Ответить