20200930, 02:11  #1 
"James Short"
Mar 2019
Canada
17 Posts 
alternative 2nd stage of p1 factoring algorithm
Suppose we're factoring an integer via the p1 method and we've already completed the first stage ie. where is the composite we wish to factor.
In the 2nd stage, we assume that there is one prime factor remaining and go on to compute for various prime integers. If is fairly smooth, would it not be more worthwhile to consider the set for some considerably smaller integer and then compute for all ? Keep in mind that we can perform another kind of "2nd stage" on this as well. ie assume that captures most of the prime factors of and then use a 2nd stage (3rd stage?) by computing for various primes and again computing for all . 
20200930, 17:38  #2 
Mar 2016
171_{16} Posts 
A peaceful night for you,
you are right, but this is not really new for me. You can transform the polynom for pollard rho in a 2x2 matrix and calculate the 2x2 matrix with fast exponentation for the primes < 10^9 for example. You can use a subgroup either a vektor consisting of a pythagoraic triple either a vektor base on the pell equation. Nevertheless it is either a p1 or a p+1 test, I think with 40 digits it will go. But elliptic curves are better because of its various group structure. Nice greetings from the factoring part Bernhard 
20200930, 20:05  #3 
"James Short"
Mar 2019
Canada
17 Posts 
What your describing is something completely different altogether and it isn't the Pollard rho factoring algorithm;
This is the Pollardrho factoring algorithm; rho(n)= { local(x,y); x=2; y=5; while(gcd(yx,n)==1, x=(x^2+1)%n; y=(y^2+1)%n; y=(y^2+1)%n ); gcd(n,yx) } 
20201001, 20:15  #4  
"James Short"
Mar 2019
Canada
17 Posts 
Quote:
However I also think that we can easily implement both. 25% of all prime integers have the form . This can be proved using Dirichlet's theorem on arithmetic progressions  https://en.wikipedia.org/wiki/Dirich...c_progressions Thus we could set the and compute for various primes up to some limit. Most programs search for primes in the 2nd stage of the p1 test. If we did the same here and if we're only checking for primes of the form in the range than would only have to be a prime up in the range . One thing I should mention is that obviously you'd want to start at 11 and then work your way up since just as in the standard 2nd stage of the test, you can use previous terms to save time in computing future terms. For example, let . Then and so on. As for the other 75% of the primes in the range , we could either run this same alternative 2nd stage as we just did. However if this proves to be slower, we can just use the standard 2nd stage that is commonly used to check the remaining primes individually. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New Factoring Algorithm  GreasyScooby  Factoring  4  20180427 13:48 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
question on P1 factoring, stage 2  nngs  Software  1  20061115 11:07 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 
memory usage in stage 2 of P1 factoring  gckw  Software  3  20030907 06:56 