Методика определения делимости чисел

[Iosif1]

незваный гость писал(а):

:evil:
Решето Эратосфена? Медлено, но верно!

maxal писал(а):

Проверку на простоту можно осуществлять алгоритмом Миллера-Рабина, готовая реализация на Pascal есть тут (вопрос 2.3.3.1).

Эффективнее, но заметно сложнее!

А существует ли электронная версия Решета Эрастофена? Например, для таблиц Эксель. iosif1

[Someone]

Iosif1 писал(а):

А как вы определяете: ПРОСТОЕ ИЛИ НЕТ КОНКРЕТНОЕ ЧИСЛО, или можете посоветовать, где с таковыми опытами можно познакомиться? Какие алгоритмы доступны для ознакомления?

http://primes.utm.edu/prove/index.html

Добавлено спустя 11 минут 36 секунд:

Re: Загадки математики

Iosif1 писал(а):

А существует ли электронная версия Решета Эрастофена? Например, для таблиц Эксель. iosif1

Про версию для электронных таблиц не слышал. Реализации решета Эратосфена можно посмотреть здесь: http://primes.utm.edu/links/programs/sieves/Eratosthenes/index.html.

[Iosif1]

Someone писал(а):

Iosif1 писал(а):

А как вы определяете: ПРОСТОЕ ИЛИ НЕТ КОНКРЕТНОЕ ЧИСЛО, или можете посоветовать, где с таковыми опытами можно познакомиться? Какие алгоритмы доступны для ознакомления?

http://primes.utm.edu/prove/index.html

Добавлено спустя 11 минут 36 секунд:

Re: Загадки математики

Iosif1 писал(а):

А существует ли электронная версия Решета Эрастофена? Например, для таблиц Эксель. iosif1

Про версию для электронных таблиц не слышал. Реализации решета Эратосфена можно посмотреть здесь: http://primes.utm.edu/links/programs/sieves/Eratosthenes/index.html.

А интересно , например, Вам было бы интересно иметь такую версию? Версию, позволяющую проверять простое или нет рассматриваемое число до 36 881 329. Для этого достаточно использовать простые числа, содержащиеся в таблице справочника М.М.Выгодского. Чуть, чуть больше. Ведь для того, чтобы проверить простое или нет рассматриваемое число необходимо и достаточно произвести деление этого числа на последовательность простых чисел в диапозоне от 1 до $L_max$, обеспечивающее неравенство:
${(L_max)^2}< L_p$
Например, таблицы простых чиселД.М.Лемера, издание 1967 г., содержат простые числа до 10 006 721. О других таблицах я не знаю. А если использовать в такой электронной версии все простые числа таблиц Лемера? Конечно этого вовсе недостаточно, чтобы бороться за выставленные премии за нахождение самого большого числа. Но для человеческого анализа, по моему мнению, вполне достаточно. Я правда не знаю, удастся ли в этом случае размещать простые числа в ячейках таблиц Эксель. И сколько будет компьютер считать. Думаю немного, несколько секунд.Но все равно, какие хорошие таблицы Эксель. Какие умные!
Iosif1

[ИСН]

Ну, это не имеет большого практического смысла (у профессионалов есть более умные и специально заточенные инструменты), но любителю, чтобы поиграться, можно применять эксель, скажем, так:
В столбец A, начиная с первой ячейки и далее вниз, загоняем простые числа, сколько влезет.
B ячейку B1 пишем что-то вроде

=IF(C$1/A1=INT(C$1/A1),1,0)

и размножаем эту формулу вниз опять же до упора.
В какую-нибудь ячейку (положим, C2) пишем сумму столбца B.
В ячейку C3 пишем

=IF(C2=0,"prime","composite")

Теперь в ячейку C1 загоняем любое (в разумных пределах) число и мгновенно узнаём, простое оно или нет.

[Iosif1]

ИСН писал(а):

Ну, это не имеет большого практического смысла (у профессионалов есть более умные и специально заточенные инструменты), но любителю, чтобы поиграться, можно применять эксель, скажем, так:
В столбец A, начиная с первой ячейки и далее вниз, загоняем простые числа, сколько влезет.
B ячейку B1 пишем что-то вроде

=IF(C$1/A1=INT(C$1/A1),1,0)

и размножаем эту формулу вниз опять же до упора.
В какую-нибудь ячейку (положим, C2) пишем сумму столбца B.
В ячейку C3 пишем

=IF(C2=0,"prime","composite")

Теперь в ячейку C1 загоняем любое (в разумных пределах) число и мгновенно узнаём, простое оно или нет.

Ну спасибо. Обязательно попробую. Не отходите на очень долго, я сейчас убегаю, но хочу с Вами посекретничить, если согласитесь. Iosif1

[Iosif1]

Iosif1 писал(а):

ИСН писал(а):

Ну, это не имеет большого практического смысла (у профессионалов есть более умные и специально заточенные инструменты), но любителю, чтобы поиграться, можно применять эксель, скажем, так:
В столбец A, начиная с первой ячейки и далее вниз, загоняем простые числа, сколько влезет.
B ячейку B1 пишем что-то вроде

