|
|
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
В вики говорится о том, что к вероятностным тестам простоты относят тест Ферма. При определении чисел Мерсенна тест Ферма часто показывает, что очередное число из последовательности - простое. А на самом деле, большое количество чисел Мерсенна, определённых тестом Ферма как простые, не являются простыми числами. А кроме чисел Мерсенна есть ли ещё примеры «ошибочности» теста Ферма? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.06.2019, 20:11 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Как известно,тест простоты Ферма для простого числа имеет вид: . (в общем виде – основание степени не 2, а произвольное число число а, которое не делится на n.) Это условие является необходимым условием, но не достаточным. Данному условию удовлетворяет бесконечное множество целых чисел, среди которых есть подмножество простых чисел. Ставится задача: из подмножества простых чисел выделить меньшее подмножество простых чисел, для которых тест Ферма будет достаточным. То есть, найти новое условие, которое будет достаточным для теста Ферма при определении простых чисел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 06:47 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
SynopticКурсовик?Нет. Просто интересная задача. Есть число (целое, нечётное). Как быстро определить: простое это число или нет? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 11:15 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Gennadiy Usov, их не так много по понятиям баз данных, особенно с учётом того что в обычном программировании есть некоторые ограничения из-за типа данных, соответственно проще держать список простых чисел в базе и делать проверку на exists из этого списка, т.е. необходимость сложно-красивой математической проверки/вывода/доказательства по всем правилам науки - отпадают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 11:27 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Я так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 12:18 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
vikkivGennadiy Usov, их не так много по понятиям баз данных, особенно с учётом того что в обычном программировании есть некоторые ограничения из-за типа данных, соответственно проще держать список простых чисел в базе и делать проверку на exists из этого списка, т.е. необходимость сложно-красивой математической проверки/вывода/доказательства по всем правилам науки - отпадают.А что, база данных простых чисел существует до ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 12:30 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
maytonЯ так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.Размечтались... Будет топик намного короче. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 13:16 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
maytonЯ так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.задача 21907153 сформулирована некорректно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 19:46 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
SiemarglmaytonЯ так понимаю... стартовал долгоиграющий топик. Ну что-ж будем ждать математиков.задача 21907153 сформулирована некорректноИ в чём некорректность? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 19:50 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovSynopticКурсовик?Нет. Просто интересная задача. Есть число (целое, нечётное). Как быстро определить: простое это число или нет?Современная математика не знает такого способа. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 20:29 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
BarloneGennadiy UsovПросто интересная задача. Есть число (целое, нечётное). Как быстро определить: простое это число или нет?Современная математика не знает такого способа.А как же куча тестов простоты, а как же алгоритм Эратосфена? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 20:35 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Мне кажется что вероятностные тесты простоты мы уже обсуждали. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 20:37 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
maytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие? Которое определяет достаточность теста простоты? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 20:45 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovmaytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие? Которое определяет достаточность теста простоты? Что за условия? Как вы их найдете? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.06.2019, 21:50 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovSiemarglпропущено... задача 21907153 сформулирована некорректноИ в чём некорректность? Ставится задача: из подмножества простых чисел выделить меньшее подмножество простых чисел, для которых тест Ферма будет достаточным. То есть, найти новое условие, которое будет достаточным для теста Ферма при определении простых чисел. Если выбросить тавтологию, то задача в том, что найти условие, которое будет достаточным для при определении простых чисел. т.е формулу простых чисел, что невозможно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 00:18 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Siemarglт.е формулу простых чисел, что невозможно какой-то совсем однозначный вывод сбивающий с пути рационального решения вопроса, ещё раз напомню если то что выше не понято: в бизнес-задачах организаций порядки области значений не настолько большие, и вот как раз для этих диапазонов в принципе генерация списка (около 10% от всего диапазона) простых чисел - не проблема так что лучше-бы не отрываться от реалий при разработке систем (помня о заложенных ограничениях) - тогда всё получится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 01:33 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
vikkiv, а ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 01:39 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Siemarglа ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп? предполагаю что сосут из пальцев наверное другие, у кого уже такая привычка сложилась и жестко в терминологию вошло, у меня выводы по реалиям бизнес задач на собственной практике работы в коммерческих организациях. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 04:59 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
vikkivSiemarglа ты откуда вдруг высосал из пальца ограничение про бизнес-задачи итп? предполагаю что сосут из пальцев наверное другие, у кого уже такая привычка сложилась и жестко в терминологию вошло, у меня выводы по реалиям бизнес задач на собственной практике работы в коммерческих организациях.Единственная бизнес-задача, для которой нужны простые числа - RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 05:37 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovmaytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие? Которое определяет достаточность теста простоты?Ну есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 05:45 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovBarloneпропущено... Современная математика не знает такого способа.А как же куча тестов простоты, а как же алгоритм Эратосфена?Ну там было "быстро". А алгоритм Эратосфена - это совсем не быстро, и вообще по объему требуемой памяти нереализуемо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 05:48 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
BarloneЕдинственная бизнес-задача, для которой нужны простые числа - RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.А зачем хранить? По мере нахождения простых чисел, эти числа "сразу поступают в работу". Или "ждут своей очереди". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 06:15 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
BarloneНу есть отдельный (не вероятностный) тест для чисел Мерсенна, он не связан с тестом Ферма.Какой? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 06:16 |
|
||
|
Ещё раз о тесте Ферма
|
|||
|---|---|---|---|
|
#18+
Barlone..Единственная бизнес-задача, для которой нужны простые числа - RSA шифрование... ну может быть конечно, однако даже на ближайшее будущее расчётных мощностей для взлома 128-битных ключей (пи Е38) на период их (короткой) жизни - пока явно не хватает. в контексте форума о базах данных: для 1024битного ключа (так понимаю ассиметричного, т.к. при симметричном так много не надо) bigint с их Е63 отпадает так-же как и decimal/real (Е38), разве что float с Е308 наиболее близок и GUID ещё кандидат с их 16ти байтным размером. за сим общество криптологов покину т.к. явно не моя тема.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2019, 06:19 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=39825681&tid=1339906]: |
0ms |
get settings: |
11ms |
get forum list: |
20ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
42ms |
get topic data: |
14ms |
get forum data: |
2ms |
get page messages: |
65ms |
get tp. blocked users: |
1ms |
| others: | 13ms |
| total: | 176ms |
| 0 / 0 |
