Ещё раз о тесте Ферма / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма

283 сообщений из 283, показаны все 12 страниц

все

Ещё раз о тесте Ферма

#39825596

Gennadiy Usov

Гость

В вики говорится о том, что к вероятностным тестам простоты относят тест Ферма.

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

А кроме чисел Мерсенна есть ли ещё примеры «ошибочности» теста Ферма?

...

Рейтинг:

0 / 0

11.06.2019, 20:11

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825640

Gennadiy Usov

Гость

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

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

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

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

...

Рейтинг:

0 / 0

12.06.2019, 06:47

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825661

Synoptic

Участник

Сообщения: 160

Рейтинг: 0 / 0

Курсовик?

...

Рейтинг:

0 / 0

12.06.2019, 09:41

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825681

Gennadiy Usov

Гость

SynopticКурсовик?Нет.

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

Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?

...

Рейтинг:

0 / 0

12.06.2019, 11:15

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825686

vikkiv

Участник

Откуда: EU

Сообщения: 2 580

Рейтинг: 0 / 0

Gennadiy Usov,

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

...

Рейтинг:

0 / 0

12.06.2019, 11:27

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825721

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.

...

Рейтинг:

0 / 0

12.06.2019, 12:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825730

Gennadiy Usov

Гость

vikkivGennadiy Usov,
их не так много по понятиям баз данных,
особенно с учётом того что в обычном программировании
есть некоторые ограничения из-за типа данных,
соответственно проще держать список
простых чисел в базе и делать проверку на exists из этого списка,
т.е. необходимость сложно-красивой математической
проверки/вывода/доказательства по всем правилам науки - отпадают.А что, база данных простых чисел существует до ?

...

Рейтинг:

0 / 0

12.06.2019, 12:30

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825737

Gennadiy Usov

Гость

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

Будет топик намного короче.

...

Рейтинг:

0 / 0

12.06.2019, 13:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825834

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

12.06.2019, 19:46

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825835

Gennadiy Usov

Гость

SiemarglmaytonЯ так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.задача 21907153 сформулирована некорректноИ в чём некорректность?

...

Рейтинг:

0 / 0

12.06.2019, 19:50

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825840

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovSynopticКурсовик?Нет.

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

Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?Современная математика не знает такого способа.

...

Рейтинг:

0 / 0

12.06.2019, 20:29

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825843

Gennadiy Usov

Гость

BarloneGennadiy UsovПросто интересная задача.
Есть число (целое, нечётное).
Как быстро определить: простое это число или нет?Современная математика не знает такого способа.А как же куча тестов простоты, а как же алгоритм Эратосфена?

...

Рейтинг:

0 / 0

12.06.2019, 20:35

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825844

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

12.06.2019, 20:37

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825845

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

12.06.2019, 20:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825861

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy UsovmaytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие?

Которое определяет достаточность теста простоты?
Что за условия? Как вы их найдете?

...

Рейтинг:

0 / 0

12.06.2019, 21:50

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825881

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Gennadiy UsovSiemarglпропущено...
задача 21907153 сформулирована некорректноИ в чём некорректность?
Ставится задача:
из подмножества простых чисел выделить меньшее подмножество простых чисел, для которых тест Ферма будет достаточным.
То есть, найти новое условие, которое будет достаточным для теста Ферма при определении простых чисел.
Если выбросить тавтологию, то задача в том, что найти
условие, которое будет достаточным для при определении простых чисел.
т.е формулу простых чисел, что невозможно

...

Рейтинг:

0 / 0

13.06.2019, 00:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825887

vikkiv

Участник

Откуда: EU

Сообщения: 2 580

Рейтинг: 0 / 0

Siemarglт.е формулу простых чисел, что невозможно
какой-то совсем однозначный вывод сбивающий с пути рационального решения вопроса,
ещё раз напомню если то что выше не понято: в бизнес-задачах организаций порядки области значений не настолько большие,
и вот как раз для этих диапазонов в принципе генерация списка (около 10% от всего диапазона) простых чисел - не проблема
так что лучше-бы не отрываться от реалий при разработке систем (помня о заложенных ограничениях) - тогда всё получится.

...

Рейтинг:

0 / 0

13.06.2019, 01:33

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825888

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

vikkiv,

а ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?

...

Рейтинг:

0 / 0

13.06.2019, 01:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825896

vikkiv

Участник

Откуда: EU

Сообщения: 2 580

Рейтинг: 0 / 0

Siemarglа ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп?
предполагаю что сосут из пальцев наверное другие, у кого уже такая привычка сложилась и жестко в терминологию вошло,
у меня выводы по реалиям бизнес задач на собственной практике работы в коммерческих организациях.

...

Рейтинг:

0 / 0

13.06.2019, 04:59

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825898

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

13.06.2019, 05:37

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825899

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovmaytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие?

Которое определяет достаточность теста простоты?Ну есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма.

...

Рейтинг:

0 / 0

13.06.2019, 05:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825900

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovBarloneпропущено...
Современная математика не знает такого способа.А как же куча тестов простоты, а как же алгоритм Эратосфена?Ну там было "быстро". А алгоритм Эратосфена - это совсем не быстро, и вообще по объему требуемой памяти нереализуемо.

...

Рейтинг:

0 / 0

13.06.2019, 05:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825903

Gennadiy Usov

Гость

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

По мере нахождения простых чисел, эти числа "сразу поступают в работу".
Или "ждут своей очереди".

...

Рейтинг:

0 / 0

13.06.2019, 06:15

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825905

Gennadiy Usov

Гость

BarloneНу есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма.Какой?

...

Рейтинг:

0 / 0

13.06.2019, 06:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825907

vikkiv

Участник

Откуда: EU

Сообщения: 2 580

Рейтинг: 0 / 0

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

за сим общество криптологов покину т.к. явно не моя тема..

...

Рейтинг:

0 / 0

13.06.2019, 06:19

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825928

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov,

тынц , может на какие мысли натолкнёт

...

Рейтинг:

0 / 0

13.06.2019, 07:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39825963

Gennadiy Usov

Гость

kealon(Ruslan)Gennadiy Usov,
тынц , может на какие мысли натолкнётДумал об этом.

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

...

Рейтинг:

0 / 0

13.06.2019, 09:05

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826022

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usovkealon(Ruslan)Gennadiy Usov,
тынц , может на какие мысли натолкнётДумал об этом.

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

Вопрос в том что мы хотим в цифрах. И сколько мы согласны ждать.

...

Рейтинг:

0 / 0

13.06.2019, 11:04

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826025

ПЕНСИОНЕРКА

Участник

Откуда: Владимирская обл

Сообщения: 4 809

Рейтинг: 0 / 0

Gennadiy UsovЕсть число (целое, нечётное).
Как быстро определить: простое это число или нет?
например так, если числа до 2000000000(тип long), с проверкой на чет/нечет, без списка простых чисел

Код: vbnet

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

Option Explicit
Sub mm()
Dim a As Long
Debug.Print "выбор  простых в интервале=============="
''''''''''''''''''''''''''''''
mm190613a 0, 7
mm190613a 18, 7
mm190613a 550, 7
''''''''''''''''''''''''''''''
a = 10 ^ 6
mm190613a a, 7
''''''''''''''''''''''''''''''
a = 10 ^ 7
mm190613a a, 7

End Sub

Код: vbnet

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.

Sub mm190613a(n1z As Long, n2z As Long)
Dim n0 As Long, j1 As Long, jm As Long, jp As Long, zkol As Long, dt
Dim j2 As Long, j2k As Long

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

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

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

End Sub

'выбор от 0 требуется чисел= 7 1 2 3 5 7 11 13 17 ' время в mсек= 12'выбор от 18 требуется чисел= 7 19 23 29 31 37 41 43 47' время в mсек= 0'выбор от 550 требуется чисел= 7 557 563 569 571 577 587 593 599' время в mсек= 0'выбор от 1000000 требуется чисел= 7 1000003 1000033 1000037 1000039 1000081 1000099 1000117 1000121' время в mсек= 12'выбор от 10000000 требуется чисел= 7 10000019 10000079 10000103 10000121 10000139 10000141 10000169 10000189' время в mсек= 0

...

Рейтинг:

0 / 0

13.06.2019, 11:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826034

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Бабуля, твой код - ужасен

...

Рейтинг:

0 / 0

13.06.2019, 11:30

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826046

ПЕНСИОНЕРКА

Участник

Откуда: Владимирская обл

Сообщения: 4 809

Рейтинг: 0 / 0

maytonБабуля, твой код - ужасен

спасибо за комплимент
просто мне хотелось проанализировать время нахождения ПРОСТЫХ чисел в произвольном диапазоне не применяя списка простых чисел
-----
а оформление --это вторично

...

Рейтинг:

0 / 0

13.06.2019, 11:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826078

Gennadiy Usov

Гость

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

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

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

...

Рейтинг:

0 / 0

13.06.2019, 12:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826086

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy UsovМы уходим от первого сообщения топика.

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

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

читайте теорию, откуда и почему, а то за заголовок зацепились и пошли дальше сочинять

...

Рейтинг:

0 / 0

13.06.2019, 12:42

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826100

Gennadiy Usov

Гость

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

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

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

...