=IF(C$1/A1=INT(C$1/A1),1,0)

и размножаем эту формулу вниз опять же до упора.
В какую-нибудь ячейку (положим, C2) пишем сумму столбца B.
В ячейку C3 пишем

=IF(C2=0,"prime","composite")

Теперь в ячейку C1 загоняем любое (в разумных пределах) число и мгновенно узнаём, простое оно или нет.

Ну спасибо. Обязательно попробую. Не отходите на очень долго, я сейчас убегаю, но хочу с Вами посекретничить, если согласитесь. Iosif1

Я согласен, что для профессионалов это не интересно. Я считаю, что многие могут настроить Эксель под эту задачу. Может быть это интересно кому-нибудь, кто не хочет возиться, считая это сопутствующей задачей. Меня, в данном случае интересуют именно профессионалы, которые могут создавать программы, которыми уже не балуются. На основании представления чисел натурального числового ряда в системах координат по модулю 6 и 4 нам удалось разработать алгоритм, позволяющий отличать простые числа от составных. Алгоритм опубликован самостоятельно как "Методика определения делимости чисел натурального числового ряда и ее практическое применение" более полутора лет назад и разослан в библиотеки некоторых математических институтов, в том числе и в институт им Стеклова. Но ни о какой реакции авторам до сих пор неизвесно. Програмирование по отдельным частям разработанной методики авторам оказалось посидьно. (16 групп, при максимальном использовании из них для расчета 4) Сделать же программу универсальной - уже не под силу. Программу, которая бы осуществляла разводку чисел по единому алгоритму расчета, желательно, с единым первичным заданием произвольного числа, позволяющую автоматически увеличивать число после завершения цикла расчетов. В разработанной Методике объем расчетов практически не зависит от величины числа, так как оно используется только при делении для определения сопоставляемых числовых рядов. И мой вопрос: А это может представлять практическую ценность. iosif1

[zw0rk]

Не понятно, как это

Цитата:

объем расчетов практически не зависит от величины числ

когда тут же

Цитата:

так как оно используется только при делении

Деления ресурсоёмкая операция. А какие есть оценки скорости алгоритма?

[Someone]

Iosif1 писал(а):

Алгоритм опубликован самостоятельно как "Методика определения делимости чисел натурального числового ряда и ее практическое применение" более полутора лет назад и разослан в библиотеки некоторых математических институтов, в том числе и в институт им Стеклова.

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

[Iosif1]

zw0rk писал(а):

Не понятно, как это

Цитата:

объем расчетов практически не зависит от величины числ

когда тут же

Цитата:

так как оно используется только при делении

Деления ресурсоёмкая операция. А какие есть оценки скорости алгоритма?

Оценки скорости алгоритма нет никакой. Оценка логическая. Очень простая: задавая новое рассматриваемое число, мы "старое" увеличиваем на $L$, прибавляемая величина всегда одна и та же, и делитель всегда один и тот же, то-есть, при анализе нового числа, частное увеличивается на известную величину. Мы как бы из всего множества чисел рассматриваем конкретный ряд, конкретное семейство чисел. Семейство чисел с одинаковыми коэффициентами перевода координат числа одной систеиы координат, в координаты, соответствующие другой системе координат. Ответ становится возможен потому, что простые числа с целочисленными координатами, расчитанными для одной системы координат не переводятся в целочисленные применительно к другой системе координат. При появлении такого числа в рассматриваемом семействе чисел ответ становится очевиден. Полная формализация алгоритма не сделана, не хватило силенок. Поэтому и требуется поддержка. Я универсально не подготовлен. Долотом и топором, так как и в "Доказательстве БТФ", с которым можно еще ознакомиться на форуме. Iosif1

[zw0rk]

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

[Iosif1]

AVARY писал(а):

Цитата:

...то многие криптографы проспят следующую ночь спокойным младенческим сном , и будут так спать и дальше (пока не построят реально работающий квантовый компьютер)

Квантовый компьютер не решит проблему, по крайней мере факторизации, так как вместе с ним придут намного более длинные ключи. Использование высокой производительности это эволюционный путь. Необходимо найти революционный.

