Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Алгоритм факторизации за *константное* время уже есть :-) [updated] 08.06.04 13:45 Число просмотров: 5717
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 08.06.04 13:54 Количество правок: 1
|
Если немного подумать, то проблема, которая не позволяет быстро факторизовать числа лежит в основе системы счисления. В римской системе счисления задача умножения (а уж тем более деления) двух чисел NP-полная (если мне ничего не изменяет), в позиционной же системе эти задачи тривиальны.
Если подумать еще немного, то корень зла позиционной системы кроется в переносе. То есть информация о числе хранится ТОЛЬКО во всем числе. Изменения в одном разряде могут привести к переносу информации из этого разряда во ВСЕ остальные разряды. И обрабатывать такие числа нужно целиком - не пережевывая. А от больших кусков бывают несварения. (сравнить можно с фотографией и голограммой, по части фотографии ничего нельзя сказать об остальной части, а в части голограммы есть информация обо всем изображении)
> Что нужно, чтоб поломать РСА - совсем немного.
> Знание арифметики на уровне начальной школы, а если уж знание
> логарифмов, то совсем замечательно
Вот как раз арифметику знать крайне вредно.
Для нахождения алгоритма быстрой факторизации нужно всего ничего: ВООБЩЕ не слушать то, чему учили в школе на уроках математики. Забыть про всякие таблицы умножения и придумать новую систему счисления (обязательно непозиционную), в которой эта задача станет тривиальной.
Из всего, что я видел, ближе всего к данной проблеме подобрался Акушский со своей системой остаточных классов: число разбивается на набор остатков от деления на взаимнопростые числа. Эти остатки однозначно определяют число на промежутке от 0 до (П(всех модулей) - 1), где П - произведение. С каждым из модулей можно производить действия независимо от других (следует из упомянутых уже мной свойств сравнений)
> пока никто не нашел. Определение говорит само за себя:
> "Алгоритмы шифрования с открытым ключем, постоенные на
> основе проблемы разложения больших чисел на простые
> сомножители, стойки до тех пор, пока не найдется человек,
> которому не придет в голову метод быстрой факторизации или
> модульного логарифмирования".
Ровно как и алгоритм поиска ключа в несортированной базе данных за константное время. Одна беда - написаны они для квантового компьютера :-)
Хотя все равно секьюрити-специалистам государственного уровня (ну и спецам, занимающимся охраной КРУПНЫХ коммерческих тайн типа банков и пр.) следует серьезно задуматься.
> Не делайте из этого тайны, даже если удача Вам (volizar)
> улыбнется, останется либо отрезать себе язык, либо быстро
> везде опубликовать, если не хотите, чтобы заинтересованные
> люди вытащили идею из Вас при помощи паяльника/утюга, а
> потом избавились от знающего человека.
Это да
> > Так что либо хоть как-нибудь излагайте, либо
> соблюдайте
> > тишину.
>
> Поддерживаю.
Тоже
|
|
|
подробно о проекте
Анализ криптографических сетевых...
