mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-04-26, 18:20   #1
MisterBitcoin
 
MisterBitcoin's Avatar
 
"Nuri, the dragon :P"
Jul 2016
Good old Germany

5·7·23 Posts
Default 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 ",".
MisterBitcoin is offline   Reply With Quote
Old 2017-04-26, 19:16   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100101011012 Posts
Exclamation

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.
Batalov is offline   Reply With Quote
Old 2017-04-26, 22:00   #3
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

3·11·43 Posts
Default

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
pepi37 is offline   Reply With Quote
Old 2017-04-28, 06:51   #4
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

3·11·43 Posts
Default

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
pepi37 is offline   Reply With Quote
Old 2017-04-28, 14:34   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41×229 Posts
Default

Can you show the 14- and 15-digit factors?
There is an easy explanation for them, I think.
Batalov is offline   Reply With Quote
Old 2017-04-28, 17:55   #6
MisterBitcoin
 
MisterBitcoin's Avatar
 
"Nuri, the dragon :P"
Jul 2016
Good old Germany

5×7×23 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
MisterBitcoin is offline   Reply With Quote
Old 2017-04-28, 17:57   #7
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

3×11×43 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
File Type: txt factors.txt (2.1 KB, 206 views)

Last fiddled with by pepi37 on 2017-04-28 at 17:58
pepi37 is offline   Reply With Quote
Old 2017-04-28, 18:39   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

24AD16 Posts
Default

Factors should be accompanied with what they divide!
Batalov is offline   Reply With Quote
Old 2017-04-28, 18:40   #9
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

3×11×43 Posts
Default

here it is
Attached Files
File Type: txt FACTORSP-1-SORTED.txt (5.1 KB, 219 views)
pepi37 is offline   Reply With Quote
Old 2017-04-28, 19:58   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41×229 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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.
Batalov is offline   Reply With Quote
Old 2017-04-28, 20:12   #11
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

3·11·43 Posts
Default

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

Thread Tools


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

All times are UTC. The time now is 01:24.

Tue Apr 13 01:24:00 UTC 2021 up 4 days, 20:04, 1 user, load averages: 2.48, 2.32, 2.36

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.