ناصرحسین غروی، عبدالرسول میرقدری، محمد عبدالهی ازگمی، سید احمد موسوی،
دوره ۱۵، شماره ۳ - ( ۹-۱۳۹۷ )
چکیده
مصالحه حافظهزمان یک الگوریتم احتمالاتی برای وارونکردن توابع یکطرفه، با استفاده از دادههای از پیش محاسبهشده است. هلمن در سال ۱۹۸۰ این روش را معرفی کرد و یک کران پایین برای احتمال موفقیت آن بهدست آورد. پس از آن نیز تحلیلهای پژوهشگران برای بررسی احتمال موفقیت، بر اساس همین کران پایین بوده است. در این مقاله، ابتدا به بررسی امید ریاضی نرخ پوشش یک ماتریس هلمن میپردازیم؛ سپس، این نرخ را برای ماتریسهای هلمنی که فقط از یک زنجیره تشکیل شدهاند، محاسبه کردهایم. نشان دادهایم که امید ریاضی نرخ پوشش برای چنین ماتریسهایی بیشینه و برابر با ۸۵/۰ است. در ادامه، روشهایی برای تخمین دقیقتر این نرخ ارائه، و با روش هلمن مقایسه و درنهایت، ماتریسهای هلمنی را معرفی کردهایم که فقط از یک زنجیره تشکیل شدهاند؛ ولی طول این زنجیره مقداری ثابت نیست و تا رسیدن به نخستین تکرار ادامه مییابد. بهصورت نظری و عملی نشان دادهایم که احتمال موفقیت برای چنین ماتریسهایی بیشتر از روش هلمن است.