Prime95 P-1/Pfactor using to find factors on CRUS bases

pepi37 · 2017-01-16, 11:03

When Masser suggested that very light P-1 factoring would further significantly reduce the likelihood of an unfactored, large exponent term with algebraic factors, I decide to try on this for me, new area of interest.
I know that Pfactor and Pminus1 is not the same, but it looks like they work similar on Prime95.
So I try on my npg sequence that have 2M1 digits and above ( bases 155, 212) in order to find same factors. I run it all night, and in the morning I have found few new factors.

So now when I have test data, I try to optimize it, so I run different setting , so find what settings find all factors I have ( in my test data) and to be faster then it was first time.
At the end I found that Pfactor=4,212,n,1,45,8 was winning combination.
Since Prime95 write in log what is B1 and B2 choose for optimal: I try also to play with Pminus1 option in Prime95.
Got pretty much same result.

And last night I try to go much more deeper ( B2 is set to 2000000) and in the morning I was surprised that I found only one new factor ( yes I know there is no need to get same B1, B2 setting and process it few times since it will be (almost) always find same factors.

I also play with base2 candidates, and in that case ( and since I sieving that sequence with GPU) I found no new factors, but find it is much faster then on any other bases.

So I have question:

1. why much more deeper B2 ( from 700000 - 2000000) gives such small number of new candidate? - Yes, it must be some reason why Masser suggested very light P-1 factoring ( in my case, and my experiment suggest values for very light P-1 will be B1=20000 , B2=400000).

Some of you maybe thing it is useless to use P-1/Pfactor to find candidates, and maybe sr x sieve will find it faster, but it is experiment, and every candidate less is good thing

So if you gave any idea, suggestion be free to write it , thanks for reading!

pepi37 · 2017-01-16, 15:05

Additional info
From CUDA PPS sieve I know for two factors

451228441149281 | 28561*2^4020784+1
478743809616001 | 83521*2^4011252+1

Prime95 successfully detect one of them , but not the other, regardless,am I using Pfactor or Pminus1 ( and regardless of low boundary value)

Pminus1
P-1 found a factor in stage #2, B1=20000, B2=700000, E=6.
83521*2^4011252+1 has a factor: 478743809616001 (P-1, B1=20000, B2=700000, E=6)
28561*2^4020784+1 completed P-1, B1=20000, B2=700000, E=6, We4: 6815670D

Pfactor

[Mon Jan 16 16:02:46 2017]
83521*2^4011252+1 completed P-1, B1=55000, B2=660000, E=6, We4: 67E373DB
28561*2^4020784+1 completed P-1, B1=55000, B2=660000, E=6, We4: 68157375

It look like I need to learn more :)

Batalov · 2017-01-16, 18:24

P-1 is effective for the inputs that have a known partial factorization of all future factors. A trivial example is Mersenne primes, as well as Wagstaff's, GFNs, GUs, GMs, EMs, All of them have factors P, with P-1 known to have 20-25 bits already factored. You get this 20-25 bit boost for free and on top of it you get an additional factor of P-1, and as a result you get a factor P which is above what you can get with TF/sieving.

For most CRUS candidates, you only know that P-1 has a factor 2 (which is no new information, and hence no boost), and a P-1 curve will be as effective as 1 curve of ECM. Occasionally, yes, you will get a factor in line with random probability,

pepi37 · 2017-01-16, 18:44

So sequence like 4*155^n+1 or 4*20^n+1 pr 4*50^n+1 etc etc will gain some boost?

Batalov · 2017-01-16, 18:47

Yes, a 1 bit boost. They are "GFNs" of form x^2+1, so all their factors are of form 4k+1.

pepi37 · 2017-01-16, 18:54

Quote:

Originally Posted by Batalov

You get this 20-25 bit boost for free and on top of it you get an additional factor of P-1, and as a result you get a factor P which is above what you can get with TF/sieving.

So does I do something wrong if I got only 1 bit boost, and you say above, 20-25 bit boost.Seems like I dont use Prime95 properly.

LaurV · 2017-01-17, 05:42

Quote:

Originally Posted by Batalov

A trivial example is Mersenne primes

Yeah, they factor as 1 times M...

(sorry, I could not stop myself, hehe)

Batalov · 2017-01-17, 07:01

Your "M" does have a factor M, for which M-1 is indeed = 2kp.
Please by all means continue correcting my missing commas and other typos. You are indispensable in this role.

pepi37 · 2017-01-17, 10:46

Just do not begin fight , everything else is allowed

pepi37 · 2017-01-20, 14:31

After few days of playing using different B1 and B2 values: I came to conclusion that removal rate is about constant 2.2% , so for small numbers it is very slower, much slower then LLR, but on huge numbers ( like Batalov say) it has some sense!
And of course it is good to learn something new.

Thanks masser for point me to P-1.

Batalov · 2017-01-20, 16:04

Quote:

Originally Posted by pepi37

I came to conclusion that removal rate is about constant 2.2% , so for small numbers it is very slower, much slower then LLR, ...

Can you run 45 P-1 tests (which will remove 1 candidate -- based on your own 2.2% value) faster than 1 LLR test?

Quote:

Originally Posted by pepi37

...but on huge numbers ( like Batalov say) it has some sense!

