если ты, crypto, хорошо кодишь, то присоеденяйся - я уже сказал здесь, что мне щас нужно. а, вообще, я занялся этой темой, потому что мне показалось реально глупым, что такой детсадовский алгоритм, как RSA, что - то там защищяет )
UbIvItS Извини, я занят сейчас другим проектом. А если бы я занялся простыми числами, то кодить бы в стал последнюю очередь - после разработки математической основы алгоритма. И RSA вовсе не детсадовский алгоритм - очень изящный с точки зрения математика. Ты думаешь, чем навороченнее, тем лучше? Сомневаюсь, чем навороченнее - тем непонятнее и тем больше шансов промахнуться.
не, crypto, я не о простоте говорил, а о самой основе надежности - факторизации. а насчет разработки мат. основы для нее нужна "пища" -факты, а один из способов их получения - эксперемент.
вначале мат. анализ не имел жесткой теор. основы, но его части применялись на практике и только потом стали появляться теории и док-ва.
UbIvItS Правильно говоришь - надежность алгоритма основана на проблеме факторизации, как только ее решат, часть криптографии уйдет в небытие. Но все-таки это не повод называть алгоритм детсадовским. Решишь проблему - честь тебе и хвала, и всевозможные заслуженные почести отечественной и мировой науки!
UbIvItS Кстати, пару лет назад появилась статья каких-то китайцев (под рукой нет, дома лежит, поэтому авторов и названия я не смогу привести), они заявляли, что разработали алгоритм полиномиальной сложности для факторизации чисел. Я читал эту статью, откровенно - так и не понял, в чем же изюмина и как соб-но надо раскладывать числа. Ты уж наверное в курсе последних достижений - все это лажей оказалось?
Честно сказать, нечего про другие разработки подобного толка не знаю: в основном слухи, намёки - конкретики 0. А то, что я написал, надеюсь, понятно??
UbIvItS Скачал файл (с энной попытки, спасибо narod.ru..) и посмотрел, правда только первый способ "Дельта – Правый (базис А).". Не думаю, что другие кардинально отличаются. Способ не лишен интереса, но не более. Прикладного значения в данном виде не имеет никакого, да и способом факторизации назвать нельзя. Хотя бы просто потому, что факторизует (мягко говоря) далеко не все числа. Гораздо более интересным было бы исследование, какой процент чисел можно разложить твоим способом. Ответ должен быть по идее связан с теоремами о распределении делителей произвольных целых чисел, так как понятно, что для успешного применения твоего способа необходимо (но не достаточно), чтобы наименьший из делителей рос медленнее, чем сумма остатков. По этой теме можно найти в сети достаточно большое количество литературы, начиная с того же Кнута. А если сюда заглянет RElf, то он тебе наверное и так скажет >но множество чисел, на котором они действенны, скажем так, не пусто Угу. Более 75% всех чисел делятся на 2,3,5 или 7. Ты уверен, что твой метод даст лучший результат?
Дельта -Правый не имеет практического интереса. По настоящему эффективен Dee..ep, ещё можно брать расширенные версии, но не ниже
и, вообще, прежде чем выкладывать свои суждения, нужно как можно лучше ознакомиться с предоставленным материалом.
UbIvItS По предоставленному файлу невозможно понять, что такое Dee..ep и как оно должно работать. Кроме того, если я правильно понял, слова "n устойчиво ко всем методам серии “базис A”, если из полученных вычетов нельзя получить сумму равную qr, где 1<=r<p." относятся ко всем перечисленным вариантам? Да и не в том дело. Просто если хочешь описать новый способ факторизации, то начинаешь не с "как", а с почему. Почему оно работает, какая идею используется, почему любое число таким образом раскладывается. Если не любое и не всегда, то опять же точное описание, при каких условиях метод не работает и почему. Все естественно с доказательствами. И только в самом конце оценка скорости. Пока что твой способ эквивалентен среднепотолочному тыку: "сделайте так-то и так-то и может повезет, ну а не повезет, значит судьба такой". А кому охота делителей по потолку гадать?
Dee..ep DF-- и BS (расширенные версии тоже можно юзать в таком контексте) могут прощупывать n на различных степенях, если n устойчиво в исконном своём виде - отсюда два вопроса: 1. Существуют ли числа устойчивые на сверхстепенях (n^t , где t стремится в бесконечность)? 2. Возможна ли быстрая генерация таких чисел?
если мы получили qr, тогда qt=n mod qr. q*t1= qr mod qt ....... итак до тех пор пока не получим q - это и есть отличее дии..ипа от расширенной версии дельта - левого, где делается предположение, что q=n mod qr, т.е., получив qt, где t>1 - Delta -Left eXt промахнется.
ну, а если qr нормальный не получен, то цикл упрется в 1, возьмёт новый qr и по той же схеме его обработает его.
ну, если кому работа Dee..ep'а не понятна покажу на числах: qr = 35, qt =21 14= 35 mod 21 7 = 21 mod 14 0 = 14 mod 7 - фактор получен qr =35 qt = 22 13 = 35 mod 22 9 = 22 mod 13 4 = 13 mod 9 1 = 9 mod 4 - фактор не получен
UbIvItS Я нашел эту статью. Написали ее индусы (а не китайцы) Manindra Agrawal, Neeraj Kayal, Nitin Saxena в августе 2002 года. Называется "PRIMES is in P", где опубликована, хз, инфа потеряна. В Abstract говорится ни много ни мало, что они представили детерминированный алгоритм с полиномиальным временем выполнения, определяющий, является ли искомое число n простым или составным. Вот мне и интересно, кто-нибудь в этой статье ковырялся, есть там зерна истины или одни плевелы?
crypto AKS - вполне работающий и достаточно красивый полиномиальный алгоритм. И статья хорошо написана, подробно. Но для больших чисел он мало пригоден и не применяется, так как проигрывает по скорости на много порядков вероятностным тестам, не давая практически ничего взамен. Как правило используются тесты типа BPSW Если не ошибаюсь кстати, их алгоритм был не первым известным с полиномиальным временем. P.S. На всякий случай: ответить на вопрос, является ли число простым, еще не значит найти его факторы
