Тест на простоту. Прошу дать совет.

Автор темы Bat 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеСтуденческий конкурс в области программирования AR Start16.04.2012 10:07
ОбъявлениеЗаседание Московского математического общества 24 апреля 2012 года23.04.2012 01:32
Форумы Список тем Новая тема
22.03.2006 14:47
Bat
Тест на простоту. Прошу дать совет.
Добрый мой собеседник г-н maxal! Уважаемые господа математики!
Удивительно. но я нашел новый тест проверки чисел на простоту.
Этот тест абсолютно объективный, но при этом обладает малой "трудоемкостью", не превышающей "трудоемкость" известных быстрых вероятностных тестов.
Ранее, если у меня возникала идея того или иного теста, то всегда существовала потребность в виду множества сомнений обсудить его с кем-то на форумах (за что я благодарен моим vis-a-vis).
В данном случае, тест настолько понятен и объясним, что сомнений нет никаких, кроме одного: Посоветуйте, что можно предпринять дальше с этим "достижением"?
Ответить Цитировать
22.03.2006 20:08
echooff (Echo-off)
выложить этот тест здесь
сабж
Ответить Цитировать
23.03.2006 06:53
Researcher
Прежде всего сделать публикацию для защиты своего авторства
В arXiv.org e-Print archive или в русскоязычном подобии, если оно есть, и если Вы уверены, что вы не ошиблись ...
:)
Ответить Цитировать
23.03.2006 07:38
Bat
1-й вариант
Спасибо за добрый совет!
Вообще-то, за ночь я пришел к такому же выводу.
Итак, 1-й вариант теста:
Свидетель простоты нечетных чисел m: k! =/= 0 mod m, где k - натуральное число m/3<=k<m.
Враианты алгоритма: Либо, для конкретного числа m рассчитываем к! и производим проверку, либо по подготовленному заранее к! проверяем любое число m в интервале от к+1 до 3к.
Если к! = 0 mod m, то число m относим к составным, если не равно 0, то m - простое.

Ответить Цитировать
23.03.2006 08:52
Researcher
Авторство очень важно, если в новом тесте ошибка :)
Будет с кого спросить ))



С уважением,
Борис
Ответить Цитировать
23.03.2006 11:26
Bat
к "спросу" готов
Потрясающий стиль Ваших сообщений впечатляет!
Я битых три часа ломал голову над ребусом...:
"То ли Вы определили возможную ошибку в тесте, то ли неоднократно "обжигались", не "застолбив" авторство, то ли с Вас не раз "спрашивали"?:))
Ответить Цитировать
23.03.2006 12:20
chingiz (ИСН)
Не понял...
У нас что, есть быстрый способ вычисления факториалов Очень Больших Чисел?
И откуда, ради Аллаха, взялось m/3? По Вашему тесту в такой форме число 14 - простое. А что, берём k=6. Так, 6!=720, верно? 720 mod 14...
Ответить Цитировать
23.03.2006 12:26
Researcher
Огромное спасибо, что не обижаетесь !
Успехов во всех начинаниях !



С уважением,
Борис
Ответить Цитировать
23.03.2006 12:41
Bat
Это Вам спасибо!
Если бы ты знал то, что знаю я, ты бы не мог знать того, что ты знаешь // Поль Валери

Уважаемый Борис .... ич!
Разгадав все же Ваш "ребус", нахожусь в полном восхищенном состоянии по поводу абстрактности Вашего (и П. Валери) мышления!
Вы, наверное, правы, что подобный тест мог скорее предложить любитель математики, к которым я отношусь, т.к. он (тест) не вписывается в рамки классических направлений поиска.
Здесь я пошел "вместе с Магометом… к горе" - "если трудно доказать, что число делится на "что-то", то не легче ли определить, что оно само делит "что-то"?:)))
Ответить Цитировать
23.03.2006 13:21
Bat
Разъяснение
Тесты на простоту четных чисел не разрабатываются.
Вместе с тем, приму к сведению Ваше замечание и поправлю свое сообщение.
По поводу Очень Больших Чисел:
Тесты Миллера-Рабина, Лемана (которые широко практикуются) оперируют, зачастую, куда большими величинами. Например, если в процессе проверки по тесту Лемана или по тесту Миллера-Рабина (если (m-1)/2 - нечетное число) выпало случайное число (m-1), то необходимо рассчитать (m-1)^[(m-1)/2], что значительно больше, чем (m/3)! Если для ОБЧ разработаны специальные программы возведения в степень, то, надеюсь, программисты справятся и с проблемами вычисления факториалов (или лучше вычисления произведения только нечетных чисел)
Кроме того, у меня "в запасе" имеется 2-й вариант теста, который призван "снизить нагрузку" на вычислительное устройство.
Ответить Цитировать
23.03.2006 13:52
Researcher
Я тоже много лет путешествую в натуральном ряде чисел ! Но он никуда не ведёт !
Я это знаю и всё равно испытываю от своего путешествия Радость !
:)

