Ещё один хейтер. Так а что обсуждать? Будет более быстрый солвер (может даже полиномиальный) - будет всё работать. А вам бы лишь бы загадить всё и всех.
512 бит факторизовать тоже не 2**512 времени заняло, так что и ваше предположение неверно. Другое дело что одни числа для SAT солвера просто берутся, а другие не берутся за время существования Вселенной, потому что солвер экспоненциальный. Но отличить простые от сложных - тоже NP-трудная задача, поэтому сказать что одно число простое а другое трудное для взятия солвером вы не можете. Как минимум, не предоставив полиномиального алгоритма выполнимости булевых формул.
Это задача "Синтез микропрограмм на основе решения булевых формул" из дальнейших исследований, которые я упоминаю в статье. По прямому алгоритму (например умножение или хеширование), сгенерировать обратный алгоритм используя выполнимость булевых формул.
Это ясно что не каждое число может быть разложено раньше окончания времени Вселенной, потому что солвер экспоненциальный, а не полиномиальный. Время в лучшем и худшем случае может сильно отличаться и для полиномиальных алгоритмов, а не то что экспоненциальных.
Но вот от количества единичек в числе это вряд ли зависит. Попробуйте ещё несколько чисел, чтобы найти вероятность, какую долю чисел солвер успевает вычислить за резонное время (нужно дать хотя бы те же 6 часов на вашем оборудовании).
Дело в том что после преобразования алгоритма умножение в формулу КНФ, все эти единички и нолики в числах очень сильно перемешиваются, до неузнаваемости, а как мы знаем - отличить лёгкую булеву формулу от сложной является тоже NP-трудной задачей. Раз вы её не решили, то и утверждать то что выше не можете.
Произведение равно 13407807926820848549984871491119855788235523322740973763876191939595871090961335127125233828880698995298214970593191507050244061726229325180256249012290513
да тут речь не о тщеславии, а чтоб элементарно брали на работу, а то меня уже лет 15 толком никуда не берут, типа я ничего не умею так выставляют. Приходишь на собеседование, а там так загнобят, что хочется то ли плакать, то ли лица бить...
И признание, и публикация конечно же важны. К наблюдению мне не привыкать. Вот именно что для дальнейшего развития ИИ очень важны быстрые алгоритмы выполнимости булевых формул, это добавило бы логику к ИИ, который сейчас (чисто нейронные сети) - с большего статистический и решать задачи может только в одно-два действия. Факторизация - это лишь способ продемонстрировать теперешние возможности SAT солверов. Главное всё-таки создать ИИ с логикой, а не чисто болтолога. Тогда автоматическое доказательство теорем позволит ИИ делать изобретения - типа межзвёздного двигателя.
Этот алгоритм легко распределяется на много потоков и/или машин, поэтому 6-ядерный десктопный Ryzen 3600 должен быть помощнее, чем одноядерный ноутбучный 13980HX.
В моей статье используется совершенно другой алгоритм, а именно выполнимость булевых формул.
Эффективность факторизации трудно оценивать. Тот алгоритм работает за его алгоритмическую сложность, и нахождения числа - вероятностно, как я понимаю. Здесь же в статье используется алгоритм, чья алгоритмическая сложность в худшем случае - невообразимое число даже на квантовых компьютерах. Но эвристики делают его практичным.
Да, для разных чисел может существенно отличаться время работы солвера.
Смотрите ответ выше - формула для RSA-512 стала в 10-15 раз больше чем для RSA-512. Конечно, это вопрос алгоритма решения выполнимости булевых формул - с текущим экспоненциальным алгоритмом и ускоряющими эвристиками, мы никогда не знаем, займёт это неделю или больше чем всё время Вселенной. Плюс для разных чисел сложность может существенно отличаться.
Так это ноутбучный проц, только 36 МБ кеша, а пыльный потому что ноут давно в чистку не сдавал. В итоге частота далека от заявленных 5.6 ГГц, а ноут с Ryzen 9955HX3D работает в разы быстрее на том же одном ядре, особенно когда данные в кеш вмещаются.
Да, формулы получаются немаленькие, но некоторые эвристики их берут. В данном случае, для RSA-512 получается формула из 202657 переменных и 1127580 выражений.
Сделал только что применение для этого движка: probqa.com. Сайт служит как система рекомендации игр для пользователей, которые слабо представляют, во что они следующее хотели бы поиграть. Не зная ключевых слов для поиска и описаний тысяч существующих игр, пользователь всё ещё может отвечать на вопросы путём кликанья на один из 5 вариантов ответа, и на каждом шаге получать список наиболее вероятных для него игр, исходя из ранее полученных программой ответов.
Книжки по физике на одну тему или на разные? Язык английский? Для русского не факт что моя программа работает сейчас.
В плане рекомендации, после «Гарри Поттера» действительно я бы лучше стал читать «Звёздные войны» чем Толкиена. По крайней мере фильмы и тот, и другой просмотрел, а «Властелин колец» смотреть не смог, выключил. У Толкиена специфический набор слов — все эти вымышленные персонажи как имена нарицательные. Это почти как другой язык получается.
Ещё один хейтер. Так а что обсуждать? Будет более быстрый солвер (может даже полиномиальный) - будет всё работать. А вам бы лишь бы загадить всё и всех.
ну это уже тонкости, для кого-то старый, для кого-то ещё не совсем - всё относительно)
я в демагогию вступать не буду - ищите кого другого хейтить, в идеале себя.
512 бит факторизовать тоже не 2**512 времени заняло, так что и ваше предположение неверно. Другое дело что одни числа для SAT солвера просто берутся, а другие не берутся за время существования Вселенной, потому что солвер экспоненциальный. Но отличить простые от сложных - тоже NP-трудная задача, поэтому сказать что одно число простое а другое трудное для взятия солвером вы не можете. Как минимум, не предоставив полиномиального алгоритма выполнимости булевых формул.
Это задача "Синтез микропрограмм на основе решения булевых формул" из дальнейших исследований, которые я упоминаю в статье. По прямому алгоритму (например умножение или хеширование), сгенерировать обратный алгоритм используя выполнимость булевых формул.
Это ясно что не каждое число может быть разложено раньше окончания времени Вселенной, потому что солвер экспоненциальный, а не полиномиальный. Время в лучшем и худшем случае может сильно отличаться и для полиномиальных алгоритмов, а не то что экспоненциальных.
Но вот от количества единичек в числе это вряд ли зависит. Попробуйте ещё несколько чисел, чтобы найти вероятность, какую долю чисел солвер успевает вычислить за резонное время (нужно дать хотя бы те же 6 часов на вашем оборудовании).
Дело в том что после преобразования алгоритма умножение в формулу КНФ, все эти единички и нолики в числах очень сильно перемешиваются, до неузнаваемости, а как мы знаем - отличить лёгкую булеву формулу от сложной является тоже NP-трудной задачей. Раз вы её не решили, то и утверждать то что выше не можете.
Произведение равно 13407807926820848549984871491119855788235523322740973763876191939595871090961335127125233828880698995298214970593191507050244061726229325180256249012290513
однопоточная программа, а не процессор.
да тут речь не о тщеславии, а чтоб элементарно брали на работу, а то меня уже лет 15 толком никуда не берут, типа я ничего не умею так выставляют. Приходишь на собеседование, а там так загнобят, что хочется то ли плакать, то ли лица бить...
И признание, и публикация конечно же важны. К наблюдению мне не привыкать. Вот именно что для дальнейшего развития ИИ очень важны быстрые алгоритмы выполнимости булевых формул, это добавило бы логику к ИИ, который сейчас (чисто нейронные сети) - с большего статистический и решать задачи может только в одно-два действия. Факторизация - это лишь способ продемонстрировать теперешние возможности SAT солверов. Главное всё-таки создать ИИ с логикой, а не чисто болтолога. Тогда автоматическое доказательство теорем позволит ИИ делать изобретения - типа межзвёздного двигателя.
посмотрите выше в комментариях - там решето уже обсуждалось (GNFS), вроде получилось медленнее для 512 бит, а 876 бит им вообще не взяли факторизацию.
вот только вроде как конкурс закрыли в 2007-м году: https://en.wikipedia.org/wiki/RSA_numbers . Или есть теперь другие конкурсы по факторизации?
спасибо Вам большое что сообщили, я не знал. Сейчас прямо вычисляю, но наверное другое число 2048-битное.
Для начала разберёмся, какой алгоритм использует CADO-NFS: https://chatgpt.com/share/68a3e312-c7c8-8000-abc5-9f7f1cf7bb44 . В кратце, числовое решето.
Этот алгоритм легко распределяется на много потоков и/или машин, поэтому 6-ядерный десктопный Ryzen 3600 должен быть помощнее, чем одноядерный ноутбучный 13980HX.
В моей статье используется совершенно другой алгоритм, а именно выполнимость булевых формул.
Эффективность факторизации трудно оценивать. Тот алгоритм работает за его алгоритмическую сложность, и нахождения числа - вероятностно, как я понимаю. Здесь же в статье используется алгоритм, чья алгоритмическая сложность в худшем случае - невообразимое число даже на квантовых компьютерах. Но эвристики делают его практичным.
Да, для разных чисел может существенно отличаться время работы солвера.
Смотрите ответ выше - формула для RSA-512 стала в 10-15 раз больше чем для RSA-512. Конечно, это вопрос алгоритма решения выполнимости булевых формул - с текущим экспоненциальным алгоритмом и ускоряющими эвристиками, мы никогда не знаем, займёт это неделю или больше чем всё время Вселенной. Плюс для разных чисел сложность может существенно отличаться.
Да, нормально так отличается формула - в 10-15 раз больше переменных и выражений для RSA-2048:
Так это ноутбучный проц, только 36 МБ кеша, а пыльный потому что ноут давно в чистку не сдавал. В итоге частота далека от заявленных 5.6 ГГц, а ноут с Ryzen 9955HX3D работает в разы быстрее на том же одном ядре, особенно когда данные в кеш вмещаются.
Да, формулы получаются немаленькие, но некоторые эвристики их берут. В данном случае, для RSA-512 получается формула из 202657 переменных и 1127580 выражений.
В плане рекомендации, после «Гарри Поттера» действительно я бы лучше стал читать «Звёздные войны» чем Толкиена. По крайней мере фильмы и тот, и другой просмотрел, а «Властелин колец» смотреть не смог, выключил. У Толкиена специфический набор слов — все эти вымышленные персонажи как имена нарицательные. Это почти как другой язык получается.