背包类问题的并行O(2^(5n/6))时间-空间-处理机折衷(英文)

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.

基于彩虹表的时间-存储折中攻击改进算法

杂凑函数是将任意长度的字符串映射到固定长度输出的函数,由于其具有单向性而被广泛的应用于口令认证.许多网站或服务器都使用杂凑函数来保存用户口令.时间-存储折中攻击是1980年由Martin Hellman提出的,它能够在有限的存储和计算能力的限制下,在可接受的时间内计算出常用的计算机口令.而Philippe Oechslin在2003年提出的彩虹表法极大地提升了时间-存储折中攻击的效率,此后在彩虹表法的基础上,大量改进算法被纷纷提出.本文提出了一种基于彩虹表的时间存储-折中攻击改进算法,它应用了概率统计的方法,能够在基本保证成功率的基础上大大提升搜索效率.即当成功率降低4.12%时,搜索时间降低86.21%,它是一种效率与成功率折中的算法.

Grain-v1的猜测确定新攻击方法

针对Grain-v1是否存在未知安全缺陷,提出了一种新的猜测确定攻击方法。利用内部状态转移特征和抽头位置关系,优先恢复其线性移位寄存器内部状态信息,并结合时间-存储-数据折中技术给出新的内部状态恢复攻击。结果表明:该攻击需要的数据复杂度为279bit密钥流,时间复杂度为286.3次算法加密,存储复杂度为280个160bit数据块。与已有的攻击方法相比,新攻击需要的时间复杂度更低。

人机交互中基于时间约束的人体工效模型

针对人机交互领域速度-准确度折中关系的预测中任务完成精确度的预测模型较为欠缺的问题,提出了一种基于时间约束的精确度模型预测方法。该方法采用了人机交互研究中常用的受控实验测试分析法,研究了在计算机用户界面中要求用户在给定的时间内完成任务时,任务完成的精确度与给定的时间约束之间的折中关系,用以衡量完成时间约束任务的人体工效。实验中设计了一系列受时间约束的轨道滑动任务,实验环境中自变量包括轨道长度、轨道宽度以及规定的在轨道中滑动的时间,因变量为任务完成的精确度,采用在轨道中滑动时轨迹的纵向偏差表示。通过对30位被试者实验数据的分析发现,任务完成的精确度与轨道宽度以及滑动速度(表示为轨道长度/规定的滑动时间)之间构成线性的关系,在此基础上采用最小二乘方回归法建立了一个基于时间约束的任务完成精确度的量化模型;该模型与真实实验数据集的拟合优度达到了0.857。

阻变存储单元中元素的三维分布

近年来,人工智能、大数据、物联网等领域的快速发展,使新原理信息存储器件的设计、制造成为半导体等产业的重点发展方向.阻变存储器因具有优异的存储特性、良好的尺寸化能力、易于高密度集成等显著优点,被视为下一代非挥发性存储器的理想解决方案.但是由于发生电阻转变的区域难以观测,阻变器件的转变机制一直存在争议.该文利用飞行时间-二次离子质谱对阻变存储单元中元素的三维分布进行探测,有效地证明了电阻转变机制与金属电极原子的扩散无关,而是由氧化物薄膜本身的电学特性所决定的.该文的工作对阻变存储器件的机理探究、设计制备和性能改进具有十分积极的意义.

一种求解背包问题的自适应算法

针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用2δ个处理机、O(ε2(n-δ)/2)的时间、O(2(n+δ)/2-ε)的空间求解背包问题(0≤δ≤n/5,1≤ε≤(n-δ)/4),根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。