Рейтинг:

0 / 0

13.06.2019, 12:52

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826102

ПЕНСИОНЕРКА

Участник

Откуда: Владимирская обл

Сообщения: 4 809

Рейтинг: 0 / 0

Gennadiy UsovМы уходим от первого сообщения топика.

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

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

в этом диапазоне пустые
\требуется чисел= \ 2039 \ 2053 \ 2063 \ 2069 \ 2081 \ 2083 \ 2087

...

Рейтинг:

0 / 0

13.06.2019, 12:53

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826108

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Спрашивается:
а есть ли ещё числа, которые тест Ферма считает простыми, а на самом деле эти числа не являются простыми (за исключением чисел Мерсенна)?
Ну... должны-быть. Я-бы спорил на виски что есть. Можем заключить пари.
По математической индукции - должны быть. С чего-бы ему быть одному этому числу?

...

Рейтинг:

0 / 0

13.06.2019, 12:56

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826117

Gennadiy Usov

Гость

mayton,
Вы меня удивляете насчет одного числа!

Неужели не знаете, что тест Ферма определил для чисел Мерсенна Мр (р-степень) простые числа для тех чисел Мр, у которых р - простое число.
А теперь посчитайте: сколько из чисел Мерсенна действительно являются простыми?

...

Рейтинг:

0 / 0

13.06.2019, 13:04

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826128

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Так что. Я проиграл бутылку Виски?

...

Рейтинг:

0 / 0

13.06.2019, 13:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826131

ПЕНСИОНЕРКА

Участник

Откуда: Владимирская обл

Сообщения: 4 809

Рейтинг: 0 / 0

Gennadiy Usov,

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

...

Рейтинг:

0 / 0

13.06.2019, 13:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826133

Gennadiy Usov

Гость

maytonТак что. Я проиграл бутылку Виски?Выиграли!

Вы же спорили на то, что есть ещё такие числа.

...

Рейтинг:

0 / 0

13.06.2019, 13:20

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826188

Gennadiy Usov

Гость

Нашел в вики число 341=11*31.

Это число удовлетворяет тесту Ферма

...

Рейтинг:

0 / 0

13.06.2019, 15:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826213

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

13.06.2019, 15:55

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826260

vikkiv

Участник

Откуда: EU

Сообщения: 2 580

Рейтинг: 0 / 0

на малых числах можно или online таблицы использовать, или online app-сервера расчётов
у меня здесь https://rextester.com/live/QNKB4696
генерирует для всего диапазона/предела в 100 миллионов за <10 секунд
(предел сервера настроенный для пользовательской сессии)
а на домашнем за долю секунды, для 1млрд за от 2х до 20ти сек.,
на выделенном сервере будет ещё быстрее..

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

здесь ещё ближайший можно проверить (в т.ч. и для 2^1024):
https://www.wolframalpha.com/input/?i=PrimeQ(2038074743)
https://www.wolframalpha.com/input/?i=PrimeQ(2^1024)
https://www.wolframalpha.com/input/?i=prime(100000000)
а по подписке у них и интеграция через API возможна.

...

Рейтинг:

0 / 0

13.06.2019, 16:56

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826261

vikkiv

Участник

Откуда: EU

Сообщения: 2 580

Рейтинг: 0 / 0

выше это в смысле ещё раз (надеюсь в последний) вклинюсь - вам шашечки или ехать?

...

Рейтинг:

0 / 0

13.06.2019, 16:57

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826379

Gennadiy Usov

Гость

В сообщении 21908030 говорилось о разложении всех простых чисел на подмножества.

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

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

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

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

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

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

...

Рейтинг:

0 / 0

14.06.2019, 06:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826407

Gennadiy Usov

Гость

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

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

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

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

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

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

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

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

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

Псевдопростые числа будут рассмотрены позднее.

...

Рейтинг:

0 / 0

14.06.2019, 09:04

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826424

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

3277, 29341, 49141, 80581, 88357, 104653, ...

...

Рейтинг:

0 / 0

14.06.2019, 09:43

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826425

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Числа составные, 2 ^(n-1)/2 == n-1

...

Рейтинг:

0 / 0

14.06.2019, 09:46

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826461

Gennadiy Usov

Гость

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

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

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

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

Я её уже видел, но думал, что проскочит.
Не получилось.

...

Рейтинг:

0 / 0

14.06.2019, 10:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826462

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Вспоминается анекдот. ".... Женится тебе пора, барин".

...

Рейтинг:

0 / 0

14.06.2019, 10:46

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826465

Gennadiy Usov

Гость

BarloneЧисла составные, 2 ^(n-1)/2 == n-1Здесь я не понял.

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

И как получается (n-1)?

...

Рейтинг:

0 / 0

14.06.2019, 10:50

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826555

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovBarloneЧисла составные, 2 ^(n-1)/2 == n-1Здесь я не понял.

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

И как получается (n-1)?Ну я там забыл взять остаток. Для 15 и не получается

...

Рейтинг:

0 / 0

14.06.2019, 12:52

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826576

Gennadiy Usov

Гость

BarloneGennadiy UsovЗдесь я не понял.
Если n =15, то (n-1)/2 = 7
2^7 = 64
И как получается (n-1)?Ну я там забыл взять остаток. Для 15 и не получаетсяА для каких чисел получится?

...

Рейтинг:

0 / 0

14.06.2019, 13:23

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826583

Gennadiy Usov

Гость

Barlone,

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

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

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

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 14.
Можно сказать, начинаем формировать первое подмножество простых чисел.

...

Рейтинг:

0 / 0

14.06.2019, 13:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826624

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovBarlone,

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

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

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

1678541, 1811573, 3400013, 3605429
Когда за дело берутся настоящие математики, у них получается лучше -
https://en.wikipedia.org/wiki/Baillie–PSW_primality_test
нет ни одного известного составного числа, походящего тест

...

Рейтинг:

0 / 0

14.06.2019, 14:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826677

Gennadiy Usov

Гость

Barlone,

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

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

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

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

Не нравится значение 3605429.
Может быть ошибка?

...

Рейтинг:

0 / 0

14.06.2019, 16:34

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39826711

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovBarlone,
Не нравится значение 3605429.
Может быть ошибка?
python

Код: plaintext