Уважаемый AVARY.
Я абсолютно с Вами согласен. Но такой формулировкой я, как бы, даю понять, что найденный алгоритм и есть революционный. Но это, по меньшей мере не скромно. Мне было бы, конечно, приятно, если бы это мне сказали, например. Вы. Я берусь утверждать, что, наконец удалось определять отличительные признаки простых чисел. Оказалось, что все числа могут быть представлены в конкретной системе координат. Что, конечно, не новость. Таких систем не мало. По аналогии с давно известным вариантом (при использовании модуля 2). Аналогичное распределение оказалось возможно и при использовании модулей 6 и 4. (координаты чисел также находятся на основании квадратных уравнений). В зависимости от вида квадратного уравнения, корнями которого являются координаты рассматриваемого числа натуральный ряд чисел может быть разделен на "семейства". И это, как по модулю 6, так и по модулю 4. При этом оказалось, что между координатами используемых систем координат. для каждого семейства чисел, есть строго детерминированные алгоритмы перевода. Для составных чисел при переводе координат из одной системы координат в другую систему координат обязательно есть набор алгоритмов, обеспечивающий целочисленность результатов. для простых чисел ни один из приемливых наборов этого не обеспечивает. всего получилось 16 расчетных вариантов. При рассмотрении конкретного числа максимальное использование расчетных вариантов - четыре. Для каждого из вариантов на основании использования таблиц Эксель составлены программы расчета, а на объединение этих вариантов в единое целое не хватило сил и знаний. Если бы хватило, мы бы занились расчетом чисел, обеспечивающих премиальные, и не только потому, что мы корыстные, но и потому, что это было бы самым действенным подтверждением работоспособности алгоритма. Iosif1

[AVARY]

Уважаемый Iosif1:
Для меня, факторизация - настолько деликатная тема, что я порой не понимаю для чего люди заявляют о том, что нашли некий сверхбыстрый алгоритм факторизации, вместо того, чтобы просто напрасто выложить множители RSA704, RSA768 и т.д. по известному всем нам адресу...

По накопленному мной опыту, могу вас заверить, что большинство найденных "закономерностей" при работе с простыми числами от 2 до 101 терпят фиаско при работе с большими простыми. Поэтому не парите в эйфории предвкушения, а найдите время довести свою теорию до точки и получите всемирную известность, богатство и бессмертие или же возможность разработать новый алгоритм!

P.S. Я буду искренне рад успеху того человека, который сумеет сорвать 30-летний юбилей RSA.

[Iosif1]

AVARY писал(а):

Уважаемый Iosif1:
Для меня, факторизация - настолько деликатная тема, что я порой не понимаю для чего люди заявляют о том, что нашли некий сверхбыстрый алгоритм факторизации, вместо того, чтобы просто напрасто выложить множители RSA704, RSA768 и т.д. по известному всем нам адресу...

По накопленному мной опыту, могу вас заверить, что большинство найденных "закономерностей" при работе с простыми числами от 2 до 101 терпят фиаско при работе с большими простыми. Поэтому не парите в эйфории предвкушения, а найдите время довести свою теорию до точки и получите всемирную известность, богатство и бессмертие или же возможность разработать новый алгоритм!

P.S. Я буду искренне рад успеху того человека, который сумеет сорвать 30-летний юбилей RSA.

Чтобы выложить множители, мне нужна поддержка профи. Мой Pentium II и я - неубедительный дуэт для этого исполнения. Я ищу такую возможность, уверяю Вас. Я уже писал, что работа разослана в библиотеки математических институтов. Ну и что? Никаких контактов. Мне кажется, что профи смогут разобраться и самостоятельно. Но тут ничего не поделаешь. Если есть советы, с удовольствием выслушаю. iosif1

[Iosif1]

Macavity писал(а):

Someone писал(а):

EsenZhar писал(а):

В последнее время ходит много слухов о разработке алгоритма быстрой факторизации числа.
Значит ли это, что система RSA рухнула? В мои руки попал алгоритм факторизации с "логарифмическим законом затрат времени". Какие ещё есть законы затрат времени кроме полиномиальных?

Чего там слухами питаться? Берите числа с http://www.rsasecurity.com/rsalabs/node.asp?id=2093, факторизуйте и получайте премии, раз Вам такой супер-алгоритм достался.

Ну вот! А ещё говорят, что теория чисел не имеет практического применения.

Очень информативно отвечаете, приятно. Нельзя ли узнать у Вас трудоемкость перевода из 256 счисления, используемого в рассчетах факторизации чисел в 6-ти ричное счисление. При этом не всего числа, а только первого разряда этого числа. Перевод числа из 256 ричного счисления в 4-ричное счисление с этой же целью, понятно, проблемы не составляет. iosif1

[Someone]

Iosif1 писал(а):

Нельзя ли узнать у Вас трудоемкость перевода из 256 счисления, используемого в рассчетах факторизации чисел в 6-ти ричное счисление. При этом не всего числа, а только первого разряда этого числа. Перевод числа из 256 ричного счисления в 4-ричное счисление с этой же целью, понятно, проблемы не составляет. iosif1

У меня была гипотеза, что "6-ти ричное счисление" - это то, что стандартно называется шестиричной системой счисления, но этому мешает следующее Ваше утверждение:

Iosif1 писал(а):

http://dxdy.ru/viewtopic.php?p=43023#43023
При этом, для составных чисел, при переводе координат из одного счисления в другое счисление все переведенные координаты остаются целочисленными. А вот для простых чисел аналогичное действие не приводит к такому результату.

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

О системах счисления есть крохотная брошюрка: С.В.Фомин. Системы счисления. "Наука", Москва, 1980.

Там есть и алгоритм перевода из одной системы счисления в другую. В Интернете она есть на http://ilib.mccme.ru/plm/ann/a40.htm. Можно посмотреть и Википедию.