随着信息化进程的深入和互联网的迅速发展,信息安全越来越重要。公开钥密码系统或非对称密码系统是实现和保障信息安全的一种重要方式。基于NP完全问题的背包公钥密码和基于离散对数问题的椭圆曲线密码(ECC)是两种著名的公钥密码系统,在计算机密码学的发展和研究中具有十分重要的地位。为提高它们的加密和解密速度,本文研究背包公钥密码中求解背包问题和GF(p)上ECC基点选取的并行算法。在深入分析背包问题的现有并行算法和GF(p)上ECC的基点选取算法性能的基础上,分别提出一种基于采样和MIMD结构的背包问题并行算法和GF(p)上ECC的并行基点选取算法。并行背包算法基于MIMD结构,在排序过程中引入基于采样的排序算法,然后对子集和生成和搜索过程加以优化。理论分析和在基于Cluster结构的IBM P690高性能计算机上的实验结果表明:本算法可显著减少处理器间的通信量、较好地实现处理器的负载均衡和局部访存。当背包实例的维数大于40时,其并行效率通常可达到60%。采用2m ( m∈N,m≥1)个处理器、m个循环缓存和一个公共表改进的GF(p)上ECC的并行基点选取算法分两步实现:并行随机点产生算法和并行基点判断算法。其算法性能分析和实验结果证明:改进算法可提高处理器的利用率,保证各处理器单元具有较好的负载均衡特性,从而加快标量乘的计算速度。当计算标量乘的点加时间是点倍数时间的3倍时,其并行效率最高可达到90%。