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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

за сим общество криптологов покину т.к. явно не моя тема..
13 июн 19, 06:19    [21907574]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 12   вперед  Ctrl      все
Все форумы / Программирование Ответить