информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
имхо можно предположить поряд необходимой точности числа В... 24.10.04 02:37  Число просмотров: 3036
Автор: maggres Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Мне требуется вычислить целую часть от возведения A в
> степень B: [A^B]. A - натуральное, B - иррациональное.
> Естесственно, что с иррациональными числами я могу работать
> только с некоторой степенью точности и, следовательно, у
> меня будет в результате некоторая погрешность. Имеется
> максимально допустимое значение погрешности и моя задача -
> найти такую точность B, при которой погрешность вычислений
> не превысит максимального значения. (Точность надо
> определить заранее)
имхо можно предположить поряд необходимой точности числа В исходя из порядка(десятичного или двоичного не важно) числа А^[B] (А возведенное в целую степень от числа В). Соответсвенно если
А^[B] = 10^n то для числа В стоит взять не менее n знаков после запятой. Это что касается практики,
а вот мат. базу под это подвести сходу не получается...

>
> Имеется и второй вопрос. Число A - большое, а B примерно
> равно мощности A (но не является двоичным логарифмом A, как
> кто-то может предположить).
Интересует сложность такого
> возведения в степень. Интуитивно догадываюсь, что задача
> эта не является вычислительно сложной,
Задача возведения числа в степень имеет экспоненциальну сложность.
<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, что бы понять, имеет ли хоть какой-то смысл мой алгоритм.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach