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

[Iosif1]

Iosif1 писал(а):

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

При размещении чисел в системе координат, составленной по шестиричной системе счисления (1), или четырех ричной (2), (по аналогии с известной системой координат, составленной на основании двоичной системы счисления) координаты числа - это корни квадратного уравнения, и они не всегда целочисленные.
Если разделить числа натурального числового ряда на легкораспознаваемые, или труднораспознаваемые (по признаку делимости), то все труднораспознаваемые числа и в (1), и во (2) системах координат находятся в корреляционной зависимости. При этом для нахождения координат составных чисел и по 1 - му, и по 2 - му вариантам, получаемые координаты целочисленные. А у простых чисел - нет. Если использовать для нахождения возможных целочисленных координат одно из уравнений, приходится делать это с неопределенным количеством просчетов. (По аналогии с ситемой координат, составленной на основании двоичного счисления). В чем мало толку. А вот использование этих способов в комбинации оказалось эффективно! Удается определять количество просчетов, необходимое для "поподания" в контрольный просчет. Иными словами, определять: существует он или нет. Если он не существует - необходимое количество просчетов, которое необходимо совершить , чтобы попасть в контрольный получаем не целочисленным. На этом строиться алгоритм определения простое или нет рассматриваемое число. Я уже писал где-то, что расчетных вариантов в алгоритме 16-ть. Для каждого из них составлена программа, а вот объединение их в единый алгоритм оказывается не по силам. А без этого, все равно остается много трудоемких расчетов. Поэтому я и обратился к Вам с вопросом об определении первого разряда числа, представленного в шестиричном счислении. И именно для тех чисел, которые представлены в 256 счислении, ведь именно их целесообразно представить в виде сомножителей.
приношу извинения, если используемые мной формулеровки, режут слух. В изданной работе я, например, я употребляю следующий заголовок:
ВСПОМОГАТЕЛЬНЫЕ ЧИСЛОВЫЕ РЯДЫ, СОСТАВЛЕННЫЕ НА ОСНОВАНИИ ИСПОЛЬЗОВАНИЯ МОДУЛЕЙ 6 И 4.
Терминология -дело не простое, в крайнем случае, для меня. Хорошего корректора найти не удалось. Iosif1

[Iosif1]

Someone писал(а):

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

Уважаемый Someone. Счисления не секретные, а самые обыкновенные. Я знаком с переводом чисел из десятичного счисления в другие. Число, в каком бы счисление оно не было выражено, свое значение не изменяет. Переведем мы его в другое счисление или нет. Думаю, что Вы с этим согласны. Разработанная же "Методика делимости чисел..." основана на использовании систем координат, составленных на основании $mod 6$и $mod 4$. По аналогии с использованием системы координат, составленной по $mod 2$. Я поищу ссылку. кажется она была издана на казахском языке. Там подробно описан метод представления нечетных чисел натурального числового ряда в формализованном виде. Это позволяет определять простое или нет рассматриваемое число посредством решения квадратного уравнения вида:${x^2}+{(B+bk)}x +C+{ck} = 0$ (1)
Определение простое или нет рассматриваемое число становится возможно посредством решения квадратного уравнения 1 методом перебора коэффициента $k$ с шагом, равным 2. При этом, если целочисленное значение корней квадратного уравнения при каком то просчете имеет место, рассматриваемое число принадлежит данной таблицы, а значит оно составное. Я считаю это широко известным. Мы же по аналогии с описанным методом, использовали системы координат, составленные по $mod 6$и $mod4$. Оставляю мой предыдущий ответ, как поясняющий сказанное сейчас. Если найдете источник, на который я ссылаюсь, пожалуйста сообщите. Понимаю, что используемая терминология режет слух. Но мне не удалось найти аналогов для использования более привычных формулировок. И, как нам кажется, данная методика позволяет использовать в изложении категорию: системы координат. Последнее же слово, конечно, не за нами. Iosif1

[PAV]

PAV:

Сообщения собраны из тем "Загадки математики" и "Быстрая факторизация"

[AndreyS]