>>> pow(2,3605429//2,3605429)
3605428

все правильно

...

Рейтинг:

0 / 0

14.06.2019, 17:28

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39828988

Gennadiy Usov

Гость

Barlone,

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

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

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

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

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 10.
Можно сказать, начинаем формировать первое подмножество простых чисел.

...

Рейтинг:

0 / 0

21.06.2019, 06:33

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39828990

Gennadiy Usov

Гость

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

"Barlone,

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

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

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

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

При этом, в диапазоне от 1 до 200 по новому варианту достаточного теста количество простых чисел уменьшается с 26 до 10.
Можно сказать, начинаем формировать первое подмножество простых чисел."

...

Рейтинг:

0 / 0

21.06.2019, 06:41

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39828991

Gennadiy Usov

Гость

Или проще - (n-1)/2 - простое число.

...

Рейтинг:

0 / 0

21.06.2019, 06:43

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39828992

Gennadiy Usov

Гость

Barlone,

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

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

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

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

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

...

Рейтинг:

0 / 0

21.06.2019, 07:03

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39829631

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovЧто тогда получается?Пока получается, что вы берете гипотезы с потолка, без обоснований их правильности.

...

Рейтинг:

0 / 0

23.06.2019, 19:37

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39829757

Gennadiy Usov

Гость

BarloneGennadiy UsovЧто тогда получается?Пока получается, что вы берете гипотезы с потолка, без обоснований их правильности.Почему без обоснования и с потолка?

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

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

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

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

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

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

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

При этом отвергаются числа, показанные в 21908441 и в 21908732

...

Рейтинг:

0 / 0

24.06.2019, 10:55

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39829817

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 2 ¹⁰²⁴ , то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
^{Ну так то оно работает, тут угадали, это частный случай теста Люка}

...

Рейтинг:

0 / 0

24.06.2019, 13:33

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39829935

Gennadiy Usov

Гость

BarloneGennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 2 ¹⁰²⁴ , то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
^{Ну так то оно работает, тут угадали, это частный случай теста Люка} Спасибо за сообщение о частном случае теста Люка!

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

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

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

И заодно определить простые числа (n-1)/2.

...

Рейтинг:

0 / 0

24.06.2019, 15:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39830117

Gennadiy Usov

Гость

BarloneGennadiy Usov,
Ну допустим, это работает. Теперь, чтобы доказать простоту n, вам надо доказать простоту (n-1)/2. Если n порядка 2 ¹⁰²⁴ , то заметно легче не стало. А еще вы выкинули из рассмотрения значительную часть простых чисел.
^{Ну так то оно работает, тут угадали, это частный случай теста Люка} Вот появился ещё один тест.

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

И спрашивается: почему?

...

Рейтинг:

0 / 0

25.06.2019, 06:56

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39830119

Gennadiy Usov

Гость

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

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

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

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

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

Спрашивается: количество m вычислений по модулю не является слишком большим?
(с точки зрения проведения расчетов на компьютере в разумное время)

...

Рейтинг:

0 / 0

25.06.2019, 07:07

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39830289

Gennadiy Usov

Гость

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

Ведь надо найти все множители числа n - 1.

...

Рейтинг:

0 / 0

25.06.2019, 12:26

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39841239

Gennadiy Usov

Гость

Barlone,

что означает данный оператор python ( не нашел описания по 4-м параметрам)Barlonepython

Код: plaintext

>>> pow(2,3605429//2,3605429)
3605428

Он определяет простоту числа?

...

Рейтинг:

0 / 0

25.07.2019, 10:14

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39841640

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovBarlone,

что означает данный оператор python ( не нашел описания по 4-м параметрам)Barlonepython

Код: plaintext

>>> pow(2,3605429//2,3605429)
3605428

Он определяет простоту числа?Там три параметра, // - целочисленное деление
2 ^3605429/2 %3605429

...

Рейтинг:

0 / 0

25.07.2019, 20:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39841772

Gennadiy Usov

Гость

BarloneBarlonepython

Код: plaintext

>>> pow(2,3605429//2,3605429)
3605428

Там три параметра, // - целочисленное деление
2 ^3605429/2 %3605429Спасибо!

Ещё вопрос:
а в python есть функция поиска простоты числа, или надо определять простоту числа обычным "дедовским" способом?

...

Рейтинг:

0 / 0

26.07.2019, 10:27

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39841807

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Есть статья которая описывает библиотеку SymPy

https://www.geeksforgeeks.org/prime-functions-python-sympy/

...

Рейтинг:

0 / 0

26.07.2019, 11:25

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39842050

Gennadiy Usov

Гость

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

А как эту библиотеку подцепить к https://ideone.com/?

...

Рейтинг:

0 / 0

26.07.2019, 18:35

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39842056

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хм... да. Действительно Идеоновская сборка не знает эту библиотечку.

...

Рейтинг:

0 / 0

26.07.2019, 18:40

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39843697

Gennadiy Usov

Гость

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

И то, только до 2^200.

...

Рейтинг:

0 / 0

31.07.2019, 20:00

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39843789

Gennadiy Usov

Гость

Продолжил построение различных множеств простых чисел.

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

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

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

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

Эти числа проверены на факторизаторе чисел.

...

Рейтинг:

0 / 0

01.08.2019, 07:28

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39844469

Gennadiy Usov

Гость

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

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

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

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

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

В эту последовательность войдут все составные числа Мерсенна - Мр, у которых р - простое число.

...

Рейтинг:

0 / 0

02.08.2019, 10:25

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39844578

Gennadiy Usov

Гость

А далее - самое интересное!

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

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

Если получится понять поведение последовательности 21940432 ,
то задача определения простых чисел с помощью теста Ферма (и ещё чего-нибудь) будет решена.

...

Рейтинг:

0 / 0

02.08.2019, 12:44

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39844918

Gennadiy Usov

Гость

Решил сам определить последовательность чисел,
полученных в результате «ошибочности» теста Ферма.

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

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

В последовательности 21940432 рассматривались все нечётные числа.
В этом случае получается 172 составных числа.

...

Рейтинг:

0 / 0

03.08.2019, 12:55

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39845430

ёёёёё

Участник

Сообщения: 2 086

Рейтинг: 0 / 0

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

Числа есть, а хранить их негде. Бардак.

...

Рейтинг:

0 / 0

05.08.2019, 15:27

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39845452

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

05.08.2019, 16:03

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39845478

ёёёёё

Участник

Сообщения: 2 086

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

05.08.2019, 17:09

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39845532

Gennadiy Usov

Гость

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

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

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

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

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

Например, поиск простых чисел, аналогичный поиску 21939419

...

Рейтинг:

0 / 0

05.08.2019, 18:07

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39847894

Gennadiy Usov

Гость

maytonGennadiy UsovmaytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие?
Которое определяет достаточность теста простоты?Что за условия? Как вы их найдете?Просто никто не рассматривал составные числа, которые "проходят" тест Ферма.
Этих чисел немного, поэтому их можно анализировать.

Для начала - 21940591

...

Рейтинг:

0 / 0

11.08.2019, 09:31

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39847952

Gennadiy Usov

Гость

maytonЕсть статья которая описывает библиотеку SymPy

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

Например, вместе с isprime (n)

...

Рейтинг:

0 / 0

11.08.2019, 16:37

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39849420

Gennadiy Usov

Гость

Важно рассмотреть ещё один вопрос.

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

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

Насколько полученная последовательность простых чисел может помочь
в решении задачи поиска простых чисел в районе 2^1024?

...

Рейтинг:

0 / 0

14.08.2019, 18:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39849501

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Первые несколько штук (probable prime).

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989

...

Рейтинг:

0 / 0

14.08.2019, 21:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39849572

Gennadiy Usov

Гость

maytonПервые несколько штук (probable prime).

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989

И сколько времени ушло на поиск этих чисел?
И с помощью какого теста простоты?

...

Рейтинг:

0 / 0

15.08.2019, 07:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39849597

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

import java.math.BigInteger

object Main {

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

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

  }

}

Еще есть забавный косяк. Я написал за пару минут функцию bigPower для встроенного в Scala типа BigInt, полагая
что это бридж к java-шному BigInteger. Дальше обнаружил что bigInt не работает с функциями простоты и добавил
java-шный тип BigInteger. Поэтому в исходнике есть два разных типа от двух разных языков.

...

Рейтинг:

0 / 0

15.08.2019, 09:28

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39849599

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

15.08.2019, 09:41

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39849616

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Второте и третье число - близнецы кстати.

...

Рейтинг:

0 / 0

15.08.2019, 10:29

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850019

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

15.08.2019, 19:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850524

Gennadiy Usov

Гость

maytonПервые несколько штук (probable prime).

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989

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

Так более читаемо.
И можно зрительно отследить интервалы между найденными простыми числами.

...

Рейтинг:

0 / 0

16.08.2019, 18:35

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850589

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Есть Питонщики?

...

Рейтинг:

0 / 0

16.08.2019, 23:03

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850595

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
518
282
78
1212
772
1298
826
212
654
258
750
22
264
1020
84
168
600
554
168
340
450
1190
1030
260
366
2094
3222

...

Рейтинг:

0 / 0

16.08.2019, 23:24

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850623

Gennadiy Usov

Гость

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

Код: sql

1.
2.
3.
4.
5.

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178

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

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

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

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

Спасибо за информацию!

...

Рейтинг:

0 / 0

17.08.2019, 06:30

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850730

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

В префиксном коде.

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.

(8(9(8(8(4(6(5(6(7(4(3(1(1(5(7(9(5(3(8(6(4(6(5(2(5(9(5(3(9(4(5(1(2(3(6(6(8(0(8(9(8(8(4(8(9(4(7(1(1(5(3(2(8(6(3
(6(7(1(5(0(4(0(5(7(8(8(6(6(3(3(7(9(0(2(7(5(0(4(8(1(5(6(6(3(5(4(2(3(8(6(6(1(2(0(3(7(6(8(0(1(0(5(6(0(0(5(6(9(3(9
(9(3(5(6(9(6(6(7(8(8(2(9(3(9(4(8(8(4(4(0(7(2(0(8(3(1(1(2(4(6(4(2(3(7(1(5(3(1(9(7(3(7(0(6(2(1(8(8(8(8(3(9(4(6(7
(1(2(4(3(2(7(4(2(6(3(8(1(5(1(1(0(9(8(0(0(6(2(3(0(4(7(0(5(9(7(2(6(5(4(1(4(7(6(0(4(2(5(0(2(8(8(4(4(1(9(0(7(5(3(4
(1(1(7(1(2(3(1(4(4(0(7(3(6(9(5(6(5(5(5(2(7(0(4(1(3(6(1(8(5(8(1(6(7(5(2(5(5(3(4(2(2(9(3(1(4(9(1(1(9(9(7(3(6(2(2
(9(6(9(2(3(9(8(5(8(1(5(2(4(1(7(6(7(8(1(6(4(8(1(2(1(1(2(0(7(0(1(0(1)9(1))2(9(3))4(7(1))9(8(9)))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

)

...

Рейтинг:

0 / 0

17.08.2019, 23:49

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850789

Gennadiy Usov

Гость

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.

89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
518
282
78  и т.д

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

А если среди них есть составные числа, как иногда бывает с тестом Ферма?

...

Рейтинг:

0 / 0

18.08.2019, 12:49

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850804

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Не знаю. Как это проверить?

...

Рейтинг:

0 / 0

18.08.2019, 13:42

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850812

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

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

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

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.

    public BigInteger nextProbablePrime() {
        if (this.signum < 0)
            throw new ArithmeticException("start < 0: " + this);

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

        BigInteger result = this.add(ONE);

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

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

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

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

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

                result = result.add(TWO);
            }
        }

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.

    boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

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

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

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

...

Рейтинг:

0 / 0

18.08.2019, 14:44

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850813

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Полностью исходники (зеркало) OpenJDK можно скачать здесь https://github.com/unofficial-openjdk/openjdk

...

Рейтинг:

0 / 0

18.08.2019, 14:46

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850814

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Код: java

result.bitLength() > 6

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

Если переменная result имеет разрядную сетку больше чем 6 бит. По сути 6 бит это число более чем 64.
Еще аналог - целое логарифмирование по основанию 2.

...

Рейтинг:

0 / 0

18.08.2019, 14:51

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850859

Gennadiy Usov

Гость

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

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

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

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

Где-то 1 : 100

Максимальный из минимальных множителей составных чисел - 2971.

...

Рейтинг:

0 / 0

18.08.2019, 20:40

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850877

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Так я самый первый исходник не до конца скопипастил.

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

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

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

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

Код: sql

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

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

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.

    public BigInteger nextProbablePrime() {
        if (this.signum < 0)
            throw new ArithmeticException("start < 0: " + this);

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

        BigInteger result = this.add(ONE);

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

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

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

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

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

                result = result.add(TWO);
            }
        }

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

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

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

...

Рейтинг:

0 / 0

19.08.2019, 00:53

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850899

Gennadiy Usov

Гость

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

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

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

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

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

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

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

Я использовал в 21952070 2-й вариант

Код: sql

1.
2.
3.
4.
5.
6.

d = 2							
p = 7							
P = p + 1000000							
while p <= P: 							
	d = 6 - d						
	p = p + d

...

Рейтинг:

0 / 0

19.08.2019, 07:27

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850902

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Не особо. Я просто комментирую то как nextPrime уже реализован в языковых библиотеках.

...

Рейтинг:

0 / 0

19.08.2019, 07:33

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850904

Gennadiy Usov

Гость

maytonНе особо. Я просто комментирую то как nextPrime уже реализован в языковых библиотеках..... и пишу простенькие программы в порядке комментария

...

Рейтинг:

0 / 0

19.08.2019, 07:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39850912

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Меня интересовал Radix tree/trie. И всякие сжатые форматы хранения аналитики.

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

Вот такой вот загадочный мотиватор.

...

Рейтинг:

0 / 0

19.08.2019, 07:58

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851900

Gennadiy Usov

Гость

В продолжение сообщения 21952153 привожу код по перебору целых чисел с помощью массива

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

my_list = [30, 8, 1, 7, 11, 13, 17, 19, 23, 29]	
nm = my_list [0]		
em = my_list [1] - 1		
p0 = 0		
w = 0		
P = 10000007		
w1 = P//nm		
while w <= w1:		
	we = 1	
	we1 = we + em	
	while we <= we1:	
		p = p0 + (w-1) * nm +my_list [we + 1]
		
		we += 1
	w += 1

...

Рейтинг:

0 / 0

21.08.2019, 07:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851904

Gennadiy Usov

Гость

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

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

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

...

Рейтинг:

0 / 0

21.08.2019, 08:00

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851944

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

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

Хотя... могли брать по другому принципу.

...

Рейтинг:

0 / 0

21.08.2019, 10:10

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851948

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

И не забывайте что факторизация и тест на простоту это всё-таки не совсем одно и то-же.

...

Рейтинг:

0 / 0

21.08.2019, 10:14

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851970

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

21.08.2019, 10:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851974

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usovmaytonпропущено...

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

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

Зачем ты говоришь про общие корни? Как мы твои корни натянем на эту практическую реализацию.
Я понимаю ты идеалист. Я тебе еще в ферзевой задаче говорил что мы должны подходить очень
селективно к алгоритму основываясь на разной природе входных данных. Серебрянной пули не будет.
У нас будет десяток бронзовых пуль каждая из которых хорошо работает в данном диапазоне чисел
или ферзей или вектора входных данных и очень-очень плохо работаает на другом векторе входа.

...

Рейтинг:

0 / 0

21.08.2019, 10:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851978

Gennadiy Usov

Гость

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

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

Сейчас попробую проверить на 1000... повторных вычислений скорость определения:
- остатка по тесту Ферма для большого числа
- остатка после деления этого большого числа на серию произвольных чисел.

...

Рейтинг:

0 / 0

21.08.2019, 10:44

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851986

Gennadiy Usov

Гость

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

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

Или разные?

...

Рейтинг:

0 / 0

21.08.2019, 10:50

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39851997

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Рабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.

...

Рейтинг:

0 / 0

21.08.2019, 11:00

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852011

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

21.08.2019, 11:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852019

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy UsovmaytonРабин Миллер не факторизирует. И брут-форс просто определяет что число разделилсь на 1 делитель нацело. Например на 3.
Дальше - не идет. Алгоритм закончен. Число - составное.А если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.
Геннадий. Я вас уже считаю разработчиком. Читайте код. Последний делитель который мы делим методом грубой силы это число 41.

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

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

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

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

                result = result.add(TWO);
            }

...

Рейтинг:

0 / 0

21.08.2019, 11:32

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852027

Gennadiy Usov

Гость

maytonGennadiy UsovА если не нашелся делитель,
то когда нужно остановиться?
Ведь число очень-очень большое.
Геннадий. Я вас уже считаю разработчиком. Читайте код. Последний делитель который мы делим методом грубой силы это число 41.
Спасибо за доверие!

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

...

Рейтинг:

0 / 0

21.08.2019, 11:43

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852058

Gennadiy Usov

Гость

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

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

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

...

Рейтинг:

0 / 0

21.08.2019, 12:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852314

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usovmaytonпропущено...

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

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

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

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

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

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

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

                result = result.add(TWO);
            }

...

Рейтинг:

0 / 0

21.08.2019, 18:05

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852331

Gennadiy Usov

Гость

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

Я попробую представить свой вариант части кода (начало цикла, остальное - в зависимости от применения)

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

#p - исходное число			
prost_list = [23,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]			
s1 = 1			
sn = prost_list[0]			
while s1 <= sn:			
	q = prost_list[s1]		
	w2 = p % q		
		if w2 == 0:	
			 и т.д.

Количество простых чисел в массиве можно увеличить

...

Рейтинг:

0 / 0

21.08.2019, 18:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852334

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я не знаю почему 41. Я просто разворачиваю вложенность сорца и представляю его на суд в форуме
в читабельном виде.

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

...

Рейтинг:

0 / 0

21.08.2019, 18:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852352

Gennadiy Usov

Гость

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

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

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

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

...

Рейтинг:

0 / 0

21.08.2019, 20:03

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852409

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я не буду спорить с википедией. Просто приведу исходник.

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

    /**
     * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
     *
     * The following assumptions are made:
     * This BigInteger is a positive, odd number.
     */
    private boolean passesLucasLehmer() {
        BigInteger thisPlusOne = this.add(ONE);

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

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

        // Step 3
        return u.mod(this).equals(ZERO);
    }

...

Рейтинг:

0 / 0

21.08.2019, 22:44

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852465

Gennadiy Usov

Гость

Тут дело не в программе.

Главное:
какие чисел эта программа (тест Люка — Лемера) определила как простые?
(кроме чисел Мерсенна)

...

Рейтинг:

0 / 0

22.08.2019, 07:28

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852467

Gennadiy Usov

Гость

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

А как для произвольного числа определить эту степень 2 ?

...

Рейтинг:

0 / 0

22.08.2019, 07:32

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852497

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Не знаю.

...

Рейтинг:

0 / 0

22.08.2019, 09:09

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852537

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Тестов много разных...
https://ru.wikipedia.org/wiki/Псевдопростое_число_Люка
https://ru.wikipedia.org/wiki/Псевдопростое_число
https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа

...

Рейтинг:

0 / 0

22.08.2019, 10:12

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852554

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

По сорцам Люка параметризуется неким загадочным Символом Якоби.

...

Рейтинг:

0 / 0

22.08.2019, 10:29

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852562

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я нарисую блок-схему. Для Геннадия и для себя тоже.

...

Рейтинг:

0 / 0

22.08.2019, 10:40

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852587

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Нет в символе Якоби ничего загадочного. Это обобщение символа Лежандра на составные числа, и для простых чисел они совпадают.
Только вычисляют его (Якоби) не по определению, где нужно разложение на простые, а через квадратичный закон взаимности.
Для простого модуля символ Якоби позволяет определить, является ли какое-то число квадратичным вычетом по этому модулю, то есть существует ли квадратный корень из числа по модулю. (Например, 2 - квадратичный вычет по модулю 7, так как 3*3 mod 7 == 2)

...

Рейтинг:

0 / 0

22.08.2019, 11:41

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852678

Gennadiy Usov

Гость

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

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

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

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

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

Далее осталось найти пример работы теста Люка.

...

Рейтинг:

0 / 0

22.08.2019, 13:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852697

Gennadiy Usov

Гость

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

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

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

Кроме того, для очень больших чисел невозможно (нужно очень много времени) найти последовательность чисел Люка
- эти числа определяются от первого числа.

...

Рейтинг:

0 / 0

22.08.2019, 13:31

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852809

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovПолучается, что можно проверить только отдельные числа.
Не так. Последовательность Люка используется для проверки произвольного числа.

...

Рейтинг:

0 / 0

22.08.2019, 15:21

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852830

Gennadiy Usov

Гость

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

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

Или я ошибаюсь?

...

Рейтинг:

0 / 0

22.08.2019, 15:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852955

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Множество ненулевых остатков (вычетов) по модулю простого числа N - абелева группа порядка N-1. Что проверяет тест Ферма? Он проверяет, что порядок подгруппы, порожденной некоторым выбранным элементом, делит N-1. Когда он дает ложноположительный результат? Если N составное, то порядок группы будет φ(N). А порядок подгруппы, порожденной неким элементом, будет делителем φ(N). И тест Ферма сфейлится, когда этот делитель φ(N) окажется также и делителем N-1

...

Рейтинг:

0 / 0

22.08.2019, 19:28

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852958

Gennadiy Usov

Гость

А такой вопрос:

есть простое число N, для которого получаем (N - 1) значений теста Ферма.
Эти числа различны или нет?

...

Рейтинг:

0 / 0

22.08.2019, 19:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852960

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Кроме мультипликативной группы вычетов по модулю, можно сконструировать и всякие другие группы - матрицы (но она на Абелева - умножение матриц не коммутативно), полиномы, точки на эллиптической кривой , решения уравнения Пелля …
Коэффициенты всех этих матриц, полиномов, … можно брать по модулю числа N. И можно несколькими способами сконструировать группу, порядок которой для простого N будет N+1. И вот тут я не совсем уверен, но кажется, тест Люка проверяет, что порядок некой подгруппы такой группы делит N+1.

...

Рейтинг:

0 / 0

22.08.2019, 19:43

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852963

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovА такой вопрос:

есть простое число N, для которого получаем (N - 1) значений теста Ферма.
Эти числа различны или нет?Для простого N естественно все значения будут 1. Для составного будет 1, если порядок подгруппы делит N-1, и не 1, если не делит :)

...

Рейтинг:

0 / 0

22.08.2019, 19:47

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852968

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Вот смотрите: 21^64 % 65 == 1 - фейл, 65 = 5*13
Смотрим 21^1 % 65 == 21; 21^2 % 65 == 51; 21^3 % 65 == 31; 21^4 % 65 == 1; а дальше пойдет повтор - 21^5 % 65 == 21. То есть порядок подгруппы, порожденной 21, по модулю 65 равен 4. А 65-1 делится на 4. И тест фейлится.

...

Рейтинг:

0 / 0

22.08.2019, 20:05

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852971

Gennadiy Usov

Гость

Наверное, я не так сформулировал задачу.

Имелось в виду числа от 2^1 % 65 до 2^64 % 65.
Это тоже группа?

...

Рейтинг:

0 / 0

22.08.2019, 20:08

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852973

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

А, да, φ(65) = 4 * 12 = 48. Кажется, всегда, когда для составного N НОД(φ(N), N-1) > 2 можно найти значение, на котором тест Ферма сфейлится. (Но это не точно, в смысле доказать я сейчас не смогу).

...

Рейтинг:

0 / 0

22.08.2019, 20:09

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852975

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovНаверное, я не так сформулировал задачу.

Имелось в виду числа от 2^1 % 65 до 2^64 % 65.
Это тоже группа?Ну так их же 4 всего разных.

...

Рейтинг:

0 / 0

22.08.2019, 20:12

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852977

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Ой, не то написал

...

Рейтинг:

0 / 0

22.08.2019, 20:13

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852978

Gennadiy Usov

Гость

А если числа от от 2^1 % 59 до 2^58 % 59,
то числа будут разные?

...

Рейтинг:

0 / 0

22.08.2019, 20:14

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852980

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Для двойки (и любого другого числа по модулю 65) порядок группы будет каким-то делителем 48. Если этот делитель будет кратен 3, то он не делит 64, и тест Ферма покажет, что число составное. А если делитель не кратен трем, то в данном случае он будет также делителем 64.

...

Рейтинг:

0 / 0

22.08.2019, 20:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852982

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovА если числа от от 2^1 % 59 до 2^58 % 59,
то числа будут разные? не обязательно

...

Рейтинг:

0 / 0

22.08.2019, 20:19

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852983

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Порядок подгруппы может оказаться делителем N-1

...

Рейтинг:

0 / 0

22.08.2019, 20:21

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852985

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

BarloneПорядок подгруппы может оказаться делителем N-1Для простого N

...

Рейтинг:

0 / 0

22.08.2019, 20:21

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39852995

Gennadiy Usov

Гость

Но при этом может быть несколько одинаковых подгрупп для простого N. (например, 7, 31, 43)

...

Рейтинг:

0 / 0

22.08.2019, 20:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853001

Gennadiy Usov

Гость

Сделал код для теста Миллера — Рабина.

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

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

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

Как быть?

...

Рейтинг:

0 / 0

22.08.2019, 20:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853044

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov,

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

...

Рейтинг:

0 / 0

23.08.2019, 00:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853064

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Если тест Ферма для какого-то a mod N говорит, что число N псевдопростое, а тест Миллера — Рабина для этого же a - что N составное, то мы еще и делитель N нашли...

...

Рейтинг:

0 / 0

23.08.2019, 05:35

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853077

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy UsovСделал код для теста Миллера — Рабина.

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

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

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

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

Делай от 2 до 50 раундов проверки. Как здесь.

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return this.passesMillerRabin(rounds, random);
        } else {
            if (sizeInBits < 256) {
                rounds = 27;
            } else if (sizeInBits < 512) {
                rounds = 15;
            } else if (sizeInBits < 768) {
                rounds = 8;
            } else if (sizeInBits < 1024) {
                rounds = 4;
            } else {
                rounds = 2;
            }

            rounds = n < rounds ? n : rounds;
            return this.passesMillerRabin(rounds, random) && this.passesLucasLehmer();
        }

...

Рейтинг:

0 / 0

23.08.2019, 07:51

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853134

Gennadiy Usov

Гость

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

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

Тогда что важнее:
- то, что появилась 1
- то, что не появилось 1

...

Рейтинг:

0 / 0

23.08.2019, 10:22

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853139

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov, важнее то что алгоритм Миллера-Раввина относится к классу bounded error probabalistic,
как и функции хеширования и фильтры Блума. Но ты упорно пытаешся вытащить его из этой классификации
и перетащить в другую.

...

Рейтинг:

0 / 0

23.08.2019, 10:31

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853165

Gennadiy Usov

Гость

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

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

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

...

Рейтинг:

0 / 0

23.08.2019, 11:04

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853167

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov, можно задать тебе вопрос?

Как ты себе понимаешь вот этот предикат?

Код: java

this.passesMillerRabin(rounds, random) && this.passesLucasLehmer();

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

(я дам подсказку. this - это и есть твое число 2047)

...

Рейтинг:

0 / 0

23.08.2019, 11:11

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853174

Gennadiy Usov

Гость

maytonGennadiy Usov, можно задать тебе вопрос?
Как ты себе понимаешь вот этот предикат?

Код: java

this.passesMillerRabin(rounds, random) && this.passesLucasLehmer();

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

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

Вопрос в действии теста Миллера-Раввина,
чтобы была уверенность, что тест "помогает" находить простые числа.
А 2047 - это тестовый вариант.

...

Рейтинг:

0 / 0

23.08.2019, 11:27

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853188

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

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

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.

    /**
     * Returns {@code true} if this BigInteger is probably prime,
     * {@code false} if it's definitely composite.
     *
     * This method assumes bitLength > 2.
     *
     * @param  certainty a measure of the uncertainty that the caller is
     *         willing to tolerate: if the call returns {@code true}
     *         the probability that this BigInteger is prime exceeds
     *         {@code (1 - 1/2<sup>certainty</sup>)}.  The execution time of
     *         this method is proportional to the value of this parameter.
     * @return {@code true} if this BigInteger is probably prime,
     *         {@code false} if it's definitely composite.
     */
    boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

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

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

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

...

Рейтинг:

0 / 0

23.08.2019, 11:47

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853224

Gennadiy Usov

Гость

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

А насчет Люка, Вы 21955051 уже ответили, что не знаете как работает этот тест с обычным числом (не числом Мерсенна).
maytonПускай Барлон подскажет так оно или нет. Одна надежда на Барлона

...

Рейтинг:

0 / 0

23.08.2019, 13:03

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853228

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy UsovТест Миллера не отбивает составные числа!
А ну-ка нука.

Что-же он делает?

...

Рейтинг:

0 / 0

23.08.2019, 13:08

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853245

Gennadiy Usov

Гость

maytonGennadiy UsovТест Миллера не отбивает составные числа!А ну-ка нука.
Что-же он делает?Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые.

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

...

Рейтинг:

0 / 0

23.08.2019, 13:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853257

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usovmaytonпропущено...
А ну-ка нука.
Что-же он делает?Я хотел сказать, что тест Миллера не отбивает все составные числа. А также некоторые составные выдаёт за простые.

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

...

Рейтинг:

0 / 0

23.08.2019, 14:04

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853283

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

23.08.2019, 14:41

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853289

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я прошу прощения. Во избежание кривотолков я буду писать фактическое название функции
как это записано в исходниках JDK. Интерпретация - это будет второй вопрос.
passesMillerRabinpassesLucasLehmerResultfalsefalsefalsefalsetruefalsetruefalsefalsetruetruetrue

...

Рейтинг:

0 / 0

23.08.2019, 14:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853317

Gennadiy Usov

Гость

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

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

Теперь осталось найти следующий тест, который оставит ещё меньше псевдопростых.

...

Рейтинг:

0 / 0

23.08.2019, 15:41

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853355

Gennadiy Usov

Гость

Просьба помочь!

Код: sql

1.
2.
3.
4.
5.

pp = 55
p = pow(2, pp) - 1
t = p - 1
t = t / 2;
print (t)

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

А как сделать так, чтобы оно было целым?

...

Рейтинг:

0 / 0

23.08.2019, 16:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853378

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Код: python

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec  5 2015, 20:40:30) [MSC v.1500 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>>
>>> pp = 55
>>> p = 2*pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
54
>>>

...

Рейтинг:

0 / 0

23.08.2019, 17:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853384

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Блин... Вот так.

Код: python

1.
2.
3.
4.
5.
6.

>>> pp = 55
>>> p = 2**pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
18014398509481983

...

Рейтинг:

0 / 0

23.08.2019, 17:28

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853396

Gennadiy Usov

Гость

maytonБлин... Вот так.

Код: python

1.
2.
3.
4.
5.
6.

>>> pp = 55
>>> p = 2**pp - 1
>>> t = p - 1
>>> t = t / 2;
>>> print (t)
18014398509481983

Спасибо!

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

В то же время, нашел t = t // 2.
Знал об этом, и забыл.

...

Рейтинг:

0 / 0

23.08.2019, 17:51

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853477

Gennadiy Usov

Гость

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

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

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

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

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

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

...

Рейтинг:

0 / 0

24.08.2019, 13:13

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853483

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Никаких бОльших смыслов здесь не было добавлено.

...

Рейтинг:

0 / 0

24.08.2019, 14:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853498

Gennadiy Usov

Гость

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

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

Кстати, название - нечётное число - это то же является самым простым (предварительным) тестом простоты.

...

Рейтинг:

0 / 0

24.08.2019, 18:23

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853520

Gennadiy Usov

Гость

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

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

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

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

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

И уже на следующем шаге подключать более сложные тесты.

...

Рейтинг:

0 / 0

25.08.2019, 05:59

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853522

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

25.08.2019, 07:51

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853523

Gennadiy Usov

Гость

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

Разница по времени вычисления теста для одного числа n есть?

...

Рейтинг:

0 / 0

25.08.2019, 08:55

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853524

Gennadiy Usov

Гость

Только сейчас заметил, что если для теста Миллера-Раввина получаем случайное число 2,
то тест Миллера-Раввина превращается в тест Ферма.

...

Рейтинг:

0 / 0

25.08.2019, 08:59

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853535

Gennadiy Usov

Гость

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

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

При этом первая часть теста Миллера-Раввина принимает за простое число 341.

...

Рейтинг:

0 / 0

25.08.2019, 13:30

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853536

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy Usov, что за "первая часть"?

...

Рейтинг:

0 / 0

25.08.2019, 13:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853537

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

Разница по времени вычисления теста для одного числа n есть?Ну это вообще ерунда, и Ферма можно по разным основаниям считать.

...

Рейтинг:

0 / 0

25.08.2019, 13:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853540

Gennadiy Usov

Гость

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

Только при реальной проверке произвольного числа на простоту сколько оснований закладывается в программу?

...

Рейтинг:

0 / 0

25.08.2019, 13:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853541

Gennadiy Usov

Гость

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

Я пока проверяю первое условие (первая часть).

...

Рейтинг:

0 / 0

25.08.2019, 13:52

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853542

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovЯ пока проверяю первое условие (первая часть).Оно так не работает

...

Рейтинг:

0 / 0

25.08.2019, 13:57

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853544

Gennadiy Usov

Гость

BarloneGennadiy UsovЯ пока проверяю первое условие (первая часть).Оно так не работаетПочему не работает.

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

Подробности позднее.

...

Рейтинг:

0 / 0

25.08.2019, 14:14

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853552

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Так не работает же
Gennadiy UsovСделал код для теста Миллера — Рабина.

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

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

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

Как быть?В вики написано: "если число простое, то выполняется хотя бы одно из условий". Значит, если не одно из условий не выполняется, число точно составное. Вы проверили только одно. Это не дает ничего. Если первое условие выполнено, число может быть как простым, так и составным. Если первое условие не выполнено, а второе не проверялось, то число тоже может быть как простым, так и составным.

...

Рейтинг:

0 / 0

25.08.2019, 15:54

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853553

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

А в чем проблема то проверить второе условие? У вас есть s - количество младших нулевых битов в n-1. Вы полученное на первом шаге число s-1 раз возводите в квадрат по модулю n и каждый раз сравниваете с n-1.

...

Рейтинг:

0 / 0

25.08.2019, 16:07

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853554

Gennadiy Usov

Гость

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

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

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

Вот и вся история с географией.

...

Рейтинг:

0 / 0

25.08.2019, 16:08

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853556

Gennadiy Usov

Гость

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

Иначе можно договорить о доработке теста Миллера — Рабина с точки зрения:
выполнения двух условий.

...

Рейтинг:

0 / 0

25.08.2019, 16:12

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853558

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

25.08.2019, 16:33

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853559

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovИначе можно договорить о доработке теста Миллера — Рабина с точки зрения:
выполнения двух условий. Ну оба условия сразу выполниться никак не могут, сколько единицу в квадрат не возводи, она минус единицей не станет.

...

Рейтинг:

0 / 0

25.08.2019, 16:44

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853560

Gennadiy Usov

Гость

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

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

Я эти правила нарушил?
Где, в каком месте?

...

Рейтинг:

0 / 0

25.08.2019, 16:54

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853561

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Код: java

boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

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

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

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


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

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

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

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

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

Если я мешаю - то скажите и я не буду больше писать. Просто мне кажется что вы "ломитесь" в открытую дверь.

...

Рейтинг:

0 / 0

25.08.2019, 17:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853563

Gennadiy Usov

Гость

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

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

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

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

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

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

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

...

Рейтинг:

0 / 0

25.08.2019, 17:49

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853566

Gennadiy Usov

Гость

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

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

При этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).

...

Рейтинг:

0 / 0

25.08.2019, 18:21

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853567

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хорошо. Я понял.

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

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

Код: java

1.
2.

private boolean passesLucasLehmer() {
.....

Спрашивайте вопросы.

...

Рейтинг:

0 / 0

25.08.2019, 18:21

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853569

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python

...

Рейтинг:

0 / 0

25.08.2019, 18:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853573

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

25.08.2019, 19:02

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853574

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

25.08.2019, 19:03

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853575

Gennadiy Usov

Гость

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

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

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?

...

Рейтинг:

0 / 0

25.08.2019, 19:07

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853576

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

При таком раскладе Миллер+Люка будут выгоднее. Никто не хочет ждать годы для проверки числа.

...

Рейтинг:

0 / 0

25.08.2019, 19:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853577

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

25.08.2019, 19:19

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853621

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovПри этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).Ерунду вы написали. Вообще-то, если в математической формуле написано "a эквивалентно минус единице по модулю N" (значок такой ≡ из трех черточек), то в программе это будет выглядеть как "a % N == N-1", потому что -1 и N-1 попадают в один класс эквивалентности по модулю N.

...

Рейтинг:

0 / 0

26.08.2019, 04:34

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853622

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Возьмем например простое число N=13, N-1 = 4*3. d=3, s=2
Взяв a=3, получим 2^3 % 13 == 1 - выполнилось первое условие.
Взяв a=10, получим 10^3 % 13 == 12 это минус единица :) и тут сразу выполнилось второе условие, при r==0.
Взяв а=2, получим 2^3 %13 == 8. Надо возводить в квадрат. 8^2 % 13 == 12 вот она минус единица при r==1.

А если у нас составное число, например N=21, N-1 = 4*5, d=5, s=2
Берем а=8, 8^5 % 21 == 8. Первое не выполнено. Берем квадрат 8^2 % 21 == 1. И второе условие не выполнено, значит число составное.

...

Рейтинг:

0 / 0

26.08.2019, 04:53

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853623

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Последний случай кстати самый интересный - когда для какого-то числа а ≠ ±1 mod N оказывается что a² ≡ 1 mod N , то gcd(a+1, N) и gcd(a-1, N) дадут нам делители N.

...

Рейтинг:

0 / 0

26.08.2019, 05:11

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853636

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

26.08.2019, 08:21

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853640

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

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

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?ты же сам ответ дал 21957011

...

Рейтинг:

0 / 0

26.08.2019, 08:36

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853678

Gennadiy Usov

Гость

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

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

Нам же нужно повысить степень, так называемой, "псевдопростоты",
которая должна, по каким-нибудь своим законам, стремиться к простоте.

...

Рейтинг:

0 / 0

26.08.2019, 11:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853685

Gennadiy Usov

Гость

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

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

То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!

...

Рейтинг:

0 / 0

26.08.2019, 11:25

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853702

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

BarlonemaytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

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

...

Рейтинг:

0 / 0

26.08.2019, 12:30

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853749

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

BarloneЕстественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V ^n+m и U ^n+m через V ⁿ , V ^m , U ⁿ , U ^m

...

Рейтинг:

0 / 0

26.08.2019, 14:56

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853848

Gennadiy Usov

Гость

BarloneGennadiy UsovЧтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!Ага, и чтобы повести тест Ферма для этого числа, надо посчитать а ⁽²¹⁰²⁴ -2) но это же не значит, что нужно 2 ¹⁰²⁴ -3 умножений на а.
BarloneЕстественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V ^n+m и U ^n+m через V ⁿ , V ^m , U ⁿ , U ^m Если я правильно понял, числа V ^{2^1024-1} и U ^{2^1024-1} нужно разложить на V и U.
А эти V и U разложить на следующие V и U. И т.д.

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

Кстати, хорошо делить число, когда оно чётное. А если очередное число нечётное?

...

Рейтинг:

0 / 0

26.08.2019, 18:07

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853856

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy Usov,
да всё так же, как с возведением в степень
Из U1,V1 получаем U2,V2, из них U4,V4, … и дальше по степеням двойки. Ну и по двоичному представлению нужного значения собираем результат - например, комбинируя пару U1,V1 c U4,V4 - получим U5,V5.

...

Рейтинг:

0 / 0

26.08.2019, 18:32

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853860

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Формулы есть в английской вики

...

Рейтинг:

0 / 0

26.08.2019, 18:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853876

Gennadiy Usov

Гость

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

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

Это ограничение для Python?

...

Рейтинг:

0 / 0

26.08.2019, 19:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853882

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Не знаю. Давайте Python-специфичные вопросы задавать тут https://www.sql.ru/forum/php-perl

...

Рейтинг:

0 / 0

26.08.2019, 19:35

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853888

Gennadiy Usov

Гость

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

Перед этим запустил программу с тестом Миллера-Рабина, и оказалось, что этот тест хорошо подходит для определения чисел Мерсенна.
На своём стареньком компьютере нашел все числа Мерсенна до 9941 где-то за 2 часа.

...

Рейтинг:

0 / 0

26.08.2019, 19:51

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853893

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Код: python

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

from sys import stdout
from math import sqrt, log
 
def is_prime ( p ):
  if p == 2: return True # Lucas-Lehmer test only works on odd primes
  elif p <= 1 or p % 2 == 0: return False
  else:
    for i in range(3, int(sqrt(p))+1, 2 ): 
      if p % i == 0: return False
    return True

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

Код: plaintext

1.
2.
3.
4.
5.

       uint64_t step = 4;
        

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

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

...

Рейтинг:

0 / 0

26.08.2019, 20:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853901

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

26.08.2019, 20:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853904

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

26.08.2019, 20:51

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853906

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

26.08.2019, 20:54

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853909

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

26.08.2019, 20:56

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853920

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

А то меня терзают смутные сомнения.

...

Рейтинг:

0 / 0

26.08.2019, 21:50

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853975

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

А то меня терзают смутные сомнения. https://ru.wikipedia.org/wiki/Умножение_Карацубы

...

Рейтинг:

0 / 0

27.08.2019, 05:15

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39853987

Gennadiy Usov

Гость

maytonGennadiy UsovЯ уже приводил чередование 4 и 2 21952153 .
Накопление простых в массиве может когда-то прекратиться.(на больших числах)А тебе много и не надо. Накопи простых хотя-бы тыщу.
Большая часть делителей отбивается на самых ранних шагах.Можно применить "ленивый алгоритм накопленных простых чисел".
О нём уже было сказано 21954752 .
Поскольку там ошибка, привожу ещё раз (без ошибки)

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

#p - исходное число			
prost_list = [22,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]			
s1 = 1			
sn = prost_list[0]			
while s1 <= sn:			
	q = prost_list[s1]		
	w2 = p % q		
		if w2 == 0:	
			 и т.д.

В массив можно записать хоть 1000 чисел.

...

Рейтинг:

0 / 0

27.08.2019, 07:50

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854157

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Почему 22 ?

...

Рейтинг:

0 / 0

27.08.2019, 13:05

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854160

Gennadiy Usov

Гость

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

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

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

Осталось проверять расстояние исследуемого числа от предыдущего "квадрата N",
и если получаемое расстояние превышает (4*N+4) от этого "квадрата N",
то определяется новый "квадрат N+1", равный увеличению предыдущего "квадрата N" на (4*N+4).

...

Рейтинг:

0 / 0

27.08.2019, 13:14

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854163

Gennadiy Usov

Гость

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

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

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

Кстати, я уже это демонстрировал на предыдущих топиках.

...

Рейтинг:

0 / 0

27.08.2019, 13:19

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854198

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Почитал про Питон.

Длину массива берут так.

Код: python

1.
2.
3.
4.

>>> prost_list = [22,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]
>>> len(prost_list)
23
>>>

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

...

Рейтинг:

0 / 0

27.08.2019, 14:12

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854344

Gennadiy Usov

Гость

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

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

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

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

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

Есть составные числа, для которых только 1 только по второму условию:
39, 105.
Поэтому по второму условию значение 1 не подходит.

...

Рейтинг:

0 / 0

27.08.2019, 18:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854382

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy Usov,

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

Код: plaintext

1.
2.
3.
4.

Почитайте про первообразный корень .

А потом выпишите такую же табличку для составного числа. Только надо как-то еще мелкими циферками в каждую клеточку дописать остатки по каждому сомножителю этого числа. Прочитайте про китайскую теорему об остатках .
А чтобы понять, как получаются псевдопростые, надо сделать такую табличку для составного числа, у которого большой НОД(φ(n), n-1). Ну например 91=7*13, НОД(90, 72)=18. Правда, табличка большая получится, но если над ней помедитировать, то озарение обязательно придет.

...

Рейтинг:

0 / 0

27.08.2019, 20:35

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854393

Gennadiy Usov

Гость

Barlone,

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

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

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.

...

Рейтинг:

0 / 0

27.08.2019, 21:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854395

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

27.08.2019, 21:23

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854397

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy Usov,

Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.

...

Рейтинг:

0 / 0

27.08.2019, 21:25

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854398

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovBarlone,

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

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

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.Вопрос как раз в том, как получаются псевдопростые.

...

Рейтинг:

0 / 0

27.08.2019, 21:34

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854400

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Я могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)

...

Рейтинг:

0 / 0

27.08.2019, 21:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854441

Gennadiy Usov

Гость

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

Здесь можно говорить о подмножестве простых чисел, для которых существует достаточное условие (примерно как в 21907153 ).BarloneЯ могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)С удовольствием прочитаю.

...

Рейтинг:

0 / 0

28.08.2019, 07:01

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854454

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovУвеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример - 21956300 ),
из-за которых эти числа принимаются тестом как простые.Не так это работает. Каждый раунд говорит либо "число точно составное", либо "не уверен, может быть простым." Если хотя бы один из раундов сказал, что число точно составное - то оно таки составное.
А чтобы доказать, что число простое, надо очень много раундов, порядка log(n) - это уже детерминированный вариант теста.

...

Рейтинг:

0 / 0

28.08.2019, 07:58

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854455

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov,

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

Первый раунд который детектировал составное - отменяет все результаты до этого.

...

Рейтинг:

0 / 0

28.08.2019, 08:01

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854470

Gennadiy Usov

Гость

У меня 2 вопроса ( с учетом примера 21956300 ) для чисел 2047 и 2053:

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

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

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

...

Рейтинг:

0 / 0

28.08.2019, 09:01

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854621

Gennadiy Usov

Гость

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

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

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

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

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

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

...

Рейтинг:

0 / 0

28.08.2019, 13:31

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854625

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

28.08.2019, 13:38

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854745

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Поэтому код с комментариями эффективнее чем просто текст который все не поняли
или интерпретировали по разному. Вот такие они... программисты.

...

Рейтинг:

0 / 0

28.08.2019, 16:15

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854748

Gennadiy Usov

Гость

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

По другому коду или по алгоритму?

...

Рейтинг:

0 / 0

28.08.2019, 16:20

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854753

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Не могу сказать. Это очень творческий процесс. Впрочем как и всё чем мы тут занимаемся.

...

Рейтинг:

0 / 0

28.08.2019, 16:25

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854855

Gennadiy Usov

Гость

maytonЕсли ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне:

Код: python

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

import random					
import math					
aaa1 = 0					
aaa2 = 0					
p =5					
P = p + 110					
while p <=P:					
	print (p)				
	t = p - 1				
	s = 0				
	while (t % 2 == 0):				
		t //= 2;			
		s += 1;			
	t1 = t//1				
	y = math.log( p )				
	#print (t,s)				
	y1 = 2				
	while y1 <= p-2:				
		#c = random.randint(2, p-2)			
		#print (c,y1)			
		x = pow(y1, t1, p)			
		print ("y",x,t1,y1)			
		y1 +=1			
	p +=2

...

Рейтинг:

0 / 0

28.08.2019, 19:19

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854899

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov

Код: python

1.
2.
3.

	y = math.log( p )				

		x = pow(y1, t1, p)

Мне кажется тут ослаблен контроль над типами. Кажется что натуральный логарифм и степень
возвращают число с плавающей точкой. А это не очень согласуется с решаемой задачей где
везде и всегда будут целые числа произвольной точности (arbitrary precision).

...

Рейтинг:

0 / 0

28.08.2019, 23:34

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854903

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Почитал Википедию.

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

Это Люка-Лемьер-Ризель (LLT) предположительно. Поэтому все что я писал надо читать с поправкой по этому названию.

...

Рейтинг:

0 / 0

28.08.2019, 23:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854930

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovmaytonЕсли ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне:

Код: python

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

import random					
import math					
aaa1 = 0					
aaa2 = 0					
p =5					
P = p + 110					
while p <=P:					
	print (p)				
	t = p - 1				
	s = 0				
	while (t % 2 == 0):				
		t //= 2;			
		s += 1;			
	t1 = t//1				
	y = math.log( p )				
	#print (t,s)				
	y1 = 2				
	while y1 <= p-2:				
		#c = random.randint(2, p-2)			
		#print (c,y1)			
		x = pow(y1, t1, p)			
		print ("y",x,t1,y1)			
		y1 +=1			
	p +=2

Код недоделанный.
После x = pow(y1, t1, p) надо еще

Код: plaintext

1.
2.

z = 0
while z < s and x != 1 and x != p-1

...

Рейтинг:

0 / 0

29.08.2019, 06:16

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854931

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

x = x*x % p

...

Рейтинг:

0 / 0

29.08.2019, 06:17

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39854932

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Недописанное ушло, 2 раза

Код: plaintext

1.
2.
3.
4.

z = 0
while z < s and x != 1 and x != p-1
   x = x*x % p 
   z = z + 1

...

Рейтинг:

0 / 0

29.08.2019, 06:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855147

Gennadiy Usov

Гость

BarloneКод недоделанный.
После x = pow(y1, t1, p) надо еще

Код: plaintext

1.
2.
3.
4.

z = 0
while z < s and x != 1 and x != p-1
   x = x*x % p 
   z = z + 1

Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Этот код необходим для оценки показаний остатков по модулю после применения различных случайных чисел.

...

Рейтинг:

0 / 0

29.08.2019, 13:51

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855160

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Gennadiy UsovА как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.

...

Рейтинг:

0 / 0

29.08.2019, 14:06

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855223

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovЭто второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.

...

Рейтинг:

0 / 0

29.08.2019, 15:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855251

Gennadiy Usov

Гость

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

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

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

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

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

Была составлена программа, были получены результаты, в сообщении 21958523 показаны основные выводы,
а в сообщении 21959374 показан код такой программы на Питоне.

...

Рейтинг:

0 / 0

29.08.2019, 15:55

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855256

Gennadiy Usov

Гость

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

Была такая игра: каждый в цепочке на ухо сообщает другому в цепочке слово, и какое слово пролучается в конце цепочки.
Или что-то похожее...

...

Рейтинг:

0 / 0

29.08.2019, 16:00

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855370

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Основные алгоритмы описаны в Википедии.

Но этот форум обычно обсуждает их реализации на конкретных языках и конфигурациях.

...

Рейтинг:

0 / 0

29.08.2019, 21:40

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855401

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy UsovDimitry Sibiryakovпропущено...
Подавляющее большинство делает это копипастом с гугля.То есть, основополагающие алгоритмы никто не читает?очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчас

...

Рейтинг:

0 / 0

30.08.2019, 00:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855430

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dimitry SibiryakovGennadiy UsovА как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.Некоторые тут и даже и копипаст не могут.

...

Рейтинг:

0 / 0

30.08.2019, 08:34

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855434

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

kealon(Ruslan)очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчасНу конечно, не рационально каждый раз писать всё с нуля. Есть готовые библиотеки, в том числе с открытыми исходниками. Можно посмотреть, оценить удобство api и качество кода, выбрать подходящее решение.

...

Рейтинг:

0 / 0

30.08.2019, 08:45

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855535

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Геннадий любит лично все обследовать.

...

Рейтинг:

0 / 0

30.08.2019, 11:19

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855606

Gennadiy Usov

Гость

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

Может быть, что-то и найдётся...

...

Рейтинг:

0 / 0

30.08.2019, 12:35

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855614

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy UsovmaytonГеннадий любит лично все обследовать. Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.

...

Рейтинг:

0 / 0

30.08.2019, 12:47

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855636

Gennadiy Usov

Гость

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

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

А насчет "кривого недотеста"? Кажется, это похвала в квадрате.

...

Рейтинг:

0 / 0

30.08.2019, 13:25

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855935

Gennadiy Usov

Гость

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

Так какое количество раундов выбрать?

...

Рейтинг:

0 / 0

31.08.2019, 11:44

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855950

Gennadiy Usov

Гость

Решил проверить с помощью простенькой программы на Питоне:

Код: python

1.
2.
3.
4.

iimport math
x = pow(2, 1024)
y = math.log( x )
print y

Получилось
709.782712893

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

А если уменьшить количество раундов в 2, 3, 4 раза?

...

Рейтинг:

0 / 0

31.08.2019, 12:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855955

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Усов. У меня идея появилась.

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

Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etc

...

Рейтинг:

0 / 0

31.08.2019, 13:00

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855959

Gennadiy Usov

Гость

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

Я же хочу иметь достаточный тест на определение простых чисел.
Пусть это будут не все простые числа, а, например, половина всех простых чисел (подмножество простых чисел).

...

Рейтинг:

0 / 0

31.08.2019, 13:21

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855961

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Gennadiy UsovЯ же хочу иметь достаточный тест на определение простых чисел.
К слову "достаточный" требуется уточнение "для чего".

...

Рейтинг:

0 / 0

31.08.2019, 13:39

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855962

Gennadiy Usov

Гость

Dimitry SibiryakovGennadiy UsovЯ же хочу иметь достаточный тест на определение простых чисел.К слову "достаточный" требуется уточнение "для чего".Рассмотрим небольшую задачу.

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

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

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

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

Главное, мы получаем не псевдопростые числа, а простые числа.

...

Рейтинг:

0 / 0

31.08.2019, 13:55

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855972

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Почему 2000 ?

...

Рейтинг:

0 / 0

31.08.2019, 15:57

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855975

Gennadiy Usov

Гость

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

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

У нас либо 1024, либо 2048

...

Рейтинг:

0 / 0

31.08.2019, 16:10

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855981

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov, будет детерминизм?

...

Рейтинг:

0 / 0

31.08.2019, 16:44

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855982

Gennadiy Usov

Гость

maytonGennadiy Usov, будет детерминизм?А куда он денется?

...

Рейтинг:

0 / 0

31.08.2019, 16:48

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855984

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy UsovmaytonGennadiy Usov, будет детерминизм?А куда он денется?
А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.

...

Рейтинг:

0 / 0

31.08.2019, 16:58

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855988

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

31.08.2019, 17:20

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855991

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

maytonGennadiy Usovпропущено...
А куда он денется?
А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.
В продолжение детерминизма и куда он денется. Я просто поставлю вопрос.

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

0..1023

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

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

Как это повлияет на результат повторного эксперимента? Зачем вообще случайность при полном покрытии?

Код: java

    
    /**
     * Constructs a randomly generated BigInteger, uniformly distributed over
     * the range 0 to (2<sup>{@code numBits}</sup> - 1), inclusive.
     * The uniformity of the distribution assumes that a fair source of random
     * bits is provided in {@code rnd}.  Note that this constructor always
     * constructs a non-negative BigInteger.
     *
     * @param  numBits maximum bitLength of the new BigInteger.
     * @param  rnd source of randomness to be used in computing the new
     *         BigInteger.
     * @throws IllegalArgumentException {@code numBits} is negative.
     * @see #bitLength()
     */
    public BigInteger(int numBits, Random rnd) {
        this(1, randomBits(numBits, rnd));
    }

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

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

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

...

Рейтинг:

0 / 0

31.08.2019, 17:34

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39855993

Gennadiy Usov

Гость

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

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

Поэтому желательно иметь другой принцип поиска остатков по mod.

...

Рейтинг:

0 / 0

31.08.2019, 17:59

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39856033

Dimitry Sibiryakov

Участник

Сообщения: 54 521

Рейтинг: 0 / 0

Gennadiy Usovдопустим для RSA.
Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.

...

Рейтинг:

0 / 0

31.08.2019, 22:09

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39856063

Gennadiy Usov

Гость

Dimitry SibiryakovGennadiy Usovдопустим для RSA.Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.Простоту полученных чисел может подтвердить только алгоритм Эратосфена - полный перебор всех делителей от 3 до ...

...

Рейтинг:

0 / 0

01.09.2019, 05:18

| Ответить | Цитировать | Написать

Ещё раз о тесте Ферма

#39862965

Gennadiy Usov

Гость

Gennadiy UsovDimitry SibiryakovДля "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.Простоту полученных чисел может подтвердить только алгоритм Эратосфена - полный перебор всех делителей от 3 до ...Простоту полученных чисел может подтвердить ещё новый эвристический алгоритм 21968895 .

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

А эвристический алгоритм формирует последовательность, состоящую из всех простых чисел (пока проверено до 600 000 000).

...

Рейтинг:

0 / 0

17.09.2019, 16:44

| Ответить | Цитировать | Написать

283 сообщений из 283, показаны все 12 страниц

все

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

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

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?all=1&fid=16&tid=1339906]:	0ms
get settings:	9ms
get forum list:	11ms
check forum access:	4ms
check topic access:	4ms
track hit:	167ms
get topic data:	13ms
get forum data:	3ms
get page messages:	315ms
get tp. blocked users:	2ms
others:	11ms

total:	539ms