Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
Мощность - количество бит, необходимых для записи числа из указанного множества. Сенкс за погрешность. 26.10.04 15:43 Число просмотров: 3062
Автор: Heller <Heller> Статус: Elderman
|
|
|
|
<theory>
|
Возведение в иррациональную степень 22.10.04 14:56
Автор: Heller <Heller> Статус: Elderman
Отредактировано 22.10.04 14:59 Количество правок: 1
|
Мне требуется вычислить целую часть от возведения A в степень B: [A^B]. A - натуральное, B - иррациональное.
Естесственно, что с иррациональными числами я могу работать только с некоторой степенью точности и, следовательно, у меня будет в результате некоторая погрешность. Имеется максимально допустимое значение погрешности и моя задача - найти такую точность B, при которой погрешность вычислений не превысит максимального значения. (Точность надо определить заранее) Вроде как задача не из сложных, но меня она поставила в тупик.
Имеется и второй вопрос. Число A - большое, а B примерно равно мощности A (но не является двоичным логарифмом A, как кто-то может предположить). Интересует сложность такого возведения в степень. Интуитивно догадываюсь, что задача эта не является вычислительно сложной, однако с математическим доказательством опять же проблемы. Хотя, если предположение моё верно, то вполне устроит даже просто ссылка, где это подтверждено. Если получится найти конкретное выражение для сложности - будет вообще замечательно.
Заранее благодарен.
|
|
Пусть B' = B + b, где b - погрешность. Тогда погрешность... 26.10.04 06:08
Автор: RElf <M> Статус: Member
Отредактировано 26.10.04 06:14 Количество правок: 1
|
> Мне требуется вычислить целую часть от возведения A в
> степень B: [A^B]. A - натуральное, B - иррациональное.
> Естесственно, что с иррациональными числами я могу работать
> только с некоторой степенью точности и, следовательно, у
> меня будет в результате некоторая погрешность. Имеется
> максимально допустимое значение погрешности и моя задача -
> найти такую точность B, при которой погрешность вычислений
> не превысит максимального значения.
Пусть B' = B + b, где b - погрешность. Тогда погрешность A^B' можно оценить как
|A^B' -A^B= A^B' * |1 -A^(-b)~= A^B' (1 + b*ln(A)),
где ln() - натуральный логарифм.
Если c - требуемая погрешность A^B', то из неравенства
A^B' (1 + b*ln(A)) <= c
следует, что
b <= (c/(A^B') - 1) / ln(A).
> Имеется и второй вопрос. Число A - большое, а B примерно равно мощности A (но не является двоичным логарифмом A, как кто-то может предположить).
Что значит "мощность" числа?!
> Интересует сложность такого возведения в степень.
Сложность, очевидно, зависит от точности. Как именно - зависит от способа вычислений.
|
| |
Мощность - количество бит, необходимых для записи числа из указанного множества. Сенкс за погрешность. 26.10.04 15:43
Автор: Heller <Heller> Статус: Elderman
|
|
|
|
имхо можно предположить поряд необходимой точности числа В... 24.10.04 02:37
Автор: maggres Статус: Незарегистрированный пользователь
|
> Мне требуется вычислить целую часть от возведения A в
> степень B: [A^B]. A - натуральное, B - иррациональное.
> Естесственно, что с иррациональными числами я могу работать
> только с некоторой степенью точности и, следовательно, у
> меня будет в результате некоторая погрешность. Имеется
> максимально допустимое значение погрешности и моя задача -
> найти такую точность B, при которой погрешность вычислений
> не превысит максимального значения. (Точность надо
> определить заранее)
имхо можно предположить поряд необходимой точности числа В исходя из порядка(десятичного или двоичного не важно) числа А^[B] (А возведенное в целую степень от числа В). Соответсвенно если
А^[B] = 10^n то для числа В стоит взять не менее n знаков после запятой. Это что касается практики,
а вот мат. базу под это подвести сходу не получается...
>
> Имеется и второй вопрос. Число A - большое, а B примерно
> равно мощности A (но не является двоичным логарифмом A, как
> кто-то может предположить).
Интересует сложность такого
> возведения в степень. Интуитивно догадываюсь, что задача
> эта не является вычислительно сложной,
Задача возведения числа в степень имеет экспоненциальну сложность.
|
| |
Чуть подробнее 24.10.04 15:06
Автор: 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, что бы понять, имеет ли хоть какой-то смысл мой алгоритм.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