Я не очень понял из вышеприведенных постов насчет нового теста простоты числа и
факторизации. Ведь это далеко не одно и тоже. Ведь для того, чтобы проверить составное
число или нет в размерах чисел порядка призовых RSA достаточно и имеющихся
алгоритмов, причем очень шустрых (я в Математике все числа RSA на простоту
проверяю практически мгновенно (точно не помню, но не более 10 минут вроде)).
Они, конечно вероятностные тесты, но возможность их ошибки стремится к нулю.
А факторизация это уже совсем другая проблема.
Так что же предлагается? Новый тест на простоту или факторизация? - что
то из текста постов не совсем понятно.

[Iosif1]

AndreyS писал(а):

Так что же предлагается? Новый тест на простоту или факторизация? - что
то из текста постов не совсем понятно.

Я посчитал, что факторизация это представление числа в виде произведения сомножителей, и верно опростоволосился? Словари, которыми я владею, эту категорию не разъяснили. Верно, факторизация это( для первого числа в списке призовых RSA): $9+5*256^1+0*256^2+7*256^3...$. Нет, нет предлагается новый невероятностный тест на простоту. Если Вы владеете такими возможностями, а значит и опытом, мне кажется Вам не представит труда оживить этот тест. Сделать объединение мини программ, состаленных посредством таблиц Эксель, в единое целое, позволяющее осуществлять разводку числа, его предварительный анализ, по вариантам, посредством деления числа на 6 и 4. Меня интересует в этом плане все возможности, и все подводные камни. Someome писал, что деление очень трудоемкая операция. Мне представляется, что разделить число на 6 не такая уж проблема, ведь число можно заводить в компьютер по частям. Но, это может быть расссуждение дилетанта? Жаль, что мечта о факторизации рухнула!iosif1

[AndreyS]

Что то Вы меня запутали. Факторизация - это в том числе и разложение на целые множители
в смысле нахождения целых сомножителей числа. В других разделах математики, а особенно
физики, под факторизацией могут часто понимать и другое - типа сохранения разделения
(и само такое разделение) параметров на подгруппы с характерными структурными представлениями
относительно группы определенных преобразований .
Относительно факторизации чисел RSA.
Одно дело знать, что число в принципе разлагается на множители, а другое дело
получить конкретные значения этих множителей. Насчет теста. Я так понял была замечена
некая закономерность для определенного множества чисел, но доказательств справедливости
закономерности нет. Тогда откуда уверенность, что это тоже не некий вероятностный тест.
Раньше тоже думали, что один известный тест точный пока числа Краймайкла не нашли.
Как кто то правильно заметил, есть много таких закономерностей для небольших чисел
(по причине неких вырождений), но они все рушатся при очень больших числах. Либо ваш алгоритм
факторизации скорей всего будет иметь численную сложность больше известных алгоритмов при
таких больших числах.
Насчет реализации - опыт программирования конечно есть, но вот времени совсем нет - даже
на свои тесты (идеи тоже имеются, но я к ним более скептически отношусь).

[Someone]

Iosif1 писал(а):

Я посчитал, что факторизация это представление числа в виде произведения сомножителей

Да, факторизация чисел - это именно представление их в виде произведения натуральных чисел, отличных от единицы.

Iosif1 писал(а):

Someome писал, что деление очень трудоемкая операция.

Это не я писал.

Iosif1 писал(а):

Мне представляется, что разделить число на 6 не такая уж проблема, ведь число можно заводить в компьютер по частям.

Деление "длинного" числа на число, помещающееся в регистре процессора, выполняется достаточно быстро. И лучше иметь делимое в компьютерной памяти целиком, а не по частям.

Но я Вас просил описать алгоритм проверки на простоту, и что такое счисление в Вашем смысле. А Вы как-то уклонились. Если, конечно, Вы считаете публикацию этого нежелательной, то вопрос снимается.

[Iosif1]

AndreyS писал(а):

Что то Вы меня запутали. Факторизация - это в том числе и разложение на целые множители

