mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2017-01-16, 11:03   #1
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

1,487 Posts
Default 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
pepi37 is online now   Reply With Quote
Old 2017-01-16, 15:05   #2
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

5CF16 Posts
Default

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 :)
pepi37 is online now   Reply With Quote
Old 2017-01-16, 18:24   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

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,
Batalov is offline   Reply With Quote
Old 2017-01-16, 18:44   #4
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

148710 Posts
Default

So sequence like 4*155^n+1 or 4*20^n+1 pr 4*50^n+1 etc etc will gain some boost?
pepi37 is online now   Reply With Quote
Old 2017-01-16, 18:47   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

259116 Posts
Default

Yes, a 1 bit boost. They are "GFNs" of form x^2+1, so all their factors are of form 4k+1.
Batalov is offline   Reply With Quote
Old 2017-01-16, 18:54   #6
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

5CF16 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
pepi37 is online now   Reply With Quote
Old 2017-01-17, 05:42   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

265016 Posts
Default

Quote:
Originally Posted by Batalov View Post
A trivial example is Mersenne primes
Yeah, they factor as 1 times M...
(sorry, I could not stop myself, hehe)
LaurV is offline   Reply With Quote
Old 2017-01-17, 07:01   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59·163 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2017-01-17, 10:46   #9
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

1,487 Posts
Default

Just do not begin fight , everything else is allowed
pepi37 is online now   Reply With Quote
Old 2017-01-20, 14:31   #10
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

101110011112 Posts
Default

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
pepi37 is online now   Reply With Quote
Old 2017-01-20, 16:04   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59·163 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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 View Post
...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".
Batalov is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:16.


Fri Dec 3 13:16:46 UTC 2021 up 133 days, 7:45, 0 users, load averages: 1.03, 1.17, 1.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.