求解一类单向函数的 TMP 权衡方法

摘要

针对求解一类具有良好伪随机性的单向函数，利用ＴＭＰ权衡技术，提出了一种新型的迭代算法．经过分析，此算法在计算上是可行的：其时间复杂度Ｔ～ｌｔ，空间复杂度Ｍ～ｍ，（其中ｍｌｔ≥Ｎ，Ｎ是所求问题定义域中元素的个数），且此算法将以极大概率（在随机性假设下，以１概率）在上述时空复杂度内得出所求结果；同时，对特殊问题ＤＥＳ进行复杂度分析，证明了此算法的优越性．