mersenneforum.org P-1 factoring and BOINC
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-04-26, 18:20 #1 MisterBitcoin     "Nuri, the dragon :P" Jul 2016 Good old Germany 2·13·31 Posts P-1 factoring and BOINC 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..] Last fiddled with by MisterBitcoin on 2017-04-26 at 18:46 Reason: Removed "e" and added ",".
 2017-04-26, 19:16 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100110100102 Posts 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.
 2017-04-26, 22:00 #3 pepi37     Dec 2011 After milion nines:) 142010 Posts 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) :) Last fiddled with by pepi37 on 2017-04-26 at 22:07 Reason: add more text
 2017-04-28, 06:51 #4 pepi37     Dec 2011 After milion nines:) 22·5·71 Posts 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
 2017-04-28, 14:34 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×3×1,571 Posts Can you show the 14- and 15-digit factors? There is an easy explanation for them, I think.
2017-04-28, 17:55   #6
MisterBitcoin

"Nuri, the dragon :P"
Jul 2016
Good old Germany

2·13·31 Posts

Quote:
 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.

2017-04-28, 17:57   #7
pepi37

Dec 2011
After milion nines:)

101100011002 Posts

Quote:
 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 :)
Attached Files
 factors.txt (2.1 KB, 213 views)

Last fiddled with by pepi37 on 2017-04-28 at 17:58

 2017-04-28, 18:39 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 24D216 Posts Factors should be accompanied with what they divide!
2017-04-28, 18:40   #9
pepi37

Dec 2011
After milion nines:)

58C16 Posts

here it is
Attached Files
 FACTORSP-1-SORTED.txt (5.1 KB, 224 views)

2017-04-28, 19:58   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts

Quote:
 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.

2017-04-28, 20:12   #11
pepi37

Dec 2011
After milion nines:)

58C16 Posts

Quote:
 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

Last fiddled with by pepi37 on 2017-04-28 at 20:14

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post jasonp Factoring 4 2011-10-09 11:24 BATKrikke Teams 2 2010-03-05 18:57 Xentar Sierpinski/Riesel Base 5 4 2009-04-25 10:26 masser Sierpinski/Riesel Base 5 1 2009-02-09 01:10 bebarce Software 3 2005-12-15 18:35

All times are UTC. The time now is 06:25.

Wed May 12 06:25:25 UTC 2021 up 34 days, 1:06, 0 users, load averages: 1.31, 1.55, 1.63

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.