I was just being polite. On these, it most likely doesn't.
I explained on which candidates "it has some sense".

2017-01-16, 11:03	#1
pepi37 Dec 2011 After milion nines:) 2³×181 Posts	Prime95 P-1/Pfactor using to find factors on CRUS bases When Masser suggested that very light P-1 factoring would further significantly reduce the likelihood of an unfactored, large exponent term with algebraic factors, I decide to try on this for me, new area of interest. I know that Pfactor and Pminus1 is not the same, but it looks like they work similar on Prime95. So I try on my npg sequence that have 2M1 digits and above ( bases 155, 212) in order to find same factors. I run it all night, and in the morning I have found few new factors. So now when I have test data, I try to optimize it, so I run different setting , so find what settings find all factors I have ( in my test data) and to be faster then it was first time. At the end I found that Pfactor=4,212,n,1,45,8 was winning combination. Since Prime95 write in log what is B1 and B2 choose for optimal: I try also to play with Pminus1 option in Prime95. Got pretty much same result. And last night I try to go much more deeper ( B2 is set to 2000000) and in the morning I was surprised that I found only one new factor ( yes I know there is no need to get same B1, B2 setting and process it few times since it will be (almost) always find same factors. I also play with base2 candidates, and in that case ( and since I sieving that sequence with GPU) I found no new factors, but find it is much faster then on any other bases. So I have question: 1. why much more deeper B2 ( from 700000 - 2000000) gives such small number of new candidate? - Yes, it must be some reason why Masser suggested very light P-1 factoring ( in my case, and my experiment suggest values for very light P-1 will be B1=20000 , B2=400000). Some of you maybe thing it is useless to use P-1/Pfactor to find candidates, and maybe sr x sieve will find it faster, but it is experiment, and every candidate less is good thing So if you gave any idea, suggestion be free to write it , thanks for reading! Last fiddled with by pepi37 on 2017-01-16 at 11:04

2017-01-20, 14:31	#10
pepi37 Dec 2011 After milion nines:) 2³×181 Posts	After few days of playing using different B1 and B2 values: I came to conclusion that removal rate is about constant 2.2% , so for small numbers it is very slower, much slower then LLR, but on huge numbers ( like Batalov say) it has some sense! And of course it is good to learn something new. Thanks masser for point me to P-1. Last fiddled with by pepi37 on 2017-01-20 at 14:32

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Find factors for non base2 candidates	pepi37	GMP-ECM	2	2017-03-07 20:13
Fails to find very small factors.	Mr. P-1	FactorDB	6	2013-03-22 02:30
Best Way to find large factors	mahnouman	Information & Answers	19	2013-02-22 06:11
Generalizing algebraic factors on Riesel bases	gd_barnes	Conjectures 'R Us	31	2010-04-06 02:04
How to find factors I found with TF?	edorajh	PrimeNet	3	2004-10-01 19:16

2017-01-16, 15:05	#2
pepi37 Dec 2011 After milion nines:) 1448₁₀ Posts	Additional info From CUDA PPS sieve I know for two factors 451228441149281 \| 285612^4020784+1 478743809616001 \| 835212^4011252+1 Prime95 successfully detect one of them , but not the other, regardless,am I using Pfactor or Pminus1 ( and regardless of low boundary value) Pminus1 P-1 found a factor in stage #2, B1=20000, B2=700000, E=6. 835212^4011252+1 has a factor: 478743809616001 (P-1, B1=20000, B2=700000, E=6) 285612^4020784+1 completed P-1, B1=20000, B2=700000, E=6, We4: 6815670D Pfactor [Mon Jan 16 16:02:46 2017] 835212^4011252+1 completed P-1, B1=55000, B2=660000, E=6, We4: 67E373DB 285612^4020784+1 completed P-1, B1=55000, B2=660000, E=6, We4: 68157375 It look like I need to learn more :)

2017-01-16, 18:24	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴×593 Posts	P-1 is effective for the inputs that have a known partial factorization of all future factors. A trivial example is Mersenne primes, as well as Wagstaff's, GFNs, GUs, GMs, EMs, All of them have factors P, with P-1 known to have 20-25 bits already factored. You get this 20-25 bit boost for free and on top of it you get an additional factor of P-1, and as a result you get a factor P which is above what you can get with TF/sieving. For most CRUS candidates, you only know that P-1 has a factor 2 (which is no new information, and hence no boost), and a P-1 curve will be as effective as 1 curve of ECM. Occasionally, yes, you will get a factor in line with random probability,

2017-01-16, 18:44	#4
pepi37 Dec 2011 After milion nines:) 2³×181 Posts	So sequence like 4155^n+1 or 420^n+1 pr 4*50^n+1 etc etc will gain some boost?

2017-01-16, 18:47	#5
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴·593 Posts	Yes, a 1 bit boost. They are "GFNs" of form x^2+1, so all their factors are of form 4k+1.

2017-01-17, 07:01	#8
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10010100010000₂ Posts	Your "M" does have a factor M, for which M-1 is indeed = 2kp. Please by all means continue correcting my missing commas and other typos. You are indispensable in this role.

2017-01-17, 10:46	#9
pepi37 Dec 2011 After milion nines:) 5A8₁₆ Posts	Just do not begin fight , everything else is allowed