View Single Post
 2020-09-30, 02:11 #1 jshort   "James Short" Mar 2019 Canada 17 Posts 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$.