Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений
Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 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_ | 1862713948658204672 |
|---|---|
| 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 | |
| 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 |