本文主要是介绍RSA数分解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述
RSA数是两个素数的乘积,例如 156287 = 373×419。问题是已知一个RSA数,如何在可接受的时间内将其分解为两个素数。
问题分析
这个问题是RSA非对称加密算法的核心。非对称的意思就是将一个大数分解质因数的时间远大于将两个素数乘起来的时间。
该问题的难点是指数增长的时间复杂度。即随着两个素数位数的增长,计算量呈指数增长。这被认为是不可解的。
问题求解
设RSA数为n,朴素的方法是穷举,即使用小于 n√ 的每一个数去除n,看看能否除尽。
另一个可能的改进是仅用小于<
这篇关于RSA数分解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!