Пусть B' = B + b, где b - погрешность. Тогда погрешность...26.10.04 06:08 Число просмотров: 3149 Автор: 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 - иррациональное.
Естесственно, что с иррациональными числами я могу работать только с некоторой степенью точности и, следовательно, у меня будет в результате некоторая погрешность. Имеется максимально допустимое значение погрешности и моя задача - найти такую точность 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' можно оценить как
Если 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
> Мне требуется вычислить целую часть от возведения 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, что бы понять, имеет ли хоть какой-то смысл мой алгоритм.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