Т ак за что конкретно обещено вознаграждение RSA, что необходимо сделать в данном конкретном случае. А то я тоже из вашего описания ничего не понял. Какая факторизация требуется? И каким образом необходимо публиковать результат, и где. И какие гарантии. Когда на что-то надеешься, а потом шишь - очень много отрицательных эмоций, что очень вредно. Понял я, что вы человек занятый. Это , по моему хорошо. Насчет скептического отношения - это тоже хорошо. Если выкроите время, посмотрите тему:"Доказательство БТФ..." на этом же форуме. А то никто по настоящему не реагирует. Даже не знаю, хорошо это или плохо. У автора всегда уверенность, поэтому то и нухны оппоненты. А насчет алгоритма у меня уверенность еще большая, чем по БТФ. У меня 16 расчетных страничек для различных классов чисел, размещенных в системах координат, и все они опробированы. Конечно, хотелось бы большего объема опробации. Понимаю, что самой лучшей может быть опробация путем нахождения нового простого числа еще неизвестной величины, или факторизация, предлагаемая RSA. Но на это ни сил, ни знаний не хватает. Получил ответ от Someone, очень этому рад. Сейчас буду писать ответ ему, может быть там и Вам что-то будет интересно интересно. (См. далее) Iosif1

Добавлено спустя 58 минут 52 секунды:

Someone писал(а):

Но я Вас просил описать алгоритм проверки на простоту, и что такое счисление в Вашем смысле. А Вы как-то уклонились. Если, конечно, Вы считаете публикацию этого нежелательной, то вопрос снимается.

Простите, это zwOrk писал, что деление ресурсоемкая операция (здесь же ранее). А на второй странице, здесь же, мой ответ Вам. А чуть ранее тоже об алгоритме. Но Вы куда-то пропали. Я решил, что Вам стало не интересно. Переслать материал даже частями, я не умею. Много табличного материала. Я стараюсь научиться, но пока безрезультатно. Ищу ссылку на источник, которым я пользовался. Не понимаю, почему такой хороший аппарат: Определение простое или нет рассматриваемое число нигде не фигурирует. Попробую начать об алгоритме. Может ответами на Ваши вопросы кое-что удастся разъяснить. В первоисточнике все нечетные числа размещены в системе координат, составленной по $mod 2$. Это позволяет посредством составления и решения квадратного уравнения вида: ${x^2}+{(B+bk)x}+C +{ck}=0$ посредством перебора коэффициента $k$, равного 1,2,3,4,5.... проверять данное уравнение на возможность получения целочисленных корней. Если такое условие выполнимо, рассматриваемое число принадлежит таблице и оно составное. Если нет - нет, а значит число простое. Но считать замотаешься. Нами же используются системы координат, составленные по мод 6 и мод 4. Обособленное их использование - тоже безталковое. Ну увеличили интервал просчета с 2 до 6, подумаешь. Но в комбинации использование этих систем координат оказалось очень эффективно. Число представленное и в первой и во второй системах координат должно иметь при разрешаемости квадратных уравнений целочисленные корни и по первому, и по второму вариантам. Начиная поисковую эпопею мы получаем возможность определять будут ли априори целочисленные решения. Это обеспечивается тем, что существует строгая корелляция между корнями уравнения (координатами чисел) как по первому, так и по второму вариантам координатных систем для каждой из 16 групп( семейств) чисел. Максимальное количество используемых расчетных страниц при анализе конкретного числа - 4. Но без компьютера с его прекрасными таблицами Эксель все равно замотаешься. Где нибудь, да ошибешься. Поэтому то и нужна программа. Как уже отмечалось, расчетные страницы опробированы, но путь до цели в одиночку все равно: О-го- го. Жду вопросов. У меня к Вам просьба: загляните на "Доказательство БТФ" на этом же форуме. Очень хочется услышать Ваше мнение. Iosif1

[Someone]

Посмотрите, поиском и проверкой каких чисел на простоту занимаются тут: http://primes.utm.edu/primes/status.php. Сколько времени требуется Вам для проверки простоты, например, числа $5070649\cdot 2^{777777}-1$, имеющего $234141$ цифру в десятичной записи? Вот здесь (http://primes.utm.edu/primes/page.php?id=78994) можно прочесть, что программа llr.pl на процессоре P4 затратила на проверку 3011 секунд.

Я всё равно не понял, что такое эти Ваши "счисления", и как определить "координаты" числа в этих "счислениях". Что касается темы "Доказательство БТФ", то отсутствие обсуждения объясняется полной непонятностью Вашего текста.

[PAV]

Для получения приза RSA нужно разложить предлагаемое число на простые сомножители.

Можете хоть как-то пояснить, каким образом зависит количество производимых действий от порядка числа? Допустим, под "действием" будем понимать проверку на решение одного квадратного уравнения. Приведите примеры, сколько проверок потребовалось для тех чисел, для которых были проведены расчеты. Как увеличится это количество, если проверяемое число увеличить, к примеру, в два раза?

[AndreyS]

Iosif1
Насчет того, что нужно сделать, чтобы получить приз от RSA могу добавить следующее к тому
что сказал PAV.
В принципе все написано на их сайте, но раз уж вопросы остались, то вот инфа.

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

Из опыта изучения этого вопроса знаю, что сомножителя всега два (это требует
алгоритм шифровки RSA) и это естественно простые числа. Кроме этого одно из этих
простых чисел как правило превосходит другое не более чем в 20 раз, но не менее
чем в два раза. Это чтобы сделать неэффективными алгоритмы факторизации при практически
равных сомножителях, но и не сделать один сомножитель много меньше другого.

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

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

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


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

Вот например вижу : "K равного 1,2,3,4,5 ... " А сколько этих "к", где верхняя граница?
Если это большое число, то в этом смысла нет и таких уже известных алгоритмов
на основе модификаций Диофантовых уравнений навалом, но практически они малоинтересны.
Я и сам в свое время изучая этот вопрос наплодил кучу таких, только это не идет
ни в какое сравнение с самым мощным на сегодняшний день алгоритмом.

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

Сгенерировать большие простые числа для эксперимента вы сможите в пакете Математика.

Ну и в заключении практический совет.
Если хотите спрограммировать что то серьезное и достаточно быстрое, то откажитесь
от Exel. Изучите хоть один язык программирования и заведите таблицы туда.
Ну если не язык программирования, то хотябы математическую среду - советую
пакет Математика, так как там по теории чисел много функций и реализована
быстрая арифметика больших чисел. В частности Вы там можете просто умножить большие числа
обычным способом и сразу проверить свой вариант вне сайта RSA
В общем начните с пакета Математика - там не нужно делать много лишнего как
в языке программирования, так как дружественный и легкий математический интерфейс,
и при этом быстрота работы сравнима с кодом на языке программирования. Этого
достаточно для проверки состоятельности алгоритма на достаточно больших числах.
А уж когда будет ясно, что идея правильная, то можно уже думать и об оптимизации
алгоритма.

В частности, он мне быстро обломал не одну "замечательную" (как в начале казалось) идею

[Iosif1]

PAV писал(а):

Приведите примеры, сколько проверок потребовалось для тех чисел, для которых были проведены расчеты. Как увеличится это количество, если проверяемое число увеличить, к примеру, в два раза?

Давайте я вышлю по почте изданную работу на Ваш почтовый адрес. Сообщите, какой он. Вам с книгой, по моему, легче будет задавать вопросы, а мне отвечать. Я не умею оценивать временные затраты. Я занимался проверкой чисел, приемлемых для таблиц Эксель. Используемые делители 6 и 4. Посредством деления определяются: числовая ветвь, к которой принадлежит рассматриваемое число, номер числа, числовые ряды величин, используемых в решении квадратных уравнений двух вариантов: составленных по модулю 6 и мод 4. Алгоритм позволяет как бы синхранизировать расчеты. При получении одних и тех же результатов по обоим вариантам, обеспечивается получение подтверждения, что данное число принадлежит данным таблицам, составленным по используемым модулям. А раз принадлежит, оно составное. Максимальное количество проверок для каждого числа - по четырем вариантам. Всего проверочных вариантов 16. Их количество обусловлено вариациями четности координат. Возможных комбинаций четности четыре: чет, чет; нечет, нечет;чет, нечет; нечет, чет. Для каждой из этих комбинаций четности координат существует по четыре варианта возможных соответствий четности координат по мод 6, с вариантами четности координат по модулю 4. Пока не проверены все возможные варианты, окончательный ответ не возможен. Их всегда не более четырех. Остальные отсеиваются в результате предварительной проверки числа. Например, если номер четный, то вариант четности координат по мод 6 может быть либо: чет,чет; либо нечет, нечет. Так как один из вариантов выражения номера числа по мод 6: $N=6xy+x+y$. Для проверки простое или нет рассматриваемое число, расчеты могут производиться при использовании начальных значений числовых рядов, необходимые для расчета. Поэтому трудоемкость расчетов при проверке чисел на простоту зависит только от трудоемкости получения частных при делении числа на модули 6 и 4. Мне кажется, что это не может давать значительное увеличение затрат времени. По 16 расчетным страницам составлены программы с использованием таблиц Эксель. Максимальное количество производимых мною проверок - четыре. Это очень быстро - мгновенно. Конечно для тех чисел, которые я проверял. Iosif1

