М.Полянскому: об одной задаче факторизации

Начать новую тему   Ответить на тему

Перейти вниз

М.Полянскому: об одной задаче факторизации

Сообщение автор Михалыч в Пн Мар 07, 2011 1:34 pm

Помнится, что Вы интересовались задачей о том, когда натуральное представимо в виде произведения РОВНО двух простых.
Появилась одна НФ-идея.
Есть такой (эвристический, "верятностный") тест на простоту " Рабина-Миллера (или Миллера-Рабина).
Похоже, что его можно модифицировать под указанную выше задачу.
Я сейчас не готов сказать, насколько это известно.
Но попробовать можно.
Только Вам придется для начала прочесть в инете про тест Рабина-Миллера.
Тогда и поговорить можно содержательно,  без обычных "не читал, но понимаю так..."

Михалыч
Гость


Вернуться к началу Перейти вниз

Re: М.Полянскому: об одной задаче факторизации

Сообщение автор Михаил Полянский в Пн Мар 07, 2011 11:45 pm

Да, Михалыч, я перечитал, возобновил в памяти. Смущает то, что там рыто-перерыто. И алгоритмы тяжеловесные. Чего только стоит ранг и выбор числа отсчёта по логарифму. Но, впрочем, пока не знаю, что у Вас. Если модификация всех этих наворотов к более продуктивному алгоритму или поиск двухсоставного через эти навороты - то всегда и очень интересно. Обещаю, что буду обдумывать до... Излагайте, пожалуйста.
avatar
Михаил Полянский
Admin

Сообщения : 3412
АКТИВНОСТЬ : 8968
РЕПУТАЦИЯ : 28
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

Re: М.Полянскому: об одной задаче факторизации

Сообщение автор Михалыч в Ср Мар 09, 2011 1:14 pm

Собственно, мысль достаточно банальна.
Тест Р-М отбраковки составных базируется на том,что при простом модуле сравнение x^2 = 1 имеет ровно два решения.
Если модуль - произведение ДВУХ простых нечетных, то такое сравнение имеет четыре решения.
Степень "подозрительности" на простоту в канонической версии теста Р-М увеличивается в четыре раза с каждым новым значением основания степени в тесте.
Осталось дать соответствующие "вероятностные" оценки для двухсоставных чисел.
Замечу, что это не подход к задаче разложения на множители, а подход к отфильтровке "более, чем двухсоставных".
Хотя возможны модификации для поиска трехсоставных и т.д.

Михалыч
Гость


Вернуться к началу Перейти вниз

Re: М.Полянскому: об одной задаче факторизации

Сообщение автор Михаил Полянский в Пн Мар 14, 2011 6:59 pm

А если "
оценки для двухсоставных чисел
дать из совершенно других соображений?
Повозившись с тестом Р-М - понял пока только (может позже осенит больше), что уж больно он программно тяжеловесен.
avatar
Михаил Полянский
Admin

Сообщения : 3412
АКТИВНОСТЬ : 8968
РЕПУТАЦИЯ : 28
Дата регистрации : 2009-09-16
Возраст : 56
Откуда : Москва

Вернуться к началу Перейти вниз

Re: М.Полянскому: об одной задаче факторизации

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу

- Похожие темы

 
Права доступа к этому форуму:
Вы можете отвечать на сообщения