Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений
Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 1 наведено асимптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення частинок по чарунках. В теоремі 2 наведено асипмптотично непокращувальні оцінки для...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45210 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений / П.А. Ендовицкий // Кибернетика и системный анализ. — 2010. — № 3. — С. 185-188. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860138661707776000 |
|---|---|
| author | Ендовицкий, П.А. |
| author_facet | Ендовицкий, П.А. |
| citation_txt | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений / П.А. Ендовицкий // Кибернетика и системный анализ. — 2010. — № 3. — С. 185-188. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 1 наведено асимптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення частинок по чарунках. В теоремі 2 наведено асипмптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення двох однакових комплектів частинок по чарунках. Отримані результати можна застосувати у криптографії для оцінювання трудомісткості побудови колізій хеш-функцій.
Proved two theorems about asymptotic behavior group size in birthday paradox. Theorem 1 gives asymptotically best possible estimates for group size in case uniform and independent particle occupancy in cells. Theorem 2 gives asymptotically best possible estimates for group size in case uniform and independent occupancy of two equal sets of particles in cells. These results one may apply in cryptography for estimation working time for construction collisions of hash-functions.
|
| first_indexed | 2025-12-07T17:47:50Z |
| format | Article |
| fulltext |
ÓÄÊ 519.2
Ï.À. ÅÍÄÎÂÈÖÊÈÉ
ÓÒÎ×ÍÅÍÈÅ ÀÑÈÌÏÒÎÒÈ×ÅÑÊÎÉ ÀÏÏÐÎÊÑÈÌÀÖÈÈ
ÐÀÇÌÅÐÀ ÃÐÓÏÏÛ Â ÏÀÐÀÄÎÊÑÅ ÄÍÅÉ ÐÎÆÄÅÍÈÉ
Êëþ÷åâûå ñëîâà: ñëó÷àéíîå ðàçìåùåíèå, ïàðàäîêñ äíåé ðîæäåíèé, àñèìïòîòè÷åñêèå íå-
ðàâåíñòâà, ôîðìóëà Ñòèðëèíãà äëÿ ãàììà-ôóíêöèè, ìåòîä êîëëèçèé äëÿ õýø-ôóíêöèé.
Ïàðàäîêñ äíåé ðîæäåíèé ñîñòîèò â ñëåäóþùåì [1, 2]. Ïóñòü ñóùåñòâóåò ãðóïïà èç n ëþ-
äåé (n � 365 ). Áóäåì ñ÷èòàòü, ÷òî äåíü ðîæäåíèÿ êàæäîãî ÷åëîâåêà èç ãðóïïû ïðèõîäèòñÿ
ñ ðàâíîé âåðîÿòíîñòüþ íà îäèí èç 365 äíåé. Òîãäà âåðîÿòíîñòü òîãî, ÷òî â ãðóïïå íàé-
äóòñÿ õîòÿ áû äâà ÷åëîâåêà, äíè ðîæäåíèé êîòîðûõ ñîâïàäàþò, ðàâíà
P n
nn
n n
( )
( ) ( )
� � � �
� � � � �
1
365
365
1
365 364 365 1
365
�
.
Ðàçìåð ãðóïïû, ãäå ñ âåðîÿòíîñòüþ p � 1 íàéäóòñÿ ïî êðàéíåé ìåðå äâà ÷åëîâåêà ñ ñîâ-
ïàäàþùèìè äíÿìè ðîæäåíèÿ, ðàâåí 366, à äëÿ p � 1 îí ãîðàçäî ìåíüøå: P( ) , ...23 0 507� ,
P( ) , ...57 0 990� è ò.ä. (ò.å. â ãðóïïå èç 23 ÷åëîâåê ñ âåðîÿòíîñòüþ, áîëüøåé
1
2
, íàéäóòñÿ äâà
÷åëîâåêà ñ ñîâïàäàþùèìè äíÿìè ðîæäåíèÿ). Ïàðàäîêñ ñîñòîèò â êàæóùåìñÿ ïðîòèâîðå÷èè ñ
ìàëûì ðàçìåðîì ãðóïïû ïðè çàäàííîì p � ( ; )0 1 . Ïîäðîáíåå ñì. â [2].
Îöåíêè âåðîÿòíîñòåé è ðàçìåðà ãðóïïû â çàäà÷å î äíÿõ ðîæäåíèÿ èìåþò âàæíûå ïðè-
ìåíåíèÿ ïðè àóòåíòèôèêàöèè, ïîñòðîåíèè õýø-ôóíêöèé, â êîäèðîâàíèè, â êðèïòîàíàëèçå,
ïðè ðåøåíèè ñèñòåì óðàâíåíèé íàä êîíå÷íûìè àëãåáðàè÷åñêèìè ñòðóêòóðàìè.
1. Ñôîðìóëèðóåì çàäà÷ó î ðàçìåðå ãðóïïû â ïàðàäîêñå äíåé ðîæäåíèé â îáùåì ñëó÷àå
(â òåðìèíàõ ðàçìåùåíèÿ ÷àñòèö ïî ÿ÷åéêàì). Ïóñòü çàäàíû ÷èñëà m N� , p � ( ; )0 1 , m — ÷èñ-
ëî ÿ÷ååê, â ïàðàäîêñå m � 365. Ïóñòü òàêæå P nm( ) — âåðîÿòíîñòü, ÷òî ïðè ðàçìåùåíèè n ÷àñ-
òèö ïî m ÿ÷åéêàì ïî êðàéíåé ìåðå äâå ÷àñòèöû ïîïàäóò â îäíó ÿ÷åéêó (ñ÷èòàåì, ÷òî êàæäàÿ
÷àñòèöà ðàçìåùàåòñÿ íåçàâèñèìî îò äðóãèõ è ðàâíîâåðîÿòíî ïî m ÿ÷åéêàì):
P n
m
m
m m m n
m
Q n n mm
n
n n m( )
( ) ( ) ( )
( ), ,� � � �
� � � � � �
� �1 1
1 1
1 0
�
� 1, (1)
ãäå Q n P nm m( ) ( )� �1 — âåðîÿòíîñòü, ÷òî âñå ÷àñòèöû ïîïàäóò â ðàçíûå ÿ÷åéêè, òîãäà
P n( )
âîçðàñòàåò ïî n ïðè ôèêñèðîâàííîì m, P P( ) ( )0 1 0� � , P m( )� �1 1 (äëÿ óïðîùåíèÿ
çàïèñè âìåñòî P nm( ) áóäåì ïèñàòü P n( )).
Îïðåäåëèì íàòóðàëüíîå ÷èñëî n n m m� � �( ) [ ; ]1 1 , êîòîðîå çàâèñèò îò m è p, èç ñëåäó-
þùåãî óñëîâèÿ:
P n p P n( ) ( )� � �1 , (2)
ò.å. n m( ) — ìèíèìàëüíîå ÷èñëî n ÷àñòèö òàêîå, ÷òî ïðè ðàçìåùåíèè n ÷àñòèö â m
ÿ÷åéêàõ âåðîÿòíîñòü ïîïàäàíèÿ ïî êðàéíåé ìåðå äâóõ ÷àñòèö â îäíó ÿ÷åéêó íå ìåíü-
øå p. Íàïðèìåð, åñëè p �
1
2
, m � 365, òî n( )365 23� , òàê êàê P P( ) ( )22
1
2
23� � .
Ðàññìîòðèì âîïðîñ îá àñèìïòîòè÷åñêîì ïîâåäåíèè n m( ) . Õîðîøî èçâåñòåí ñëåäóþ-
ùèé ðåçóëüòàò (ñì., íàïðèìåð, [2]):
n m am o m( ) ( )� �2 , m � � ,
ãäå a p� � �
ln ( )1 0 .
Öåëü äàííîé ñòàòüè — äîêàçàòü òåîðåìó 1, êîòîðàÿ ñóùåñòâåííî óñèëèâàåò ýòîò ðå-
çóëüòàò.
Òåîðåìà 1. Ïóñòü p � ( ; )0 1 ôèêñèðîâàíî, a p� � �ln ( )1 , òîãäà n m( ) � �2am m� ( ) ,
ãäå ïîñëåäîâàòåëüíîñòü { }� ( ),m m � 1 îãðàíè÷åíà è lim ( )
m
m
��
� � �
1
2 3
a
, lim ( )
m
m
a
��
� ��
3
2 3
.
Äîêàçàòåëüñòâî. Äëÿ òîãî ÷òîáû âîñïîëüçîâàòüñÿ èçâåñòíûìè ðåçóëüòàòàìè î ñâîéñò-
âàõ ãàììà-ôóíêöèè �( )x [3], áóäåì ñ÷èòàòü, ÷òî ÷èñëà n, m èç (1) ìîãóò ìåíÿòüñÿ íåïðåðûâ-
íî. Ïóñòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 185
© Ï.À. Åíäîâèöêèé, 2010
Q x
y
y x y
y x yy x
( )
( )
( )
, ,�
�
� �
� � �
�
�
1
1
0 0 1. (3)
Î÷åâèäíî, ÷òî ïðè íàòóðàëüíûõ x , y â (3) ïîëó÷àåì Q nm( ) èç ôîðìóëû (1).
Îïðåäåëèì õàðàêòåð ìîíîòîííîñòè Q xy ( ) ïðè ôèêñèðîâàííîì y
Q x
y
y x y
t y x
t y
y
t y
y x y
( )
( )
( )
( )
( )
�
�
� �
�
� � �
� � �
�
��
�
�
�
1
1
1
0 1
1
� � �
�
�
1 1
1
t y
y
f t y
�( )
( )
,
ãäå
f t
t
y y
u e du e d
t t
t u t y( )
( )
� � �� �
�
� �
�
� �
� 1 1
0
1
0
� �� .
Ïðè ýòîì f t e dt y' ( ) ln� �
�
� � � �� �1
0
, �
f t( ) , òàê êàê �� �
�
� �
�f t e dt y( ) ln
0
1 2 0� � �� , äèôôå-
ðåíöèðîâàíèå ïîä çíàêîì èíòåãðàëà âîçìîæíî ïî ïðèçíàêó Ëåéáíèöà [3], òàêæå
f y
y
y
y
y
f y
y y
( )
( ) ( )
( )� �
�
� �
�
� � 1
1
1
, ò.å. ïî òåîðåìå Ðîëëÿ � � � �y y y f y0 01 0( , ) : ( )' .
Îòñþäà è èç âîçðàñòàíèÿ f t' ( ) ñëåäóåò, ÷òî f t( ) ïðè t y� ( ; ]0 0 óáûâàåò è ïðè
t y y� �( ; ]0 1 âîçðàñòàåò. Îòñþäà � �z0 0 1( , ) òàêîå, ÷òî Qy ( )� ïðè x z�[ ; ]0 0 âîçðàñòàåò è ïðè
x z y� �[ ; ]0 1 óáûâàåò, ò.å. Qy ( )� óáûâàåò ïðè x y� �[ ; ]1 1 (òàê êàê z0 1� ), íî Qy ( )1 1� ,
Q yy ( )� � �1 0 0 . Çíà÷èò, ââèäó íåïðåðûâíîñòè Qy ( )� äëÿ çàäàííîãî p � ( ; )0 1
� � �! ( ) ( ; )x y y1 1 òàêîå, ÷òî Q x y py ( ( )) � �1 .
Ôóíêöèÿ x y( ) åñòü íåïðåðûâíîå ðàñïðîñòðàíåíèå ïîñëåäîâàòåëüíîñòè {n m m( ), }� 1 èç
(2) äëÿ äåéñòâèòåëüíûõ x y,
0 .
Èññëåäóåì àñèìïòîòè÷åñêîå ïîâåäåíèå x y( ) ïðè y� � � (ýòî â äàëüíåéøåì äàñò âîç-
ìîæíîñòü îïðåäåëèòü àñèìïòîòè÷åñêîå ïîâåäåíèå n m( ) , m � 1). Äëÿ ýòîãî äîêàæåì òðè ëåì-
ìû è ââåäåì îáîçíà÷åíèå x y x y1 1( ) ( )� � äëÿ óïðîùåíèÿ çàïèñè íåêîòîðûõ ôîðìóë.
Ëåììà 1. Ôóíêöèÿ x y( ) � � � ïðè y� � � .
Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî x y( ) âîçðàñòàåò. Äëÿ ýòîãî äîñòàòî÷íî óáåäèòüñÿ, ÷òî
�
b 0 ôóíêöèÿ g y
y
y b yb
( )
( )
( )
�
�
�
�
âîçðàñòàåò ïðè y b
. Ïîêàæåì, ÷òî [ln ( )]g y '
0 , ò.å.
ln ( )g y âîçðàñòàåò
[ln ( )] [ln ( ) ln ( ) ln ]
( )
( )
(
g y y y b b y
y
y
y b
' '� � � � �
�
�
� �
� �
�
�
� )
( )� y b
b
y�
� ,
íî
�
� � � � �
�
�
�
�
�
�
�
�
�
�
�
�
( )
( )
a
a a
C
n n an
1 1 1
1
, ãäå C — êîíñòàíòà Ýéëåðà [3].
Îòñþäà
[ln ( )]g y
y y b
b
y n n y n n y b
' � � �
�
� � �
�
�
�
��
�
�
�� � �
� �
�
�
�
1 1 1 1 1 1
�
�
�
�� �
�
�
�
�
��
nn 11
�
� � �
�
��
�
�
b
n c n b c
b
b cn ( )( )0
,
ãäå c y b� �
0 . Íî
b
n c n b c
b
dx
x c x b c
b
c
b
c
b
c
( )( ) ( )( )
ln
� � �
� � �
� �
�
�
�
�
�
�
�
1
10
�
�
�
�� �
�n
b
b c0
,
ïîñêîëüêó ln ( )1
1
�
�
t
t
t
ïðè t
0 . Îòñþäà [ln ( )]g y '
0 , ò.å. g y( ) è x y( ) âîçðàñòàþò.
Åñëè òåïåðü lim ( )
y
x y M R
���
� � , òî äëÿ N M� �[ ] 1 èìååì x y N( ) � �
y 0 , ò.å.
1
1
1
1
� � �
�
�
�
�
� �
p Q x
y
y x y
y
y N y
y y N
y x N
( )
( )
( )
( )
( )
( ) ... (�
�
�
�
)
yN
� 1, y� � � .
Ïîëó÷èëè ïðîòèâîðå÷èå, ò.å. lim ( )
y
x y
���
� � � .
Ëåììà äîêàçàíà.
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Ëåììà 2. Ôóíêöèÿ
x y
y
( )
� 0 ïðè y� � � .
Äîêàçàòåëüñòâî. Åñëè lim
( )
y
x y
y���
0 , òî �
� 0 �
M 0 �
y M x y y: ( )1 � .
 ýòîì ñëó÷àå
