P-1 factoring and BOINC

[MisterBitcoin]

Hello dear Searchers,

I´d like to start an discussion about P-1 factoring and BOINC.
As some of us now that p-1 factoring can find factors for our bases, it might be usefull to test any candidate after sieving. This could be done if n>1M (or a bit less?).

I think this is an great effort for CRUS and could be done using srbase (BOINC). Well, what are you think about that idea?

[Ok, Phase 2 is using some memory, but this shouldn´t be the biggest problem..]

[Batalov]

P-1 factoring has a benefit for moderately sized Mersennes (demonstratively) and similarly for GFNs, and P.I.E.S. All for the same reason - their factors are of shape 2*k*S+1 where S is known and fairly large (it is p for Mersennes, and 2^q for GFNs and 3^t*2^q for P.I.E.S.). This S value is easily added to the group order of the P-1 curve and allows to find significantly larger factors than those found by conventional sieving. P-1 is a good final step before the expensive test for these use cases.

There is no such P-1 benefit for most CRUS forms - except for very few of the CRUS series which are "low-exponent GFNs" (example: when k is a forth power and all survivor n candidates are divisible by 4; see also: there was a thread a few months back by pepi37). For this reason, for most CRUS forms, P-1 will be not producing enough factors that were not already found by conventional sieving.

[pepi37]

I ask Batalov many questions, and he give me many answers in field od math. When I "discovered" P-1 in Prime95 I was astonished when I find first "big factor", but as Batalov say in answer above this: and regardless how many times I try to disprove his information truth is on his side.
P-1 will find factors in any base, and with any candidates, but number of those candidates with needed time to find him is slower then simple sieving them. For now the only sequence that give me many P-1 factors is 4*20˘^n+1 ( it is my own, personal search)
Other sequences give me also some factors , and my highest factor has 36 digits ( and it was composed one)

So from my perspective, when is useful to make P-1?
If you make really deep sieving ( really deep for home users, not deep like Primegrid do) and you what to find a little more factors before starting LLR ( so it looks like good idea when you have own project) - in that case few days more or less is not relevant.
Sieve depth is OK, when you need more time to find factor by sieving then for do LLR.
So doing P-1 on that sequence will find extra factors that you will need many months of sieving until reach that depth.

Second: if candidate number of digits is raised, also time for P-1 is raised as memory allocation. So if you need 10 minutes for P-1 test, and you need to to process 300 candidates until find one ( in average) ( and in meantime for one LLR you need 2 hours) then P-1 is waste of time.

Last,P-1 factors is also good if you have limited resources ( like many of us has limited resources) Then ( sometimes) 50 candidates less ( you find them with P-1) is 50 candidates less for processing. Currently I do 4*53^n+1 and I periodically perform P-1 test before start LLR processing , just to "kill" monotony of LLR , to find some factors and to learn something ( it is funny to factoring those factors) :)

[pepi37]

This is some more info ( on sequence 4*20^n+1)
Let say that sequence is tested up to 100 T -so all factors found by P-1 is above 100T
This is statistics how long are factors and how many factors is found by P-1

14 digits factors - 5
15 digits factors - 36
16 digits factors - 25
17 digits factors - 12
18 digits factors - 12
19 digits factors - 7
20 digits factors - 2
21 digits factors - 4
22 digits factors - 1
23 digits factors - 2
24 digits factors - 2
26 digits factors - 1

[Batalov]

Can you show the 14- and 15-digit factors?
There is an easy explanation for them, I think.

[MisterBitcoin]

Originally Posted by Batalov

P-1 factoring has a benefit for moderately sized Mersennes (demonstratively) and similarly for GFNs, and P.I.E.S. All for the same reason - their factors are of shape 2*k*S+1 where S is known and fairly large (it is p for Mersennes, and 2^q for GFNs and 3^t*2^q for P.I.E.S.). This S value is easily added to the group order of the P-1 curve and allows to find significantly larger factors than those found by conventional sieving. P-1 is a good final step before the expensive test for these use cases.

There is no such P-1 benefit for most CRUS forms - except for very few of the CRUS series which are "low-exponent GFNs" (example: when k is a forth power and all survivor n candidates are divisible by 4; see also: there was a thread a few months back by pepi37). For this reason, for most CRUS forms, P-1 will be not producing enough factors that were not already found by conventional sieving.

Ok, thanks for that info.

[pepi37]

Originally Posted by Batalov

Can you show the 14- and 15-digit factors?
There is an easy explanation for them, I think.

This is list of all factors ( and I listen carefully what is explanation of them)
Can that fact ( that explanation) be used to sieve faster ( or in bigger depth)?
All I can see that every factor end with 1 or 9 :)

[Batalov]

Factors should be accompanied with what they divide!

[pepi37]

here it is

[Batalov]

Originally Posted by pepi37

All I can see that every factor end with 1 or 9 :)

What other digits could they end with (if they are factors of 4*20^n+1 and n = 4k+2 *)?

It is a simple question, really.
Just consider all possible values p mod 20, and you will find that only 1 (mod 20) and 9 (mod 20) are permitted to be factors of 4*20^n+1.

So, it is not just "every factor end with 1 or 9"; it is also (if you are into numerology) "the next to last digit is even"; or in other words, simply, every f = 1 (mod 20) or 9 (mod 20).

____
*...and I am pleased to see that you are not trying to remove n divisible by 4 by running P-1. They seem to be already removed. Good for you. My advice was not wasted.

[pepi37]

Originally Posted by Batalov

*...and I am pleased to see that you are not trying to remove n divisible by 4 by running P-1. They seem to be already removed. Good for you. My advice was not wasted.

Yes, they are removed by your script :) And for that script, I am very grateful :)

There is an easy explanation for them, I think. -and for this part of your message :)? -any new info?

I like those small letters :P