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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
объясняю 27.10.06 03:58  Число просмотров: 1846
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
[moved from beginners]
смотри - в начальной задаче: 2^x-2^y ты легко нашел соответствие x,y от n (и считается оно быстро)

а что такое задача факторизации? n=p*q - по n найти p и q (аналогии не видишь?)
задачу факторизации можно предствить еще так:
т.к. любое нечетное число можно разложить на разность квадратов - получаем
n = x^2 - y^2 = (x-y)*(x+y)
p = x-y
q = x+y

а риторический вопрос в том, что, если перевернуть формулу - то получается полная %опа. Никак не найти прямое соответствие x,y от n
<miscellaneous>
Народ, а как насчет математической задачки всвязи с этим? 26.10.06 20:00   [Den, whiletrue]
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 26.10.06 20:06  Количество правок: 1
<"чистая" ссылка>
Числа, где вначале 1-ки, а потом 0-й - это 2^x-2^y
Вопрос: какой формулой можно расположить их в порядке возрастания? (имеется ввиду не маска, любое кол-во байт) =)
В Misc, однозначно! 27.10.06 12:26  
Автор: Den <Denis> Статус: The Elderman
<"чистая" ссылка>
[moved from beginners]
Я тоже не совсем понял чего надо 26.10.06 21:47  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 26.10.06 21:48  Количество правок: 1
<"чистая" ссылка>
[moved from beginners]
> Числа, где вначале 1-ки, а потом 0-й - это 2^x-2^y
> Вопрос: какой формулой можно расположить их в порядке
> возрастания? (имеется ввиду не маска, любое кол-во байт) =)

Что значит какой формулой? Если по какому ключу сортировать, чтобы они возрастали, то ответ очевиден: по вот этому 2x - 2y. А если алгоритмически (без насточщего возведения и даже без сдвигов), то

bool
less(x1, y1, x2, y2) {
return (x1 < x2|(x1 == x2 && y1 < y2));
}

---
ну это числа (в порядке возрастания) [upd] 26.10.06 23:14  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 27.10.06 00:19  Количество правок: 8
<"чистая" ссылка>
[moved from beginners]
> > Числа, где вначале 1-ки, а потом 0-й - это 2^x-2^y
> > Вопрос: какой формулой можно расположить их в порядке
> > возрастания? (имеется ввиду не маска, любое кол-во
> байт) =)
>
> Что значит какой формулой? Если по какому ключу
> сортировать, чтобы они возрастали, то ответ очевиден: по
> вот этому 2x -
> 2y. А если алгоритмически (без
> насточщего возведения и даже без сдвигов), то
>
>
bool> less(x1, y1, x2, y2) {
> return (x1 < x2|(x1 == x2 && y1 < y2));
> }

---

ну это числа (в порядке возрастания) (для x>y>0)

1-е: 10 = 2
2-е: 100 = 4
3-е: 110 = 6
4-е: 1000 = 8
5-е: 1100 = 12
6-е: 1110 = 14
7-е: 10000 = 16
8-е: 11000 = 24
...

Это табличное задание F(n)
А формула какая?
Немного не догнал: что такое F(n)? (как называется) 27.10.06 13:08  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Ну это довольно просто на самом деле 27.10.06 02:43  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
[moved from beginners]
> 1-е: 10 = 2
> 2-е: 100 = 4
> 3-е: 110 = 6
> 4-е: 1000 = 8
> 5-е: 1100 = 12
> 6-е: 1110 = 14
> 7-е: 10000 = 16
> 8-е: 11000 = 24
> ...
>
> Это табличное задание F(n)
> А формула какая?

x(n) = int((sqrt(8 * n + 1) + 3) / 2)
int - целая часть
y(n) = (x(n) + 1) * x(n) / 2 - n

Я даже проверил
> f := (x, y) -> 2 ^ x - 2 ^ y;
> fx := n -> trunc((sqrt(8 * n + 1) + 3) / 2);
> fy := (n) -> (fx(n) - 1) * fx(n) / 2 - n;

                                        x    y
                        f := (x, y) -> 2  - 2


              fx := n -> trunc(1/2 sqrt(8 n + 1) + 3/2)


                 fy := n -> 1/2 (fx(n) - 1) fx(n) - n

> seq(f(evalf(fx(i)), evalf(fy(i, fx(i)))), i = 0..10);
> seq(convert(f(evalf(fx(i)), evalf(fy(i, fx(i)))), binary), i = 0..10);

          2., 4., 6., 8., 12., 14., 16., 24., 28., 30., 32.


  10., 100., 110., 1000., 1100., 1110., 10000., 11000., 11100.,

        11110., 100000.

> 

---
А вот теперь вопрос риторический =) 27.10.06 03:20  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 27.10.06 03:23  Количество правок: 1
<"чистая" ссылка>
[moved from beginners]
> > 1-е: 10 = 2
> > 2-е: 100 = 4
> > 3-е: 110 = 6
> > 4-е: 1000 = 8
> > 5-е: 1100 = 12
> > 6-е: 1110 = 14
> > 7-е: 10000 = 16
> > 8-е: 11000 = 24
> > ...
> >
> > Это табличное задание F(n)
> > А формула какая?
>
> x(n) = int((sqrt(8 * n + 1) + 3) / 2)
> int - целая часть
> y(n) = (x(n) + 1) * x(n) / 2 - n

ну... че-то в это роде и у меня получалось, там даже взаимооднозначное соответствие между (x,y) и n (в смысле и туда и обратно быстро можно посчитать)

> Я даже проверил

спасибо, что проверил..

А вот тепрь риторический вопрос:
почему если слегка изменить изначальную формулу: x^2-y^2 =)))))
то все становится оооооооооооочень плохо!!!
Опять не понял вопрос 27.10.06 03:38  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
[moved from beginners]
> А вот тепрь риторический вопрос:
> почему если слегка изменить изначальную формулу: x^2-y^2
> =)))))
> то все становится оооооооооооочень плохо!!!

Наверное как раз потому, что формулы для x и y рассчитывались именно для этой самой "изначальной формулы". Если изменить ее, то надо проводить расчеты с самого начала.
Не выйдет ничего, просто. Эта задача = задача факторизации =))) 27.10.06 03:41  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
[moved from beginners]
Какая задача? Я действительно не понял в чем состоял "риторический вопрос" :-) 27.10.06 03:50  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 27.10.06 04:32  Количество правок: 1
<"чистая" ссылка>
[moved from beginners]
А ответил наобум
объясняю 27.10.06 03:58  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
[moved from beginners]
смотри - в начальной задаче: 2^x-2^y ты легко нашел соответствие x,y от n (и считается оно быстро)

а что такое задача факторизации? n=p*q - по n найти p и q (аналогии не видишь?)
задачу факторизации можно предствить еще так:
т.к. любое нечетное число можно разложить на разность квадратов - получаем
n = x^2 - y^2 = (x-y)*(x+y)
p = x-y
q = x+y

а риторический вопрос в том, что, если перевернуть формулу - то получается полная %опа. Никак не найти прямое соответствие x,y от n
Не вкурил :)) 26.10.06 20:07  
Автор: NKritsky <Nickolay A. Kritsky> Статус: Elderman
<"чистая" ссылка>
[moved from beginners]
> Числа, где вначале 1-ки, а потом 0-й - это 2^x-2^y

какие числа? тира 1хххххх0 ?

> Вопрос: какой формулой можно расположить их в порядке
> возрастания? (имеется ввиду не маска, любое кол-во байт) =)
1




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


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