Проблема факторизации чисел возникла не вчера, она насчитывает тысячелетия. Можно лишь гадать почему в 1900 г на Математическом конгрессе Д. Гильберт не включил ее в список своих 23 проблем, а позднее она не попала в список нерешенных математических задач С. Улама. Особое внимание и интерес математиков к проблеме обозначился лишь в последние десятилетия. Возможно, стимулом стало открытие нового направления — двухключевой криптологии, появление шифров с открытым ключом. Можно предположить, что сегодняшний интерес к проблеме факторизации чисел продиктован некоторой неопределенностью относительно теоретического обоснования стойкости к раскрытию весьма популярного сегодня двухключевого шифра (личного ключа) RSA, который в принципе может быть взломан и без знания закрытого ключа. Бесключевое дешифрование. Просто в теории алгебраических колец до сих пор не найдены необходимые для этого результаты. Но есть не менее важный аспект этой проблемы — отсутствие операции обратной к умножению чисел. Простое быстрое и доступное мультипликативное разложение составных чисел может стать такой арифметической операцией, и пополнит арсенал вычислительных средств математики.
Краткое описание современной ситуации в области факторизации
Дабы прояснить ситуацию сегодняшнего дня в области факторизации натуральных чисел (элементов натурального ряда чисел (НРЧ)) и оценить возможности современного уровня ее разрешения фирмой RSA в 1991 г. был сформирован и опубликован список из 42 тестовых чисел различной разрядности от 100 до 617 десятичных цифр, позднее получивших название RSA-чисел. Фирмой было предложено всем желающим попробовать свои силы и использовать математическую подготовку в решении задачи факторизации больших чисел (ЗФБЧ) из этого списка. Для стимулирования активности участников за каждое факторизованное число была назначена премия. В условиях такого конкурса оговаривалось, что все числа списка получены путем перемножения лишь двух простых чисел практически одинаковой разрядности и, что разность этих сомножителей имеет разрядность такого же порядка (т.е. числа не близкие одно другому). «Конкурс» растянулся на два с лишним десятилетия и пока не завершен (список чисел не разложен). Возможно «конкурс» будет продолжен еще не на одно десятилетие. К настоящему времени опубликованы результаты разложения всего 13 первых чисел списка. Наибольшее из них описывается 232-мя десятичными цифрами, сомножители образованы 116-ю цифрами. Публикация об этом 2010 года.
Таблица 1 – Достижения в области факторизации больших чисел (модулей сравнения шифра RSA), список которых объявлен фирмой RSA в 1991 году.
Анализ почти 20-летних усилий и результатов успешной факторизации RSA-чисел позволяет сделать вывод о том, что методы, используемые коллективами и отдельными математиками при решении ЗФБЧ, существенным образом зависят от такого свойства факторизуемого числа как его длина. Чем длиннее число, тем больше лет требовалось для его факторизации.
Спустя 10-15 лет представители фирмы перестали беспокоиться по поводу скорого краха, спокойно и успешно функционируют по сей день. Так в финансовом отчете фирмы за 2003 год говорилось о реализации на рынке ≈500 млн копий программ шифрования. Стойкость шифра к взлому обеспечивается невозможностью за приемлемое для практики (часы, сутки) время решить ЗФБЧ. Это подтверждается многолетними попытками факторизации чисел из списка и исследованиями в этой области. Но при этом не отрицается, что при изобретении более совершенного алгоритма решения ЗФБЧ или какого-либо другого атакующего алгоритма (например, бесключевого дешифрования) шифр не устоит.
Если принцип алгоритмизации решения ЗФБЧ останется прежним, то фирма простым увеличением длины ключа продлит жизненный цикл шифра, быстродействие которого, конечно, будет хуже, но останется приемлемым для части пользователей.
В этой работе не будут рассматриваться алгоритмы, решающие ЗФБЧ годами. Скажем только, что все они используют идеи числовых решет, начиная от решета Эратосфена, затем Бруна, Сельберга, Линника, Ленстры и т.п… Эти алгоритмы последовательно во времени модифицируются и совершенствуются на протяжении десятилетий, а «воз и ныне там». Привлечение теории эллиптических кривых несколько улучшает ситуацию, но к коренному перелому ситуации не приводит.
Считаю названное направление и подход в целом тупиковым. Повышение быстродействия вычислителей, распараллеливание процессов в рамках сохраняющегося принципа ситуацию не улучшит. Просто решение станет более дорогим.
Мотивация нового подхода
Перспективный выход из сложившегося положения видится таким. Необходимо совместно рассматривать число и окружающую его область, совместно разрабатывать математические алгоритмы решения ЗФБЧ на основе свойств факторизуемых чисел и числовой системы, которые были бы свободны от разрядности чисел, не зависели от их длины. Свойства числовой системы при этом нельзя игнорировать, что достаточно наглядно демонстрирует открытый автором «Закон распределения делителей в НРЧ». Это новый теоретический фундаментальный результат. Закон распределения делителей. Закон указывает для любого составного нечетного натурального числа (сннч), где в ограниченной области НРЧ лежат его делители или кратные им числа. Только при выполнении названных условий алгоритм сможет обеспечить высокое быстродействие, и время t получения решения не будет зависеть от длины числа N.
Подтверждением потенциальных возможностей таких алгоритмов служат широко известные признаки делимости чисел. Так, свойство числа иметь свертку s(N) – сумму цифр числа, кратную трем не зависит от его длины или зависимость эта очень слабая. Числа произвольной длины с таким свойством на ПК делятся на 3 практически мгновенно. Другие свойства, называемые признаками делимости, используемые при факторизации N, обеспечивают успешное решение нахождение частных разложений. К сожалению, известные в настоящее время свойства чисел и их систем не обеспечивают полного решения проблемы. С другой стороны, они демонстрируют возможности практически мгновенно в частных случаях проблему факторизации закрыть. В этом я вижу один из намеков нам со стороны числовой системы, на скрытые пока от нас возможности решения ЗФБЧ. Другой намек — бесключевое дешифрование. Периодичность появления исходного текста очевидна, ищите период.
Отсюда возникает потребность и необходимость поиска новых свойств, свободных от длины числа и использование их при разработке алгоритмов факторизации. Примером такого нового свойства является найденный автором новый ф-инвариант числа Новый инвариант числа.
Моделирование и базис исследований
В большинстве математических исследований объектов важную роль играют математические модели объектов. Разработка таких моделей для отдельного числа и их системы (НРЧ) представляет самостоятельное направление в исследованиях. Автором в опубликованных работах предложено несколько различных моделей и НРЧ, и отдельных натуральных чисел.
Читателю (не боги горшки обжигают), желающему всерьез заняться (не на коленке, как написал один из комментаторов) проблемой факторизации чисел, а возможно и других объектов (матриц, многочленов …), излагаемые в работах подходы к моделированию окажут существенную помощь и могут служить начальными примерами.
Где сегодня можно почитать о распределении делителей натурального числа в НРЧ? Кто из известных математиков публиковал материалы об этом? Где в НРЧ могут находиться простые числа, а где нет? Область запрета. Как можно моделировать натуральный ряд? Как устроены числа НРЧ? Классы чисел
Эти и другие вопросы возникали у автора, на которые приходилось искать ответы, перелопачивая можно сказать, горы литературы от Н. Бурбаки и многотомных энциклопедий до учебных пособий творчески работающих авторов. На ряд вопросов ответы найти пока не удалось, а на некоторые пришлось ответы творить самостоятельно. Что-то удалось строго доказать, что-то остается на уровне гипотез.
Возможно, не всем читателям представленные результаты покажутся интересными и важными. Автор убежден тому, кому это интересно, результаты будут весьма полезны. Думаю, что пока почитать об этом больше просто негде. Это новые и оригинальные результаты. Кто в состоянии быть объективным может это увидеть и оценить.
В цикле опубликованных работ излагается определенный базис знаний в четко определенной области: НРЧ и его элементы. После этих публикаций мои ученики получили возможность более основательно познакомиться с тем материалом, который им излагался устно, или вообще не доводился. Среди учеников люди с разным уровнем подготовки есть школьники, студенты, выпускники ВУЗов, специалисты со степенями и с учеными званиями. В первую очередь для меня имеют значение их реакция на текст и их вопросы к автору. В нашей жизни есть вещи важнее рейтингов и кармы, а в целом я Хабру благодарен за предоставленную возможность поместить у него свои тексты.
О форме и стиле изложения текстов
В комментариях к моим работам читателями высказывались замечания, пожелания, советы и критика. Благодарю всех за внимание к работам. Я не программист (не кодирую алгоритмы в языках высокого уровня), не IT- шник. Пишу как считаю нужным и учусь оформлению. Стиль изложения работ мной выбран сознательно. Стремление излагать материал просто и доступно даже для начинающего читателя-исследователя определило и элементарность используемых понятий, определений и средств. Это, конечно же, не означает, что все в текстах очень просто. Для усвоения содержания и смысла любой работы от читателя всегда требуются определенные усилия и временные затраты. Предлагаемые вниманию читателя работы не являются легким чтивом, это не перечисление любопытных занимательных фактов. Поверхностное ознакомление с работами у некоторых читателей оставляет вообще ощущение лженауки или чуши. Что с этим можно поделать? Даже советовать не хочу.
Личный опыт показывает, насколько трудно бывает вникнуть в чужую работу, если ее автор не ставил перед собой задачу сделать ее для читателя доступной и понятной, не сопроводил сквозным числовым примером и еще злоупотребляет словосочетанием «отсюда легко следует…». Даже П. Лапласу однажды пришлось на одно такое «отсюда легко следует…» потратить около двух месяцев для восполнения пробела.
Для себя считаю, что хорошим примером изложения порой не простых вопросов являются оригинальные тексты Эйлера или Ньютона. Сейчас в таком стиле не пишут. Рекомендую, если повезет, у букиниста откройте старый фолиант этих авторов и полистайте его. Латынь, на которой написан текст, можно пропустить, но математические выкладки вполне современны и вызывают восхищение. Подробно, неторопливо выполняются даже простые преобразования, и, видимо, также комментируются формулы латинским текстом.
Краткое описание современной ситуации в области факторизации
Дабы прояснить ситуацию сегодняшнего дня в области факторизации натуральных чисел (элементов натурального ряда чисел (НРЧ)) и оценить возможности современного уровня ее разрешения фирмой RSA в 1991 г. был сформирован и опубликован список из 42 тестовых чисел различной разрядности от 100 до 617 десятичных цифр, позднее получивших название RSA-чисел. Фирмой было предложено всем желающим попробовать свои силы и использовать математическую подготовку в решении задачи факторизации больших чисел (ЗФБЧ) из этого списка. Для стимулирования активности участников за каждое факторизованное число была назначена премия. В условиях такого конкурса оговаривалось, что все числа списка получены путем перемножения лишь двух простых чисел практически одинаковой разрядности и, что разность этих сомножителей имеет разрядность такого же порядка (т.е. числа не близкие одно другому). «Конкурс» растянулся на два с лишним десятилетия и пока не завершен (список чисел не разложен). Возможно «конкурс» будет продолжен еще не на одно десятилетие. К настоящему времени опубликованы результаты разложения всего 13 первых чисел списка. Наибольшее из них описывается 232-мя десятичными цифрами, сомножители образованы 116-ю цифрами. Публикация об этом 2010 года.
Таблица 1 – Достижения в области факторизации больших чисел (модулей сравнения шифра RSA), список которых объявлен фирмой RSA в 1991 году.
Анализ почти 20-летних усилий и результатов успешной факторизации RSA-чисел позволяет сделать вывод о том, что методы, используемые коллективами и отдельными математиками при решении ЗФБЧ, существенным образом зависят от такого свойства факторизуемого числа как его длина. Чем длиннее число, тем больше лет требовалось для его факторизации.
Спустя 10-15 лет представители фирмы перестали беспокоиться по поводу скорого краха, спокойно и успешно функционируют по сей день. Так в финансовом отчете фирмы за 2003 год говорилось о реализации на рынке ≈500 млн копий программ шифрования. Стойкость шифра к взлому обеспечивается невозможностью за приемлемое для практики (часы, сутки) время решить ЗФБЧ. Это подтверждается многолетними попытками факторизации чисел из списка и исследованиями в этой области. Но при этом не отрицается, что при изобретении более совершенного алгоритма решения ЗФБЧ или какого-либо другого атакующего алгоритма (например, бесключевого дешифрования) шифр не устоит.
Если принцип алгоритмизации решения ЗФБЧ останется прежним, то фирма простым увеличением длины ключа продлит жизненный цикл шифра, быстродействие которого, конечно, будет хуже, но останется приемлемым для части пользователей.
В этой работе не будут рассматриваться алгоритмы, решающие ЗФБЧ годами. Скажем только, что все они используют идеи числовых решет, начиная от решета Эратосфена, затем Бруна, Сельберга, Линника, Ленстры и т.п… Эти алгоритмы последовательно во времени модифицируются и совершенствуются на протяжении десятилетий, а «воз и ныне там». Привлечение теории эллиптических кривых несколько улучшает ситуацию, но к коренному перелому ситуации не приводит.
Считаю названное направление и подход в целом тупиковым. Повышение быстродействия вычислителей, распараллеливание процессов в рамках сохраняющегося принципа ситуацию не улучшит. Просто решение станет более дорогим.
Мотивация нового подхода
Перспективный выход из сложившегося положения видится таким. Необходимо совместно рассматривать число и окружающую его область, совместно разрабатывать математические алгоритмы решения ЗФБЧ на основе свойств факторизуемых чисел и числовой системы, которые были бы свободны от разрядности чисел, не зависели от их длины. Свойства числовой системы при этом нельзя игнорировать, что достаточно наглядно демонстрирует открытый автором «Закон распределения делителей в НРЧ». Это новый теоретический фундаментальный результат. Закон распределения делителей. Закон указывает для любого составного нечетного натурального числа (сннч), где в ограниченной области НРЧ лежат его делители или кратные им числа. Только при выполнении названных условий алгоритм сможет обеспечить высокое быстродействие, и время t получения решения не будет зависеть от длины числа N.
Подтверждением потенциальных возможностей таких алгоритмов служат широко известные признаки делимости чисел. Так, свойство числа иметь свертку s(N) – сумму цифр числа, кратную трем не зависит от его длины или зависимость эта очень слабая. Числа произвольной длины с таким свойством на ПК делятся на 3 практически мгновенно. Другие свойства, называемые признаками делимости, используемые при факторизации N, обеспечивают успешное решение нахождение частных разложений. К сожалению, известные в настоящее время свойства чисел и их систем не обеспечивают полного решения проблемы. С другой стороны, они демонстрируют возможности практически мгновенно в частных случаях проблему факторизации закрыть. В этом я вижу один из намеков нам со стороны числовой системы, на скрытые пока от нас возможности решения ЗФБЧ. Другой намек — бесключевое дешифрование. Периодичность появления исходного текста очевидна, ищите период.
Отсюда возникает потребность и необходимость поиска новых свойств, свободных от длины числа и использование их при разработке алгоритмов факторизации. Примером такого нового свойства является найденный автором новый ф-инвариант числа Новый инвариант числа.
Моделирование и базис исследований
В большинстве математических исследований объектов важную роль играют математические модели объектов. Разработка таких моделей для отдельного числа и их системы (НРЧ) представляет самостоятельное направление в исследованиях. Автором в опубликованных работах предложено несколько различных моделей и НРЧ, и отдельных натуральных чисел.
Читателю (не боги горшки обжигают), желающему всерьез заняться (не на коленке, как написал один из комментаторов) проблемой факторизации чисел, а возможно и других объектов (матриц, многочленов …), излагаемые в работах подходы к моделированию окажут существенную помощь и могут служить начальными примерами.
Где сегодня можно почитать о распределении делителей натурального числа в НРЧ? Кто из известных математиков публиковал материалы об этом? Где в НРЧ могут находиться простые числа, а где нет? Область запрета. Как можно моделировать натуральный ряд? Как устроены числа НРЧ? Классы чисел
Эти и другие вопросы возникали у автора, на которые приходилось искать ответы, перелопачивая можно сказать, горы литературы от Н. Бурбаки и многотомных энциклопедий до учебных пособий творчески работающих авторов. На ряд вопросов ответы найти пока не удалось, а на некоторые пришлось ответы творить самостоятельно. Что-то удалось строго доказать, что-то остается на уровне гипотез.
Возможно, не всем читателям представленные результаты покажутся интересными и важными. Автор убежден тому, кому это интересно, результаты будут весьма полезны. Думаю, что пока почитать об этом больше просто негде. Это новые и оригинальные результаты. Кто в состоянии быть объективным может это увидеть и оценить.
В цикле опубликованных работ излагается определенный базис знаний в четко определенной области: НРЧ и его элементы. После этих публикаций мои ученики получили возможность более основательно познакомиться с тем материалом, который им излагался устно, или вообще не доводился. Среди учеников люди с разным уровнем подготовки есть школьники, студенты, выпускники ВУЗов, специалисты со степенями и с учеными званиями. В первую очередь для меня имеют значение их реакция на текст и их вопросы к автору. В нашей жизни есть вещи важнее рейтингов и кармы, а в целом я Хабру благодарен за предоставленную возможность поместить у него свои тексты.
О форме и стиле изложения текстов
В комментариях к моим работам читателями высказывались замечания, пожелания, советы и критика. Благодарю всех за внимание к работам. Я не программист (не кодирую алгоритмы в языках высокого уровня), не IT- шник. Пишу как считаю нужным и учусь оформлению. Стиль изложения работ мной выбран сознательно. Стремление излагать материал просто и доступно даже для начинающего читателя-исследователя определило и элементарность используемых понятий, определений и средств. Это, конечно же, не означает, что все в текстах очень просто. Для усвоения содержания и смысла любой работы от читателя всегда требуются определенные усилия и временные затраты. Предлагаемые вниманию читателя работы не являются легким чтивом, это не перечисление любопытных занимательных фактов. Поверхностное ознакомление с работами у некоторых читателей оставляет вообще ощущение лженауки или чуши. Что с этим можно поделать? Даже советовать не хочу.
Личный опыт показывает, насколько трудно бывает вникнуть в чужую работу, если ее автор не ставил перед собой задачу сделать ее для читателя доступной и понятной, не сопроводил сквозным числовым примером и еще злоупотребляет словосочетанием «отсюда легко следует…». Даже П. Лапласу однажды пришлось на одно такое «отсюда легко следует…» потратить около двух месяцев для восполнения пробела.
Для себя считаю, что хорошим примером изложения порой не простых вопросов являются оригинальные тексты Эйлера или Ньютона. Сейчас в таком стиле не пишут. Рекомендую, если повезет, у букиниста откройте старый фолиант этих авторов и полистайте его. Латынь, на которой написан текст, можно пропустить, но математические выкладки вполне современны и вызывают восхищение. Подробно, неторопливо выполняются даже простые преобразования, и, видимо, также комментируются формулы латинским текстом.
