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