2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.





Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 46  След.
 
 Поиск простых чисел
Сообщение28.08.2009, 14:05 
Аватара пользователя


07/07/09
346
Минск
Сами мы не местные (как было уже сказано)
Помогите, пожалуйста, разобраться в одном вопросе.

Вообщем у меня есть новый метод поиска простых чисел. Вернее я точно не знаю новый ли он, но по крайней мере нигде в интернете я не встречал подобного.
Суть его в слудующем:

Берется любое нечётное число n. (допустим это число 9) Возводиться в квадрат (81). Применяется формула и на выходе выходит ряд простых чисел 79, 73, 71, 67, 61, 59, 53

Вообщем так с любым числом мы можем получить на выходе простые числа лежащие до него.

Я попросил знакомого программиста оформить это в программе. Он сделал её в паскале. Вообщем проверил - все простые числа до 201 в квадрате находит без проблем, потом комп выдает ошибку ПРОЦЕССОР NTVDM обнаружил недопустимую инструкцию. CS: 0000 IP:0077 fo 37 05 0c 02 Сравнивал результаты с таблицей известных простых чисел.

Есть ли практическое применение этому методу? Знаю в криптографии работают с простыми числами.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:11 
Заслуженный участник


11/05/08
31333
SerjeyMinsk в сообщении #238656 писал(а):
Берется любое нечётное число n. (допустим это число 9) Возводиться в квадрат (81). Применяется формула

Какая формула-то?

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:20 
Аватара пользователя


07/07/09
346
Минск
ewert в сообщении #238659 писал(а):
SerjeyMinsk в сообщении #238656 писал(а):
Берется любое нечётное число n. (допустим это число 9) Возводиться в квадрат (81). Применяется формула

Какая формула-то?

Если возможно что-либо посоветовать без выкладки формулы - я буду очень благодарен. Пожалуйста, поймите мое положение.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:22 
Заслуженный участник
Аватара пользователя


13/08/08
13012
Криптография интересуется гораздо большими числами. Их не уложишь в обычный четырёх байтный формат (судя по характеру ошибки, именно на его основе была написана программа).
В этих числах обычно по нескольку десятков цифр. Поэтому Ваш алгоритм надо реализовать в виде программы, которая представляет натуральные числа в виде массива цифр (допустимо и двоичных), проверить его для больших чисел разной длины, определить скорость работы. Если Ваш алгоритм выдаёт хотя бы одно простое число из 100 десятичных цифр в секунду, то его с удовольствием купят банки, компьютерные компании или спецслужбы.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:24 
Заслуженный участник


11/05/08
31333
Ну Вы же спрашиваете, имеет ли метод практическое значение, а что за метод -- не говорите. И что тут можно ответить?...

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:27 
Заслуженный участник
Аватара пользователя


13/08/08
13012
С обнародованием формулы спешить не советую. Во-первых, Вы не можете её запатентовать, а потом никак не докажете, что именно Вы автор. Будет много интересующихся и желающих разделить не столько славу, сколько деньги. Славы вы не дождётесь, скорее всего. Авторы подобных открытий обычно законспирированы не хуже разработчиков оружия.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:27 
Заслуженный участник


08/04/08
8417
SergejMinsk писал(а):
79, 73, 71, 67, 61, 59, 53

Это все простые в промежутке от $7^2$ до $9^2$. Очень похоже на решето Эратосфена.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:28 
Аватара пользователя


07/07/09
346
Минск
gris в сообщении #238666 писал(а):
Криптография интересуется гораздо большими числами. Их не уложишь в обычный четырёх байтный формат (судя по характеру ошибки, именно на его основе была написана программа).
В этих числах обычно по нескольку десятков цифр. Поэтому Ваш алгоритм надо реализовать в виде программы, которая представляет натуральные числа в виде массива цифр (допустимо и двоичных), проверить его для больших чисел разной длины, определить скорость работы. Если Ваш алгоритм выдаёт хотя бы одно простое число из 100 десятичных цифр в секунду, то его с удовольствием купят банки, компьютерные компании или спецслужбы.

Огромное спасибо за подробный ответ.
Скажите, а существует ли возможность проверить скорость алгоритма с тем-же решетом Эратосфена до этих чисел хотябы. По милиоткликам процессора или как-нибудь еще?
Я могу попробовать сделать видео работы этой программы. Естественно, что сразу-же возникнет сомнение, что, а не вбил ли я просто все простые числа и выдаю результаты. Но смею заверить, что высчитывает числа именно по формуле. Клянусь.

-- Пт авг 28, 2009 14:30:11 --

Sonic86 в сообщении #238671 писал(а):
SergejMinsk писал(а):
79, 73, 71, 67, 61, 59, 53

