Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Теоретическое обоснование теста Рабина-Миллера
СообщениеДобавлено: 08 сен 2012, 20:38 
Не в сети
Начинающий
Зарегистрирован:
08 сен 2012, 20:29
Сообщений: 6
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Всем доброго времени суток. В общем, мой преподаватель дал мне задание: указать ДВА (!) "факта" или "теоретических обоснования" теста Рабина-Миллера. Первое, что приходит в голову - это малая теорема Ферма, но что же второе?! Если кто-либо предложит какие-либо варианты - буду несказанно рад.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теоретическое обоснование теста Рабина-Миллера
СообщениеДобавлено: 09 сен 2012, 00:43 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13534
Откуда: Москва
Cпасибо сказано: 1290
Спасибо получено:
3616 раз в 3175 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Факт 1.
Алгоритм Миллера — Рабина не зависит от справедливости гипотезы, но является вероятностным. Он гарантированно распознает простые и составные числа при условии выполнения расширенной гипотезы Римана.

Факт 2.
Если число a является свидетелем простоты составного нечетного числа m, то число m в свою очередь называется сильно псевдопростым по основанию a. Если число m является сильно псевдопростым по основанию a, то оно также является псевдопростым Ферма по основанию a.
Например, сильно псевдопростые числа по основанию 2 образуют последовательность:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, … (последовательность A001262 в OEIS) - http://oeis.org/A001262

а по основанию 3 — последовательность:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, … (последовательность A020229 в OEIS) - http://oeis.org/A020229

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Avgust "Спасибо" сказали:
Alexdemath
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 2 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Теоретическое распределение гипотеза

в форуме Математическая статистика и Эконометрика

stranger99

1

305

12 июн 2018, 13:06

Теоретическое определение предела

в форуме Пределы числовых последовательностей и функций, Исследования функций

SashaKvint

5

274

29 окт 2017, 16:29

Дуга эллипса по проекции (практическо-теоретическое зад-е)

в форуме Аналитическая геометрия и Векторная алгебра

AAANorilsk

9

371

24 июл 2017, 22:43

Математическое обоснование ответа

в форуме Дискретная математика, Теория множеств и Логика

AlexKostal

5

536

06 апр 2021, 12:40

Математическое обоснование зависимости

в форуме Математическая статистика и Эконометрика

Aster379

3

238

14 июн 2018, 10:50

Обоснование схемы доказательства

в форуме Дискретная математика, Теория множеств и Логика

Andy

1

256

09 янв 2017, 15:41

Две задачки из теста

в форуме Алгебра

ustas6873

11

676

26 фев 2015, 16:45

Уравнения с разделяющими переменными - строгое обоснование

в форуме Размышления по поводу и без

searcher

1

116

25 дек 2019, 22:43

Обоснование шестимерной модели пространства - времени

в форуме Размышления по поводу и без

ivashenko

15

1305

29 май 2014, 23:17

Задача из психометрического теста 3

в форуме Геометрия

ustas6873

5

397

26 фев 2015, 15:58


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: Yandex [bot] и гости: 43


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved