a=2在Pollard p-1分解方法中的应用

Question

波拉德p-1分解方法指出，如果\gcd(2^{B!}-1,n)=p，其中p>1和B定义了p的素因子，则p是n的素因子。

• 对于任意的\gcd(a^{B!}-1,n)，它不应该是a吗？
• 我们为什么选择a=2？是因为计算2的功率在计算上更便宜吗？(左移)。
• 此外，B是p-1素因子的上界还是p-1素数因子的上界及其幂呢？

Answer 1

• 对于任意的\gcd(a^{B!}-1,n)，它不应该是a吗？

是的，您的代码尝试在while循环中计算它。注:正常情况下

M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }只有小于或等于B的素数才构成M。幻灯片中的伪代码包括所有不正确的数字<B，它必须是素数小于或等于B。

• 我们为什么选择a=2？是因为计算2的功率在计算上更便宜吗？(左移)。

我们需要一个随机整数a，它是n的余素数，即\gcd(a,n)=1。如果像RSA模- n是两个奇数素数的乘积一样，可以选择2，那么计算\gcd(2^{B!}-1,n)就容易了。

• 此外，B应该是p-1素数的上界还是p-1素数的上界及其幂呢？

B是一个光滑数，在开始时，您选择B的任何光滑性。来自维基百科代码；

1. 选择光滑界B
2. 定义M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }
3. 随机选择n的一个副本(注意:我们实际上可以修复a，例如，如果n是奇数，那么我们总是可以选择a = 2，这里的随机选择并不是必需的)
4. 计算g = \gcd(a^M − 1, n) (注意:指数可以做模n)
5. 如果1 < g < n，则返回g
6. 如果g = 1，然后选择一个较大的B并转到步骤2或返回失败
7. 如果g = n，然后选择一个较小的B，然后转到步骤2或返回失败

因此，该算法在意义上是一种自适应算法。如果失败，您可以停止或调整平滑范围。