mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-09-30, 02:11   #1
jshort
 
"James Short"
Mar 2019
Canada

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
Old 2020-09-30, 17:38   #2
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25·32 Posts
Default

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 p-1 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
bhelmes is offline   Reply With Quote
Old 2020-09-30, 20:05   #3
jshort
 
"James Short"
Mar 2019
Canada

17 Posts
Default

What your describing is something completely different altogether and it isn't the Pollard rho factoring algorithm;

This is the Pollard-rho factoring algorithm;

rho(n)=
{
local(x,y);

x=2; y=5;
while(gcd(y-x,n)==1,
x=(x^2+1)%n;
y=(y^2+1)%n; y=(y^2+1)%n
);
gcd(n,y-x)
}
jshort is offline   Reply With Quote
Old 2020-10-01, 20:15   #4
jshort
 
"James Short"
Mar 2019
Canada

1116 Posts
Default

Quote:
Originally Posted by jshort View Post
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.
I know its bad form to write answers to your own question. To be honest I don't have a straightforward answer as to whether or not this way of conducting a 2nd-stage to the p-1 method is faster than the standard way.

However I also think that we can easily implement both.

25% of all prime integers have the form 1 + 12k. This can be proved using Dirichlet's theorem on arithmetic progressions -

https://en.wikipedia.org/wiki/Dirich...c_progressions

Thus we could set the b = 4! / 2 = 12 and compute (L^{2^{12p}}, L^{3^{12p}}, L^{4^{12p}},. . . ,L^{a^{12p}}) for various primes p up to some limit. Most programs search for primes 100 < p < 1000 in the 2nd stage of the p-1 test. If we did the same here and if we're only checking for primes of the form 1 + 12k in the range (100,1000)than p would only have to be a prime up in the range (11,83).

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 T_{11} = (L^{2^{11(12)}}, L^{3^{11(12)}}, L^{4^{11(12)}},. . . ,L^{a^{11(12)}}) = (s_{1}, s_{2}, . . . , s_{a}).

Then T_{13} = (s_{1}^{2^{12(13-11)}}, s_{2}^{3^{12(13-11)}}, . . . , s_{a}^{a^{12(13-11)}} and so on.

As for the other 75% of the primes in the range (100,1000), 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.
jshort is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New Factoring Algorithm GreasyScooby Factoring 4 2018-04-27 13:48
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
question on P-1 factoring, stage 2 nngs Software 1 2006-11-15 11:07
A new prime factoring algorithm? Visu Factoring 22 2006-11-09 10:43
memory usage in stage 2 of P-1 factoring gckw Software 3 2003-09-07 06:56

All times are UTC. The time now is 17:57.

Fri Dec 4 17:57:10 UTC 2020 up 1 day, 14:08, 0 users, load averages: 2.21, 1.87, 1.79

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.