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

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

Expected coverage rate for the Hellman matrices

Hellman rsquo;s timememory tradeoff is a probabilistic method for inverting oneway functions, using precomputed data. Hellman introduced this method in 1980 and obtained a lower bound for the success probability of his algorithm. After that, all further analyses of researchers are based on this lower bound. In this paper, we first studied the expected coverage rate (ECR) of the Hellman matrices, which are constructed by a single chain. We showed that the ECR of such matrices is maximum and equal to 0.85. In this process, we find out that there exists a gap between the Hellman rsquo;s lower bound and experimental coverage rate of a Hellman matrix. Specifically, this gap is larger, when considering the Hellman matrices constructed with one single chain. So, we are investigated to obtain an accurate formula for the ECR of a Hellman matrix. Subsequently, we presented a new formula that estimate the ECR of a Hellman matrix more accurately than the Hellman rsquo;s lower bound. We showed that the given formula is closely match experimental data. In the last, we introduced a new method to construct matrices which have much more ECR than Hellman matrices. In fact, each matrix in this new method is constructed with one single chain, which is nonrepeating trajectory from a random point. So, this approach result in a number of matrices that each one contains a chain with variable length. The main advantage of this method is that we have more probability of success than Hellman method, however online time and memory requirements are increased. We have also verified theory of this new method with experimental results.