امید ریاضی نرخ پوشش برای ماتریس های هلمن

مصالحه حافظه زمان یک الگوریتم احتمالاتی برای وارون کردن توابع یک طرفه، با استفاده از داده های از پیش محاسبه شده است. هلمن در سال 1980 این روش را معرفی کرد و یک کران پایین برای احتمال موفقیت آن به دست آورد. پس از آن نیز تحلیل های پژوهش گران برای بررسی احتمال موفقیت، بر اساس همین کران پایین بوده است. در این مقاله، ابتدا به بررسی امید ریاضی نرخ پوشش یک ماتریس هلمن می پردازیم؛ سپس، این نرخ را برای ماتریس های هلمنی که فقط از یک زنجیره تشکیل شده اند، محاسبه کرده ایم. نشان داده ایم که امید ریاضی نرخ پوشش برای چنین ماتریس هایی بیشینه و برابر با 85/0 است. در ادامه، روش هایی برای تخمین دقیق تر این نرخ ارائه، و با روش هلمن مقایسه و در نهایت، ماتریس های هلمنی را معرفی کرده ایم که فقط از یک زنجیره تشکیل شده اند؛ ولی طول این زنجیره مقداری ثابت نیست و تا رسیدن به نخستین تکرار ادامه می یابد. به صورت نظری و عملی نشان داده ایم که احتمال موفقیت برای چنین ماتریس هایی بیشتر از روش هلمن است.