View Single Post
Old 2020-09-30, 02:11   #1
"James Short"
Mar 2019

17 Posts
Default alternative 2nd stage of p-1 factoring algorithm

Suppose we're factoring an integer via the p-1 method and we've already completed the first stage ie. L = a^{B!} mod(n) where n is the composite we wish to factor.

In the 2nd stage, we assume that there is one prime factor remaining q > B and go on to compute L^{p} for various prime integers.

If q-1 is fairly smooth, would it not be more worthwhile to consider the set (L^{2^{b!}}, L^{3^{b!}}, L^{4^{b!}},. . .,L^{a^{b!}}) for some considerably smaller integer b < B and then compute gcd(L^{i^{b!}} - L^{j^{b!}},n) for all 1 < i < j < a?

Keep in mind that we can perform another kind of "2nd stage" on this as well. ie assume that b! captures most of the prime factors of q-1 and then use a 2nd stage (3rd stage?) by computing (L^{2^{p(b!)}}, L^{3^{p(b!)}}, L^{4^{p(b!)}},. . . ,L^{a^{p(b!)}}) for various primes p > b and again computing gcd(L^{i^{p(b!)}} - L^{j^{p(b!)}},n) for all 1 < i < j < a.
jshort is offline   Reply With Quote