[PAV]

Книжку мне слать не надо, я этими вещами не занимаюсь и специально не интересуюсь. Но из Вашего текста я все равно ничего не понял. Давайте лучше сделайте так: разберите здесь пару примеров. Простых, чтобы было коротко, но чтобы был понятен смысл. Возьмите хотя бы двух- или трех-значное число и покажите, как с помощью Вашей методики проверить его на простоту. Тогда может быть что-то станет понятно.

[Iosif1]

Someone писал(а):

Я всё равно не понял, что такое эти Ваши "счисления", и как определить "координаты" числа в этих "счислениях". Что касается темы "Доказательство БТФ", то отсутствие обсуждения объясняется полной непонятностью Вашего текста.

Посмотрите пока мой ответ PAV.
Что такое мои счисления? Общепризнанные. Например: $10_{10}= 101_3$. Перевод десятичного счисления в третичное. И вот, если осуществлять перевод в счисление, равного величине рассматриваемой степени и основания и степени, обеспечивается наглядность закономерностей, существующих в степенных выражениях. На основании этих выявленных закономерностей и выполнен первый вариант доказательства БТФ. Оказалось, что при выполнении вводимого условия видно отличие степеней от не степеней уже по второму разряду (при счете справа налево). Это и позволило установить, что величины, которые должны быть точными степенями, таковыми быть не могут. Я уже написал кому то, что задача то для математических олимпиад семиклассников. Конечно, достаточно знакомых с используемым аппаратом. Я ознакомлюсь с материалом, согласно Вашим ссылкам. Я немного знаком с этой информацией. Считаю, что поставленные задачи победимы, но не в одиночку. Я и так прошел достаточно длиный путь. Если бы мог идти дальше в одиночку, может бы и попробовал. Но мне кажется, что если разработанная методика будет признана, лучше это делать совместно с профессионалами. Зачем соперничать с ними, лучше шагать в ногу. Iosif1

[Iosif1]

AndreyS писал(а):

В частности, он мне быстро обломал не одну "замечательную" (как в начале казалось) идею

Очень все в вашем письме для меня полезно. Я с Вами, не могу не соглашаться, так как кроме програмирования с помощью Эксель ни с чем не сталкивался. Хочу только заметить, что если бы не Эксель, у меня не возникла бы возможность вести с Вами беседу на форуме. Вы верно молоды, а я отнюдь. Пакета "Математика" у меня нет, и как я понимаю, для его изучения тоже нужен какой то период и практика. И поэтому, несмотря на то, что Ваши рекомендации, по моему мнению, очень полезны, я хотел бы продолжить попытки в упряжке с профессионалом. Конечно, если ему предлагаемый алгоритм приглянется. У меня действительно терминология не сопоставимая с требуемой (самостильные определения). А что делать, если даже не могу найти источник, на который можно было бы сослаться. Простительно: горный инженер. Неплохо знающий школьный курс математики. Насчет последовательности числового ряда, указанного мной, могу только сказать, что Вы, верно, меня не поняли. Я и отметил, что требуемая последовательность просчетов малоэффективна. Да, не в этом дело! По рекомендации PAV думаю завтра описать конкретный пример по определению делимости числа. Надеюсь прочесть потом Ваше мнение. Iosif1