步走到教室找最前排的位置坐下，将平板打开。
    今天学习的内容是对大整数n=pq分解的一个RSA有效搜索算法，尽管距离最终目标还有一定的差距，但是在今天过后他就可以开始尝试沿着这个方向去构建算法，等过几天学完了相关知识点，算法也就能得到完善了。
    顺着平板上的内容学习下去，其方法思路也逐渐清晰明了。
    设n=pq，其中p与q都是大素数，令k=st，称之为调差因子，这两都是正整数的话，则有等式sp+tq的平方等于sp-tq的平方加4stpq恒成立。
    ……
    如果m+1的平方减去4kn所得结果是一个整数的平方，那就可以用欧几里德算法，使n得以分解。
    再有开放算法从m的高比特位开始依次确定m的各比特位的值，用x的绝对值表示x的比特位长度……
    为方便分析把移位看作加法（移位比加法简单），因加一运算均是在左移后进行，只相当于最低比特位取反，可忽略不计，所以最坏的情况下全过程只需要4(t-1)次加法。
    具体的算法流程并不长，因为这不是真正的对大整数进行了因数分解，而是采用了一定取巧的方式，在实际体制中不可能穷尽s、t的值去进行验证，因此该RSA有效搜索算法有很大的有效性，但是不绝对。
    至于时间复杂度，对于一般的每秒可做一千万次基本加法运算的计算机，需要约一个半小时完成，考虑到当前碧穹星的计算机运算

本章还未完，请点击下一页继续阅读>>>