Q x
y
y x y
y
y y
Q yy x y y( )
( )
( )
( )
( )
( )�
�
� �
�
�
�
�1
1 �
�
�
, � �� �1 .
Ïîêàæåì, ÷òî Q yy ( )� � 0 ïðè y� � � . Ïî ôîðìóëå Ñòèðëèíãà äëÿ �-ôóíêöèè [3] èìååì:
� � � � � � � �ln ( ) ln
( )
( )
ln ( ) ln ( ) lnQ y
y
y y
y y y yy y
�
�
� �
�
�
�
� �
� � �
�
�
�
�
�
� � � �
�
�
�
�
�
� � � � �y y y y y y y y o
1
2
1
2
1ln ln ln ( )� � � �
� � � � � � � �y o( ln ) ln ( )1
1
2
1� � � � , y� � � ,
òàê êàê 1 0� �
� � �ln ïðè � � ( ; )0 1 . Îòñþäà 1 0� � � �p Q x Q yy y( ) ( )� , y� �� .
Ïîëó÷èëè ïðîòèâîðå÷èå, ò.å. lim
( )
y
x y
y���
� 0 .
Ëåììà äîêàçàíà.
Ëåììà 3. Ôóíêöèÿ x y a y
a
o( ) ( )� � � �2
1
2 3
1 ïðè y� � � .
Äîêàçàòåëüñòâî. Ïóñòü a p� � �
ln( )1 0 , òîãäà ïî ôîðìóëå Ñòèðëèíãà äëÿ �-ôóíêöèè
èìååì
a Q x y y x x yy� � � � � � � �ln ( ) ln ( ) ln ( ) ln� � 1 1
� � �
�
� �
�
� �
�
�( )ln ln
( )
y x
y
y x
x
y
y x y y x
1
1
1
1
1 2
1
1
2 12 12
� �
� �
�
� �
�
�
�
�
�
� � � � �x
u
u
u u
u
x
u
1
1
1
21
1
1
1
2
1
12 1
ln ( )
ln ( ) ln ( )
� �
2 11x u( )�
,
ãäå u u y
x y
y
� � �( )
( )1 0 , y� � � , � �1 2 0 1, ( ; )� .
Îòñþäà
x y
a
u y
a
o( )
( )
( )� � �
�
�
�
�
�
� �
2
2
1
2 3
1 y� � � ,
è, ñëåäîâàòåëüíî,
x y a y
a
o( ) ( )� � � �2
1
2 3
1 , y� � � .
Ëåììà äîêàçàíà.
Òåïåðü çàêîí÷èì äîêàçàòåëüñòâî òåîðåìû 1. Èç ëåììû 3 èìååì, ÷òî
x m( ) � � � , m � � � ,
x m x m( ) ( )� � �1 0 , m � � � ,
îòñþäà ñëåäóåò, ÷òî äðîáíûå ÷àñòè { }x m( ) , m N� , âñþäó ïëîòíû â [ ; ]0 1 .
Èç óñëîâèÿ (2) òàêæå ñëåäóåò, ÷òî n m x m n m( ) ( ) ( )� � �1 . Îòñþäà è èç ëåììû 3 ïîëó-
÷èì, ÷òî äëÿ � ( ) ( )m n m am� � 2 áóäåò âûïîëíÿòüñÿ { ( ), } ;� m m
a a
� � � �
�
��
�
�
1
1
2 3
3
2 3
(÷åðòà
íàä ìíîæåñòâîì îçíà÷àåò çàìûêàíèå).
 ÷àñòíîñòè, lim ( )
