Решение обобщенной обратной задачи о днях рождения
Доказаны теоремы об асимптотическом поведении решения обобщенной обратной задачи о днях рождения. В теоремах даны асимптотически неулучшаемые оценки в случае неравновероятного и независимого размещения частиц по ячейкам для появления l ≥ 1 k-кратных совпадений. Полученный результат можно применять...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2012 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84292 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Решение обобщенной обратной задачи о днях рождения / П.А. Ендовицкий // Доп. НАН України. — 2012. — № 7. — С. 20-27. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859796171132764160 |
|---|---|
| author | Ендовицкий, П.А. |
| author_facet | Ендовицкий, П.А. |
| citation_txt | Решение обобщенной обратной задачи о днях рождения / П.А. Ендовицкий // Доп. НАН України. — 2012. — № 7. — С. 20-27. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Доказаны теоремы об асимптотическом поведении решения обобщенной обратной задачи о днях рождения. В теоремах даны асимптотически неулучшаемые оценки в случае
неравновероятного и независимого размещения частиц по ячейкам для появления l ≥ 1
k-кратных совпадений. Полученный результат можно применять в криптографии для
оценивания трудоемкости построения коллизий хэш-функций.
Доведено теореми про асимптотичну поведiнку розв’язку в узагальненiй задачi про днi народження. У теоремах наведенi асимптотично непокращувальнi оцiнки у випадку нерiвноймовiрного та незалежного розмiщення частинок по комiрках для появи l ≥ 1 k-кратних
збiгiв. Отриманий результат можна застосовувати в криптографiї для оцiнювання трудомiсткостi побудови колiзiй хеш-функцiй.
Theorems of the asymptotic behavior of the solution of a generalized inverse birthday problem are
proved. They give the asymptotically best possible estimates in the case of a nonuniform independent
arrangement of particles in cells for the appearance of l ≥ 1 k-fold coincidences. The result can be
applied to the evaluation of the laboriousness of a construction of collisions of the hash-functions
in cryptography.
|
| first_indexed | 2025-12-02T13:37:00Z |
| format | Article |
| fulltext |
УДК 519.2
© 2012
П.А. Ендовицкий
Решение обобщенной обратной задачи о днях рождения
(Представлено академиком НАН Украины И. Н. Коваленко)
Доказаны теоремы об асимптотическом поведении решения обобщенной обратной зада-
чи о днях рождения. В теоремах даны асимптотически неулучшаемые оценки в случае
неравновероятного и независимого размещения частиц по ячейкам для появления l > 1
k-кратных совпадений. Полученный результат можно применять в криптографии для
оценивания трудоемкости построения коллизий хэш-функций.
Задача о днях рождения является классической в теории вероятностей [1]. Задача состоит
в нахождении вероятности того, что по крайней мере двое человек из группы, состоящей
из n человек, n 6 365, родились в один день. При этом предполагается, что все 365 воз-
можных дней рождения равновероятны. Также “задачей о днях рождения” называют [2]
задачу нахождения минимального n такого, что в группе из n человек найдутся с вероят-
ностью не меньше чем заданное число p ∈ (0; 1) по крайней мере двое человек, которые
родились в один день.
Сформулируем обобщения обеих задач о днях рождения в терминах размещения частиц
по ячейкам.
Задача 1. Пусть n частиц независимо размещается в m ячейках (выше было m = 365).
Вероятности попадания каждой частицы в ячейки равны p1, . . . , pm,
m
∑
i=1
pi = 1 (выше было
p1 = · · · = p365 = 1/365). Чему равна вероятность Pk(n,m) того, что найдется по крайней
мере одна ячейка, содержащая не менее k частиц, k > 2 (выше было k = 2)?
Задачу 1 будем называть прямой задачей о днях рождения, так как в ней по задан-
ным параметрам m, n, k надо вычислить вероятность Pk(n,m). Обратной задачей о днях
рождения будем называть следующую задачу.
Задача 2. Рассматривается независимое заполнение m ячеек частицами. Вероятнос-
ти попадания каждой частицы в ячейки равны p1, . . . , pm,
m
∑
i=1
pi = 1. Также задано число
p ∈ (0; 1). Чему равно минимально необходимое число частиц n = n(m, p, k) такое, что
Pk(n,m) > p?
В задаче 2 по заданным параметрам m, k и значению вероятности p надо найти мини-
мальное число частиц n такое, чтобы при размещении n частиц в m ячейках вероятность
существования ячейки, содержащей k и более частиц, была не меньше p.
Заметим, что вероятность Pk(n,m) возрастает по n и при этом P (1) = · · · = P (k−1) = 0,
P (m(k − 1) + 1) = 1 (для упрощения записи иногда будем писать P (n) вместо Pk(n,m) и n
или n(m) вместо n(m, p, k), если это не вызывает неясности) и число частиц n = n(m) из
задачи 2 удовлетворяет неравенству
P (n− 1) < p 6 P (n). (1)
Например, если m = 365, p1 = · · · = pm = 1/365, k = 2, p = 1/2, то n(365) = 23, так как
в этом случае P (22) < 1/2 < P (23). Т. е. если считать, что каждый из 365 дней рождения
20 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №7
равновероятен, то в группе из 23 человек с вероятностью больше чем 1/2 найдутся по
крайней мере двое, которые родились в один день.
Прямая задача о днях рождения (задача 1) рассматривалась в статьях [2–5], обратная
(задача 2) — в [2, 6, 7] (см. также [8, 9]).
При решении прямой и обратной задач о днях рождения помогает следующая теоре-
ма [9].
Теорема 1. Пусть n частиц независимо и равновероятно размещаются в m ячейках.
Обозначим νk(n,m) — количество ячеек, содержащих k и более частиц, тут k > 2 —
фиксированное число. Тогда если nk/(k!mk−1) → λ > 0 при n, m → ∞, то νk(n,m) слабо
сходится к пуассоновской случайной величине с параметром λ > 0.
Из теоремы 1 получаем, что если nk/(k!mk−1) → λ > 0 при n,m → ∞, то
Pk(n,m) = P (νk(n,m) > 1) → 1− e−λ, n,m → ∞. (2)
Соотношение (2) дает “первое приближение” для решения прямой задачи о днях рождения
в равномерном случае, т. е. когда в задаче 1 p1 = · · · = pm = 1/m. Решение же прямой зада-
чи 1 требует получения числового интервала, в котором будет лежать вероятность Pk(n,m),
для чего надо, например, оценить скорость сходимости в предельном соотношении (2).
Но в данной работе будет рассматриваться не прямая задача 1, а обратная задача 2.
Из теоремы 1 следует теорема 2 об асимптотическом поведении минимально необходимого
числа частиц n(m) из задачи 2.
Теорема 2. Пусть в обратной задаче 2 p1 = · · · = pm = 1/m, т. е. рассматривается
равномерная схема. Тогда при фиксированных p ∈ (0; 1), k > 2 имеем
n(m) =
k
√
k!amk−1 + o(m(k−1)/k), m → ∞, (3)
где a = − ln(1 − p).
В случае k = 2 (т. е. когда ищется n(m) — минимальное число n частиц, необходимое
для того, чтобы при равновероятном и независимом размещении n частиц в m ячейках
с вероятностью не меньше чем p существовала ячейка, содержащая две или более частицы)
формула (3) принимает вид
n(m) =
√
2am+ o(
√
m), m → ∞,
где a = − ln(1 − p).
Целью настоящей работы является уточнение формулы (3), которая описывает асимпто-
тическое поведение минимально необходимого числа частиц n(m) из задачи 2 при m → ∞
и фиксированных p ∈ (0; 1) и k > 2.
При этом сначала формула (3) будет уточнена для равномерной схемы, а далее полу-
ченная уточненная формула будет распространена на некоторые полиномиальные схемы,
отличные от равномерной.
Сформулируем без доказательства соответствующую теорему для следующего варианта
полиномиальной схемы.
Теорема 3. Пусть задана некоторая неотрицательная, дважды дифференцируемая на
отрезке [0; 1] функция p(x) такая, что
1
∫
0
p(x) dx = 1. Рассматривается полиномиальная
схема {pi(m),m > 1, i = 1,m}, которая задается через функцию p(x) по формуле: ∀m > 1
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 21
∀ i = 1,m : pi(m) =
i/m
∫
(i−1)/m
p(x)dx (при p(x) ≡ 1 получается равномерная полиномиальная
схема).
Тогда минимальное число частиц n(m) из задачи 2 будет равняться
n(m) =
k−1
∑
i=0
Aim
i/k + θ(m), (4)
где последовательность {θ(m),m > 1} будет ограниченной и
lim θ(m) = 0, lim θ(m) = 1. (5)
Константы A0, A1, . . . , Ak−1 из (4) определяются следующим образом. Пусть a =
= − ln(1− p), b = k
√
k!a/Mk (смысл параметров p и k см. в формулировке задачи 2),
а числа Ml, l > 1, определяются по формуле
Ml =
1
∫
0
p(x)ldx, l > 1, (6)
тогда при i = 0, k − 1
Ai =
bk−i
k − i
(
∑
l1+2l2+···+(k−1)lk−1=k−1−i
(
−1 + i
k
)
l1+···+lk−1
l1! · · · lk−1!
Bl1
1 · · · · ·Blk−1
k−1
)
, (7)
где суммирование производится по всем решениям уравнения l1 + 2l2 + · · · + (k − 1)lk−1 =
= k − 1 − i, ls > 0, s = 1, k − 1.
Также обозначено (c)t = c(c − 1) · · · (c − t + 1), t ∈ N, c ∈ R, (c)0 = 1, а константы
B1, . . . , Bk−1, в свою очередь, равны
Bs =
(−1)s
s!
Mk+s
Mk
k
k + s
, s = 1, k − 2,
Bk−1 =
(−1)k−1
(k − 1)!
M2k−1
Mk
k
2k − 1
+
k
2
Mk
(k − 1)!
− Mk
2(k − 2)!
1
a
.
(8)
Формула (4) и является уточнением формулы (3).
Замечание 1. Условие (5) позволяет строить хорошие приближения для искомого числа
частиц n(m), так как в левой части формулы (4) стоит целое число n(m), а отрезок
[
k−1
∑
i=0
Aim
i
k + lim θ(m);
k−1
∑
i=0
Aim
i
k + lim θ(m)
)
=
[
k−1
∑
i=0
Aim
i
k ;
k−1
∑
i=0
Aim
i
k + 1
)
содержит ровно одну целую точку, которую можно рассматривать как приближение для
n(m).
П р и м е р 1 . Приведем асимптотическую формулу для n(m) из теоремы 3 в случае k = 2,
т. е. для минимального числа частиц n(m), которые надо разместить в m ячейках, чтобы с вероят-
ностью не меньше чем p ∈ (0; 1) существовала ячейка, содержащая по крайней мере две частицы.
22 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №7
В этом случае, при k = 2 из (4) имеем
n(m) = A1
√
m+A0 + θ(m),
где lim θ(m) = 0, lim θ(m) = 1, а константы A0 и A1 определяются следующим образом.
Пусть a = − ln(1 − p), b =
√
2a/M2, определение чисел Ml, l > 1, см. в формуле (6). Тогда по
формуле (8) рассчитываем константу B1:
B1 = −2
3
M3
M2
+M2 −
M2
2a
,
и теперь из формулы (7) получаем значения A0 и A1:
A1 =
b1
1
∑
l1=0
(−1/2)l1
l1!
Bl1
1 = b =
√
2a
M2
,
A0 =
b2
2
∑
l1=1
(−1)l1
l1!
Bl1
1 = −b2
2
B1 = a
(
2
3
M3
M2
2
− 1
)
+
1
2
.
Отсюда получаем выражение для n(m) в случае k = 2:
n(m) =
√
2a
M2
m+ a
(
2
3
M3
M2
2
− 1
)
+
1
2
+ θ(m). (9)
В равномерном случае, когда Ml = 1, l > 1, формула (9) принимает вид
n(m) =
√
2am− a
3
+
1
2
+ θ(m), (10)
где a = − ln(1 − p), limθ(m) = 0, lim θ(m) = 1.
Формула (10) получена в [10].
П р и м е р 2 . Получим аналогичную формулу для n(m) в случае k = 3. Она будет иметь вид
n(m) = A2m
2/3 +A1m
1/3 +A0 + θ(m),
где lim θ(m) = 0, lim θ(m) = 1, а константы A0, A1, A2 определяются следующим образом. Пусть
a = − ln(1 − p), b = 3
√
6a/M3. Рассчитываем по формулам (8) константы B1, B2:
B1 = −3
4
M4
M3
, B2 =
3
10
M5
M3
+
3
4
M3 −
M3
2a
,
и теперь по формулам (7) получаем значения A0, A1, A2:
A2 =
b1
1
∑
l1+2l2=0
(−1/3)l1+l2
l1!l2!
Bl1
1 Bl2
2 = b,
A1 =
b2
2
∑
l1+2l2=1
(−2/3)l1+l2
l1!l2!
Bl1
1 Bl2
2 =
b2
2
(−(2/3)B1) =
M4
4M3
b2,
A0 =
b3
3
∑
l1+2l2=2
(−1)l1+l2
l1!l2!
Bl1
1 Bl2
2 =
2a
M3
(B2
1 −B2) = a
(
9
8
M2
4
M3
3
− 3
5
M5
M3
− 3
2
)
+ 1.
Отсюда получаем выражение для n(m) в случае k = 3:
n(m) = bm2/3 +
M4
4M3
b2m1/3 + a
(
9
8
M2
4
M3
3
− 3
5
M5
M3
− 3
2
)
+ 1 + θ(m), (11)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 23
где a = − ln(1 − p), b = 3
√
6a/M3, lim θ(m) = 0, lim θ(m) = 1. В равномерном случае, когда Ml = 1,
l > 1, формула (11) принимает вид
n(m) = bm2/3 +
b2
4
m1/3 − 39
40
a+ 1 + θ(m), (12)
где a = − ln(1 − p), b =
3
√
6a, lim θ(m) = 0, lim θ(m) = 1.
П р и м е р 3 . Приведем также формулу для n(m) в случае k = 4 (способ ее получения такой же,
как и для случаев k = 2 и k = 3):
n(m) = bm3/4 +
M5
5M4
b2m2/4 +
(
7
50
M2
5
M2
4
− 1
12
M6
M4
)
b3m1/4+
+ a
(
384
125
M3
5
M4
4
− 16
5
M5M6
M3
4
+
12
21
M7
M2
4
− 2
)
+
3
2
+ θ(m), (13)
где a = − ln(1 − p), b = 4
√
24a/M4, lim θ(m) = 0, lim θ(m) = 1. В равномерном случае, когда Ml = 1,
l > 1, формула (13) принимает вид
n(m) = bm3/4 +
b2
5
m2/4 +
17
300
b3m1/4 − 4086
2625
a+
3
2
+ θ(m), (14)
где a = − ln(1 − p), b =
3
√
24a, lim θ(m) = 0, lim θ(m) = 1.
Если m = 365, p = 1/2, то (при равновероятном размещении частиц) из формул (10), (12), (14)
получаем следующие значения для минимально необходимого числа частиц n(m) в случаях k = 2,
k = 3, k = 4 соответственно:
n(365) = 23, n(365) = 88, n(365) = 187, (15)
т. е. в группе из 187 человек с вероятностью больше, чем 1/2 найдутся 4 человека, родившиеся в один
день [2]. Т. е. значения (15), полученные из асимптотических формул (10), (12), (14), совпадают
с точными значениями, найденными в [2] (только для этих трех случаев) компьютерным перебором.
Обобщением задач 1 и 2 являются задачи 3 и 4.
Задача 3. Пусть n частиц независимо размещается в m ячейках. Вероятности попа-
дания каждой частицы в ячейки равны p1, . . . , pm,
m
∑
i=1
pi = 1. Чему равна вероятность
Pk(n,m, l) того, что найдется по крайней мере l ячеек, l > 1, содержащих не менее k
частиц, k > 2?
Задача 4. Рассматривается независимое заполнение m ячеек частицами. Вероятнос-
ти попадания каждой частицы в ячейки равны p1, . . . , pm,
m
∑
i=1
pi = 1. Также задано чис-
ло p ∈ (0; 1). Чему равно минимально необходимое число частиц n = nl(m) такое, что
Pk(n,m, l) > p?
Очевидно, что при l = 1 в задачах 3 и 4 получаем задачи 1 и 2.
В данном случае из теоремы 1 будет следовать, что если в равномерной схеме
nk
k!mk−1
→
→ λ > 0, то
Pk(n,m, l) = P (νk(n,m) > l) → 1− e−λ
l−1
∑
t=0
λt
t!
, n,m → ∞,
и отсюда для минимального числа частиц nl(m) из задачи 4 будет справедливо представ-
ление
nl(m) =
k
√
k!almk−1 + o(m(k−1)/k), m → ∞, (16)
24 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №7
где
al = hl(1− p), l > 1, (17)
а функция hl(x) : (0; 1) → (0;+∞) убывает и определяется своей обратной функцией h−1
l (x):
h−1
l (x) = e−x
l−1
∑
t=0
xt/t!, x > 0.
Формула (16), как и формула (3), также может быть уточнена. А именно, справедлива
следующая теорема.
Теорема 4. Пусть для произвольных фиксированных k > 2 и l > 1 выполнены условия
теоремы 3, тогда
nl(m) =
k−1
∑
i=0
Aim
i/k +
k(l − 1)
2
+ θ(m), (18)
где последовательность {θ(m),m > 1} ограничена и lim θ(m) = 0, lim θ(m) = 1. Константы
Ai, i = 0, k − 1, из (18) определяются так же, как и константы Ai, i = 0, k − 1, из (4)
в теореме 3. Только везде вместо значения a = − ln(1− p) в формуле (4) тут надо брать
значение al = hl(1 − p) из формулы (17).
Замечание 2. Отметим, что в свободном члене в формуле (18) появляется слагаемое
k(l − 1)/2, которого нет в формуле (4), т. е. когда l = 1.
П р и м е р 4 . Пусть k = 2. Приведем асимптотические формулы для n1(m), n2(m) и n3(m) — ми-
нимального количества частиц, которое необходимо разместить в m ячейках, чтобы с вероятностью
не меньше чем p ∈ (0; 1) существовали по крайней мере соответственно 1, 2, 3 ячейки, содержащие
две частицы и более. Имеем
n1(m) =
√
2a1
M2
m+ a1
(
2
3
M3
M2
2
− 1
)
+
1
2
+ θ1(m),
n2(m) =
√
2a2
M2
m+ a2
(
2
3
M3
M2
2
− 1
)
+
3
2
+ θ2(m),
n3(m) =
√
2a3
M2
m+ a3
(
2
3
M3
M2
2
− 1
)
+
5
2
+ θ3(m),
тут limθi(m) = 0, limθi(m) = 1, i = 1, 3, числа ai = ai(p), i = 1, 3, определяются по формуле (17),
а числа Ml, l > 1, определены в формуле (6).
П р и м е р 5 . Используя уточненные формулы (4) и (18) из теорем 3 и 4, построим таблицу
значений nl(m) в равномерной схеме размещения частиц при m = 365, p = 1/2, для значений
k = 2, 4 и l = 1, 5 (смысл параметров см. в формулировке задач 3 и 4):
k
l
1 2 3 4 5
2 23 36 46 55 62
3 88 120 142 160 175
4 187 240 274 301 323
т. е. чтобы в группе из n человек нашлась с вероятностью не меньше чем 1/2 по крайней мере одна
тройка, где все трое родились в один день, достаточно взять n = 88; для того чтобы с вероятностью
не меньше чем 1/2 нашлись по крайней мере две тройки, в каждой из которых все трое родились
в один день, достаточно взять n = 120 и т. д.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 25
Являются ли значения в таблице решениями задачи 4? Т. е. удовлетворяют ли они не-
равенству (1)? Ведь эти значения получены при подстановке числовых значений в асим-
птотические формулы (4) и (18) и про значение величины θ(365) теоремы 3 и 4 ничего не
говорят. Известно лишь, что
lim θ(m) = 0, lim θ(m) = 1,
а значения в таблице были получены в предположении, что 0 < θ(365) < 1.
Ответить на последний вопрос можно, решав прямую задачу о днях рождения (зада-
чи 1 и 3) для значений, указанных в таблице и соседних к ним. Из условия (5) следу-
ет, что для достаточно больших m значения n(m), полученные по асимптотическим фор-
мулам (4) и (18), будут либо совпадать с точными решениями задачи 4, либо отлича-
ться от них на 1. Но, как показывают числовые расчеты [2], уже при m = 365 первый
столбец в таблице, полученный по асимптотическим формулам, совпадает с точным ре-
шением.
С помощью полученных формул (4) и (18) можно рассчитывать трудоемкость построе-
ния многократных коллизий хэш-функций в криптографии, критические области при про-
верке статистических гипотез и др.
1. Feller W. An introduction to probability theory and its applications. – New York: Wiley, 1958. –
411 p.
2. McKinney E.H. Generalized birthday problem // Amer. Math. Monthly. – 1966. – 73. – P. 385–387.
3. Levin B. A representation for multinomial cumulative distribution functions // Ann. Stat. – 1981. – 9. –
P. 1123–1126.
4. Nunnikhoven T. A birthday problem solution for nonuniform birth frequencies // Amer. Statist. – 1992. –
46. – P. 601–606.
5. Sayrafiezadeh M. The birthday problem revisited // Math. Mag. – 1994. – 64. – P. 220–223.
6. Heuer G.A. Estimation of a certain probability problem // Amer. Math. Monthly. – 1959. – 66. –
P. 704–706.
7. Mathis F. A generalized birthday problem // SIAM Rev. – 1991. – 33. – P. 265–270.
8. DasGupta A. The matching, birthday and strong birthday problem: a contemporary review // J. Statist.
Planning and Inference. – 2005. – 130. – P. 377–389.
9. Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. – Москва: Наука, 1976. –
224 с.
10. Ендовицкий П.А. Уточнение асимптотической аппроксимации размера группы в парадоксе дней рож-
дений // Кибернетика и систем. анализ. – 2010. – 3. – С. 185–188.
Поступило в редакцию 24.10.2011НТУ Украины “Киевский политехнический институт”
П.О. Єндовицький
Розв’язок узагальненої оберненої задачi про днi народження
Доведено теореми про асимптотичну поведiнку розв’язку в узагальненiй задачi про днi на-
родження. У теоремах наведенi асимптотично непокращувальнi оцiнки у випадку нерiвно-
ймовiрного та незалежного розмiщення частинок по комiрках для появи l > 1 k-кратних
збiгiв. Отриманий результат можна застосовувати в криптографiї для оцiнювання тру-
домiсткостi побудови колiзiй хеш-функцiй.
26 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №7
P.A. Yendovitskij
The solution of a generalized inverse birthday problem
Theorems of the asymptotic behavior of the solution of a generalized inverse birthday problem are
proved. They give the asymptotically best possible estimates in the case of a nonuniform independent
arrangement of particles in cells for the appearance of l > 1 k-fold coincidences. The result can be
applied to the evaluation of the laboriousness of a construction of collisions of the hash-functions
in cryptography.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №7 27
|
| id | nasplib_isofts_kiev_ua-123456789-84292 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-02T13:37:00Z |
| publishDate | 2012 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Ендовицкий, П.А. 2015-07-06T08:34:13Z 2015-07-06T08:34:13Z 2012 Решение обобщенной обратной задачи о днях рождения / П.А. Ендовицкий // Доп. НАН України. — 2012. — № 7. — С. 20-27. — Бібліогр.: 10 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/84292 519.2 Доказаны теоремы об асимптотическом поведении решения обобщенной обратной задачи о днях рождения. В теоремах даны асимптотически неулучшаемые оценки в случае неравновероятного и независимого размещения частиц по ячейкам для появления l ≥ 1 k-кратных совпадений. Полученный результат можно применять в криптографии для оценивания трудоемкости построения коллизий хэш-функций. Доведено теореми про асимптотичну поведiнку розв’язку в узагальненiй задачi про днi народження. У теоремах наведенi асимптотично непокращувальнi оцiнки у випадку нерiвноймовiрного та незалежного розмiщення частинок по комiрках для появи l ≥ 1 k-кратних збiгiв. Отриманий результат можна застосовувати в криптографiї для оцiнювання трудомiсткостi побудови колiзiй хеш-функцiй. Theorems of the asymptotic behavior of the solution of a generalized inverse birthday problem are proved. They give the asymptotically best possible estimates in the case of a nonuniform independent arrangement of particles in cells for the appearance of l ≥ 1 k-fold coincidences. The result can be applied to the evaluation of the laboriousness of a construction of collisions of the hash-functions in cryptography. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Решение обобщенной обратной задачи о днях рождения Розв’язок узагальненої оберненої задачi про днi народження The solution of a generalized inverse birthday problem Article published earlier |
| spellingShingle | Решение обобщенной обратной задачи о днях рождения Ендовицкий, П.А. Математика |
| title | Решение обобщенной обратной задачи о днях рождения |
| title_alt | Розв’язок узагальненої оберненої задачi про днi народження The solution of a generalized inverse birthday problem |
| title_full | Решение обобщенной обратной задачи о днях рождения |
| title_fullStr | Решение обобщенной обратной задачи о днях рождения |
| title_full_unstemmed | Решение обобщенной обратной задачи о днях рождения |
| title_short | Решение обобщенной обратной задачи о днях рождения |
| title_sort | решение обобщенной обратной задачи о днях рождения |
| topic | Математика |
| topic_facet | Математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84292 |
| work_keys_str_mv | AT endovickiipa rešenieobobŝennoiobratnoizadačiodnâhroždeniâ AT endovickiipa rozvâzokuzagalʹnenoíobernenoízadačiprodninarodžennâ AT endovickiipa thesolutionofageneralizedinversebirthdayproblem |