Это все простые в промежутке от $7^2$ до $9^2$. Очень похоже на решето Эратосфена.

Уверяю, что не эратосфен. Там принцип другой.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:40 
Заслуженный участник
Аватара пользователя


13/08/08
13012
Понимаете, с помощью видео никого не убедишь. Да и, честно говоря, какое там решето Эратосфена для огромных чисел. Кроме этого никому не нужна абсолютная точность метода. Если он выдаёт простые числа с вероятностью хотя бы 23-27%, уже заинтересует кого нужно.
Однако, это всё вопросы более близкие к секретным, чем к математическим. Я слышал о печальной судьбе одного студента с кафедры теории чисел, который нашёл очень быстрый алгоритм разложения числа на множители. Во всяком случае, Вам лучше заручиться поддержкой крупной организации.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 14:49 
Аватара пользователя


07/07/09
346
Минск
gris в сообщении #238681 писал(а):
Во всяком случае, Вам лучше заручиться поддержкой крупной организации.

Да кто меня слушать будет. Я писал как-то пару писем в фирмы, занимающиеся криптографией. Послали куда подальше. Говорят, покажите, формулу, а там посмотрим. Эх, придется публиковать для всех и на всех возможных сайтах. Наметил себе время один месяц. Уже осталось две недели и потом в открытый доступ выкладываю все, что есть. Может потом кто поможет материально по доброй воли.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 16:05 
Заслуженный участник


27/06/08
3144
Волгоград
gris в сообщении #238666 писал(а):
Криптография интересуется гораздо большими числами. Их не уложишь в обычный четырёх байтный формат (судя по характеру ошибки, именно на его основе была написана программа).
В этих числах обычно по нескольку десятков цифр. Поэтому Ваш алгоритм надо реализовать в виде программы, которая представляет натуральные числа в виде массива цифр (допустимо и двоичных), проверить его для больших чисел разной длины, определить скорость работы. Если Ваш алгоритм выдаёт хотя бы одно простое число из 100 десятичных цифр в секунду, то его с удовольствием купят банки, компьютерные компании или спецслужбы.
Заблуждаетесь! Простые числа указанного Вами размера современные программы за одну секунду способны генерить миллионами. Иное дело разложение на множители. Но эти задачи (проверка на простоту и факторизация) даже близко рядом не лежали.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 22:52 
Заслуженный участник


31/12/05
1048
gris в сообщении #238681 писал(а):
Однако, это всё вопросы более близкие к секретным, чем к математическим. Я слышал о печальной судьбе одного студента с кафедры теории чисел, который нашёл очень быстрый алгоритм разложения числа на множители.
"Я видел секретные карты Генштаба. Там нет Америки!" (c) Даун Хаус

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 22:53 
Аватара пользователя


07/07/09
346
Минск
Подскажите, пожалуйста, как проверяют скорости работы алгоритмов. Как мне его проверить с тем-же решетом Эратосфена?

-- Пт авг 28, 2009 22:57:29 --

gris в сообщении #238681 писал(а):
Понимаете, с помощью видео никого не убедишь. Да и, честно говоря, какое там решето Эратосфена для огромных чисел. Кроме этого никому не нужна абсолютная точность метода. Если он выдаёт простые числа с вероятностью хотя бы 23-27%, уже заинтересует кого нужно.
.

Понимаете, метод абсолютно точный до тех чисел, которые смог посчитать мой компьютер или сама программа в паскале. Не вероятностный.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 23:13 
Заслуженный участник


11/05/08
31333
SerjeyMinsk в сообщении #238825 писал(а):
Подскажите, пожалуйста, как проверяют скорости работы алгоритмов.

Например. Если Вы загоните тот же алгоритм в Матлаб -- то там есть функция подсчёта флопиков (количества затраченных операций). Это более надёжно, чем засекать собственно время выполнения -- в многозадачных-то системах.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.08.2009, 23:15 
Заслуженный участник


04/05/09
4398
SerjeyMinsk в сообщении #238825 писал(а):
Подскажите, пожалуйста, как проверяют скорости работы алгоритмов.
Если вы не знакомы с понятием сложности алгоритма, то, например, часами.

-- Пт авг 28, 2009 16:21:18 --

ewert в сообщении #238832 писал(а):
Это более надёжно, чем засекать собственно время выполнения -- в многозадачных-то системах.
Даже в могозадачых системах часы - достаточно точный инструмент, если конечно система не загружена.
Количество же операций скорее даст гораздо большую ошибку, т.к. времена выполнения разных операций (и даже одинаковых операций в разных контекстах) могут различаться на порядок. К тому же детальный подсчёт операций занимает значительные ресурсы.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 682 ]  На страницу 1, 2, 3, 4, 5 ... 46  След.

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group