m
m
a
��
� ��
1
2 3
, lim ( )
m
m
a
��
� ��
3
2 3
.
Òåîðåìà äîêàçàíà.
Òåîðåìà 1 äàåò àñèìïòîòè÷åñêè òî÷íîå âûðàæåíèå äëÿ n m( ) , òàê êàê
lim ( ) lim ( )� �m m� � 1, ò.å. îòðåçîê �
�
� � �
�
�
�� ��
2 2am m am m
m m
lim ( ); lim ( )� � ñîäåðæèò íå áîëåå
÷åì îäíó öåëóþ òî÷êó n m
0
( ) , êîòîðóþ ìîæíî ðàññìàòðèâàòü êàê ïðèáëèæåíèå äëÿ n m( ) ïðè
áîëüøèõ m .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 187
Ïðèìåð. Åñëè m � 264, p �
1
2
, òî n m0 5056937541( ) � , ïðè ýòîì
P n( ) , ...0 0 500000000006094� ,
P n( ) , ...0 1 0 499999999869026� � .
2. Ðàññìîòðèì ñëåäóþùèé âàðèàíò ïàðàäîêñà äíåé ðîæäåíèé [1]: â m ÿ÷åéêàõ íåçàâèñè-
ìî ðàçìåùàåòñÿ äâå ãðóïïû ïî n ÷àñòèö, ïðè÷åì â êàæäîé ãðóïïå ÷àñòèöû ïîïàäàþò â ðàçëè÷-
íûå ÿ÷åéêè è âñå Cm
n âîçìîæíûõ ðàçìåùåíèé îäíîé ãðóïïû ðàâíîâåðîÿòíû. Ïóñòü R nm( ) —
âåðîÿòíîñòü òîãî, ÷òî ïðè ðàçìåùåíèè äâóõ ãðóïï ïî n ÷àñòèö ïî m ÿ÷åéêàì õîòÿ áû äâå ÷àñ-
òèöû èç ðàçíûõ ãðóïï ïîïàäóò â îäíó ÿ÷åéêó:
R n
C
C
m n
m m n
S nm
m n
n
m
n m( )
( )!
!( )!
( )� � � �
�
�
��1 1
2
1
2
, n k k
m
� �
�
��
�
�
0
2
, , ,
ãäå S n R nm m( ) ( )� �1 — âåðîÿòíîñòü, ÷òî âñå ÷àñòèöû ïîïàäóò â ðàçíûå ÿ÷åéêè. Ïðè
n
m
�
��
�
� 2
èìååì R nm( ) � 1.
Ïóñòü çàäàíî ÷èñëî p � ( ; )0 1 , îïðåäåëèì íàòóðàëüíîå ÷èñëî n n m k� � �( ) [ ; ]1 1 , êîòî-
ðîå çàâèñèò îò m è p , èç óñëîâèÿ R n p R n( ) ( )� � �1 , ò.å. n m( ) — ìèíèìàëüíîå ÷èñëî n ÷àñòèö
òàêîå, ÷òî ïðè ðàçìåùåíèè äâóõ ãðóïï ïî n ÷àñòèö â m ÿ÷åéêàõ âåðîÿòíîñòü ïîïàäàíèÿ äâóõ
÷àñòèö â îäíó ÿ÷åéêó íå ìåíüøå p .
Çàäà÷à ñîñòîèò â îïðåäåëåíèè àñèìïòîòè÷åñêîãî ïîâåäåíèÿ äëÿ n m( ) . Ñïðàâåäëèâà
ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2. Ïóñòü p � ( ; )0 1 ôèêñèðîâàíî, a p� � �ln( )1 , òîãäà n m am m( ) ( )� � � , ãäå
ïîñëåäîâàòåëüíîñòü { }� ( ),m m � 1 îãðàíè÷åíà è lim ( )
m
m
a
��
� ��
2
, lim ( )
m
m
a
��
� � ��
2
1.
Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî òåîðåìû 2 àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 1.
Ââåäåì ôóíêöèþ
S x
y x
y y x
y x
y y
y ( )
( )
( ) ( )
( )
( ) (
�
� �
� � �
�
�
�
�
� �
�
� �
1
1 2 1 2
2
1
2
1 1 x)
, y y1 1 1� �
, 0
2
� �x
y
.
Îïðåäåëèì ôóíêöèþ x y( ) : ( ; ) ( ; )0 0� � � � � èç ñîîòíîøåíèÿ S x y py ( ( )) � �1 . Òîãäà
n m x m n m( ) ( ) ( )� � �1 , m N� , x y a y
a
o( ) ( )� � �
2
1 ïðè y� � � .
Îòñþäà ñëåäóåò óòâåðæäåíèå òåîðåìû 2.
Ýòè ðåçóëüòàòû ìîæíî ïðèìåíèòü, íàïðèìåð, äëÿ îöåíèâàíèÿ âåðîÿòíîñòè êîëëèçèé
õýø-ôóíêöèé è òðóäîåìêîñòè ïîñòðîåíèÿ êîëëèçèé [4], â êðèïòîàíàëèçå, â òåîðèè ñëó÷àé-
íûõ ðàçìåùåíèé è ñëó÷àéíûõ îòîáðàæåíèé, ïðè îöåíêå ñîâïàäåíèÿ ðåäêèõ ñîáûòèé [5, 6].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ø è ð ÿ å â À . Í . Âåðîÿòíîñòü. — Ì.: Íàóêà, 1980. — 576 ñ.
2. Ñ å ê å é Ã . Ïàðàäîêñû â òåîðèè âåðîÿòíîñòåé è ìàò. ñòàòèñòèêå. — Ì.: Ìèð, 1990. — 240 ñ.
3. Ô è õ ò å í ã î ë ü ö à . Ì . Êóðñ äèôôåðåíöèàëüíîãî è èíòåãðàëüíîãî èñ÷èñëåíèÿ. Ò.2. — Ì.: Íàóêà,
1966. — 800 ñ.
4. À ë ô å ð î â À . Ï . , Ç ó á î â À . Þ . , Ê ó ç ü ì è í À . Ñ . , × å ð å ì ó ø ê è í À . Â . Îñíîâû êðèïòî-
ãðàôèè. — Ì.: Ãåëèîñ ÀÐÂ, 2001. — 480 ñ.
5. Ñ o o p e r C . , G i l c h r i s t R . , K o v a l e n k o I . N . , N o v a c o v i c D . Deriving the number of good
permutstions with applications to cryptography // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1999. — ¹ 5. —
Ñ. 10–16.
6. Ã è ë ê ð è ñ ò Ð . , Ê î â à ë å í ê î È . Í . Îá îöåíêå âåðîÿòíîñòè îòñóòñòâèÿ êîëëèçèé íåêîòîðûõ ñëó-
÷àéíûõ îòîáðàæåíèé // Òàì æå. — 2000. — ¹ 1. — Ñ. 132–138.
Ïîñòóïèëà 17.11.2009
188 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-45210 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:47:50Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ендовицкий, П.А. 2013-06-08T18:41:39Z 2013-06-08T18:41:39Z 2010 Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений / П.А. Ендовицкий // Кибернетика и системный анализ. — 2010. — № 3. — С. 185-188. — Бібліогр.: 6 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45210 519.2 Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 1 наведено асимптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення частинок по чарунках. В теоремі 2 наведено асипмптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення двох однакових комплектів частинок по чарунках. Отримані результати можна застосувати у криптографії для оцінювання трудомісткості побудови колізій хеш-функцій. Proved two theorems about asymptotic behavior group size in birthday paradox. Theorem 1 gives asymptotically best possible estimates for group size in case uniform and independent particle occupancy in cells. Theorem 2 gives asymptotically best possible estimates for group size in case uniform and independent occupancy of two equal sets of particles in cells. These results one may apply in cryptography for estimation working time for construction collisions of hash-functions. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Краткие сообщения Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений Уточнення асимптотичної апроксимації розміру групи в парадоксі днів народжень Asymptotic approximation of the group size in birthday paradox Article published earlier |
| spellingShingle | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений Ендовицкий, П.А. Краткие сообщения |
| title | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_alt | Уточнення асимптотичної апроксимації розміру групи в парадоксі днів народжень Asymptotic approximation of the group size in birthday paradox |
| title_full | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_fullStr | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_full_unstemmed | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_short | Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| title_sort | уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений |
| topic | Краткие сообщения |
| topic_facet | Краткие сообщения |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45210 |
| work_keys_str_mv | AT endovickiipa utočnenieasimptotičeskoiapproksimaciirazmeragruppyvparadoksedneiroždenii AT endovickiipa utočnennâasimptotičnoíaproksimacíírozmírugrupivparadoksídnívnarodženʹ AT endovickiipa asymptoticapproximationofthegroupsizeinbirthdayparadox |