Поиск простых чисел

[SerjeyMinsk]

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

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

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

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

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

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

[ewert]

SerjeyMinsk в сообщении #238656 писал(а):

Берется любое нечётное число n. (допустим это число 9) Возводиться в квадрат (81). Применяется формула

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

[SerjeyMinsk]

ewert в сообщении #238659 писал(а):

SerjeyMinsk в сообщении #238656 писал(а):

Берется любое нечётное число n. (допустим это число 9) Возводиться в квадрат (81). Применяется формула

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

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

[gris]

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

[ewert]

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

[gris]

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

[Sonic86]

SergejMinsk писал(а):

79, 73, 71, 67, 61, 59, 53

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

[SerjeyMinsk]

gris в сообщении #238666 писал(а):

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

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

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

Sonic86 в сообщении #238671 писал(а):

SergejMinsk писал(а):

79, 73, 71, 67, 61, 59, 53

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

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

[gris]

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

[SerjeyMinsk]

gris в сообщении #238681 писал(а):

Во всяком случае, Вам лучше заручиться поддержкой крупной организации.

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

[VAL]

gris в сообщении #238666 писал(а):

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

Заблуждаетесь! Простые числа указанного Вами размера современные программы за одну секунду способны генерить миллионами. Иное дело разложение на множители. Но эти задачи (проверка на простоту и факторизация) даже близко рядом не лежали.

[tolstopuz]

gris в сообщении #238681 писал(а):

Однако, это всё вопросы более близкие к секретным, чем к математическим. Я слышал о печальной судьбе одного студента с кафедры теории чисел, который нашёл очень быстрый алгоритм разложения числа на множители.

"Я видел секретные карты Генштаба. Там нет Америки!" (c) Даун Хаус

[SerjeyMinsk]

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

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

gris в сообщении #238681 писал(а):

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

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

[ewert]

SerjeyMinsk в сообщении #238825 писал(а):

Подскажите, пожалуйста, как проверяют скорости работы алгоритмов.

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

[venco]

SerjeyMinsk в сообщении #238825 писал(а):

Подскажите, пожалуйста, как проверяют скорости работы алгоритмов.

Если вы не знакомы с понятием сложности алгоритма, то, например, часами.

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

ewert в сообщении #238832 писал(а):

Это более надёжно, чем засекать собственно время выполнения -- в многозадачных-то системах.

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