Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Чуть подробнее 24.10.04 15:06 Число просмотров: 3012
Автор: Heller <Heller> Статус: Elderman
|
> > Мне требуется вычислить целую часть от возведения A в
> > степень B: [A^B]. A - натуральное, B - иррациональное.
> > Естесственно, что с иррациональными числами я могу
> работать
> > только с некоторой степенью точности и, следовательно,
> у
> > меня будет в результате некоторая погрешность. Имеется
> > максимально допустимое значение погрешности и моя
> задача -
> > найти такую точность B, при которой погрешность
> вычислений
> > не превысит максимального значения. (Точность надо
> > определить заранее)
> имхо можно предположить поряд необходимой точности числа В
> исходя из порядка(десятичного или двоичного не важно) числа
> А^[B] (А возведенное в целую степень от числа В).
> Соответсвенно если
> А^[B] = 10^n то для числа В стоит взять не менее n знаков
> после запятой. Это что касается практики,
> а вот мат. базу под это подвести сходу не получается...
Если честно, то не совсем понял..
> > Имеется и второй вопрос. Число A - большое, а B
> примерно
> > равно мощности A (но не является двоичным логарифмом
> A, как
> > кто-то может предположить).
> Интересует сложность такого
> > возведения в степень. Интуитивно догадываюсь, что
> задача
> > эта не является вычислительно сложной,
> Задача возведения числа в степень имеет экспоненциальну
> сложность.
Что бы была яснее задача, объясню зачем мне это всё надо.
Идея моя связана, как обычно, со "взломом" RSA :-)
Я нашёл иррациональное число B такое, что открытый текст гарантированно находится в некоторой окрестности точки c^B mod n. Размер окрестности зависит только от погрешности вычисления c^B. Само B никак не связано с вычислением ф(n).
Таким образом, для расшифрования c мне требуется найти B с такой точностью, что бы окрестность не получилась очень большой, а потом найти саму точку по формуле c^B mod n и далее искать открытый текст перебором из найденной окрестности.
Вычисление самого B - тоже трудоёмкая задача и мне требуются конкретные формулы подсчёта сложности для нахождения "золотой середины" между вычислением B, возведением c в степень B и перебором всех допустимых значений из окрестности c^B. Ну и сравнить это всё со сложностью факторизации n, что бы понять, имеет ли хоть какой-то смысл мой алгоритм.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
