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

Автор темы Bat 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
22.03.2006 14:47
Тест на простоту. Прошу дать совет.
Добрый мой собеседник г-н maxal! Уважаемые господа математики!
Удивительно. но я нашел новый тест проверки чисел на простоту.
Этот тест абсолютно объективный, но при этом обладает малой "трудоемкостью", не превышающей "трудоемкость" известных быстрых вероятностных тестов.
Ранее, если у меня возникала идея того или иного теста, то всегда существовала потребность в виду множества сомнений обсудить его с кем-то на форумах (за что я благодарен моим vis-a-vis).
В данном случае, тест настолько понятен и объясним, что сомнений нет никаких, кроме одного: Посоветуйте, что можно предпринять дальше с этим "достижением"?
22.03.2006 20:08
выложить этот тест здесь
23.03.2006 06:53
Прежде всего сделать публикацию для защиты своего авторства
В arXiv.org e-Print archive или в русскоязычном подобии, если оно есть, и если Вы уверены, что вы не ошиблись ...
:)
23.03.2006 07:38
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
Авторство очень важно, если в новом тесте ошибка :)
Будет с кого спросить ))



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



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

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

Цитата

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

Цитата

Батороев писал(а) :
"если трудно доказать, что число делится на "что-то", то не легче ли определить, что оно само делит "что-то"?:)))
Я восхищён вашей выдумки ! И обязательно применю ваш принцип для чисел, названных в чью-то честь !
23.03.2006 14:25
Не думаю, что никуда...
Мы с Вами одной крови: "ты и я"! (Р. Кипплинг).
Нет такой работы, которая должна обязательно иметь итог. - Важно, что мы действуем!
Хотел бы обсудить с Вами другой вопрос. Можно? vbatorATmail.ru
23.03.2006 14:53
Понял...
Теперь Вы поймите, как реализовано быстрое возведение ОБЧ в степень другого ОБЧ по модулю третьего ОБЧ, почему не получается так же быстро считать факториалы, и каких размеров железобетонная стена стоит между Вашей правильной (хотя и тривиальной) идеей и её практическим применением.
23.03.2006 20:24
если уметь считать факториалы по модулю, то можно сломать 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
2-й вариант
а какой же сабж?
24.03.2006 08:05
??
Что такое сабж?
24.03.2006 11:05
А кто нас торопит?
Не спеша, за год-полтора, создадим Нуочень Большое Число k! и будем этим числом проверять все ОБЧ от k+1 до 3k...

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

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

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

Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

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