Цитата

Батороев писал(а) :
Вы, наверное, правы, что подобный тест мог скорее предложить любитель математики, к которым я отношусь
Дорогой Батороев ! Я о вашем тесте вообще ничего не говорил ! Я рад вашей исследовательской натуре ! Сам такой :)

Цитата

Батороев писал(а) :
"если трудно доказать, что число делится на "что-то", то не легче ли определить, что оно само делит "что-то"?:)))
Я восхищён вашей выдумки ! И обязательно применю ваш принцип для чисел, названных в чью-то честь !
Ответить Цитировать
23.03.2006 14:25
Bat
Не думаю, что никуда...
Мы с Вами одной крови: "ты и я"! (Р. Кипплинг).
Нет такой работы, которая должна обязательно иметь итог. - Важно, что мы действуем!
Хотел бы обсудить с Вами другой вопрос. Можно? vbatorATmail.ru
Ответить Цитировать
23.03.2006 14:53
chingiz (ИСН)
Понял...
Теперь Вы поймите, как реализовано быстрое возведение ОБЧ в степень другого ОБЧ по модулю третьего ОБЧ, почему не получается так же быстро считать факториалы, и каких размеров железобетонная стена стоит между Вашей правильной (хотя и тривиальной) идеей и её практическим применением.
Ответить Цитировать
23.03.2006 20:24
maxal
если уметь считать факториалы по модулю, то можно сломать RSA
Пусть n=p*q, где p и q - неизвестные простые, для определенности p<q.
Вычислим m = [sqrt(n)]! mod n и затем НОД(m,n). Нетрудно видеть, что m делится на p, но не на q, и поэтому НОД(m,n)=p. Таким образом RSA сломан.

Проблема здесь только в том как вычислить m. Если Вы умеете это делать, бегите на сайт RSA Security, ломайте там все оставшиеся шифровки и получайте от $30000 до $200000 за каждую.

Ответить Цитировать
23.03.2006 20:48
echooff (Echo-off)
2-й вариант
а какой же сабж?
Ответить Цитировать
24.03.2006 08:05
Bat
??
Что такое сабж?
Ответить Цитировать
24.03.2006 11:05
Bat
А кто нас торопит?
Не спеша, за год-полтора, создадим Нуочень Большое Число k! и будем этим числом проверять все ОБЧ от k+1 до 3k...

"как реализовано быстрое возведение ОБЧ в степень другого ОБЧ по модулю третьего ОБЧ"

Интересно! Покажите, пожалуйста, на примере ОМЧ (в пределах 1000).

Ответить Цитировать
24.03.2006 11:06
Bat
Поясните
В этой задаче имеется хоть одно известное?
Ответить Цитировать
24.03.2006 11:18
maxal
n известно
n известно. Еще известно, что оно равняется произведению ровно двух простых чисел p и q, которые нам неизвестны. Задача состоит в том, чтобы по заданному n определить p и q.
Ответить Цитировать
24.03.2006 12:54
Bat
Подумаю.
Относительно вычислений m по модулю... Разве нельзя считать факториал обычным способом, но ступенчато, т.е. в нужный момент (когда "зашкаливает") находить modn и умножать полученный остаток дальше на следующие множители?

Ответить Цитировать
Страницы: 12
« Следующая тема   Предыдущая тема »
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти