A few questions about CHG

wpolly · 2018-10-27, 17:11

Hey guys,

So I have a generalized Lucas PRP of ~13k digits, and N-1 has been factored to about 25.55%.

The first question is would this percentage allow the CHG test to be done in a reasonable time?

I would also like to ask, is it feasible to include the factors of N+1 (about 20 total digits) in the process? I've read that considering factors of both N+1 and N-1 requires two CHG processes for factors congruent to 1 and N respectively, so it might be counter-productive. Please correct me if I'm wrong here.

For the third question, I'm thinking about doing the interval selection manually instead of relying on the script. Am I correct in the following phrasing of the whole process?

Choose several tuples of parameters $[h_i,u_i,\beta_i,\gamma_i]$ , such that $2(\alpha+\beta_i)u_ih_i>u_i(u_i+1)+\gamma_ih_i(h_i-1)$ , and the union of all intervals $[\beta_i,\gamma_i]$ covers $[0,1-3\alpha]$ . ( $\alpha$ is the factorization percentage of N-1)
For each tuple of parameters, construct a matrix as in Corollary 3.1 of the CHG paper, use LLL reduction to find a short vector in its row space, and then attempt to show the polynomial induced by this short vector has no integer roots.
The total running time is proportional to $\sum_{i}h_i^4$ , so this is what I should be minimizing when choosing the intervals.

Many thanks for your help!

paulunderwood · 2018-11-01, 16:58

Is this the number in question? I guess not because it is much bigger than ~13k digits.

You should email Prof. Chis Caldwell to change it to a CHG prover code from a primeform one. Also the syntax is wrong. It should use U(?,-1,?). And the comment should say "Generalized Lucas number".

Congrats. I am interested in the proof method. Please post its output here.

wpolly · 2018-11-01, 17:48

No, the PRP I was referring to is Phi(3121,-15439) at 13069 digits. Phi(4201,-5798) is a much lighter CHG proof with 28% factored, thanks to a P1740 factor of N-1.

Batalov · 2018-11-02, 01:31

Quote:

Originally Posted by wpolly

No, the PRP I was referring to is Phi(3121,-15439) at 13069 digits. Phi(4201,-5798) is a much lighter CHG proof with 28% factored, thanks to a P1740 factor of N-1.

It is not clear why that would be a Generalized Lucas.

It is, in a sense, a generalized 'Generalized repunit' (but UTM only takes positive bases b>2).Only a few forms (like Wagstaffs) also happen to be Generalized Lucas, but not just any (b^n+1)/(b+1).

wpolly · 2018-11-02, 03:53

Quote:

Originally Posted by Batalov

It is not clear why that would be a Generalized Lucas.

It is, in a sense, a generalized 'Generalized repunit' (but UTM only takes positive bases b>2).Only a few forms (like Wagstaffs) also happen to be Generalized Lucas, but not just any (b^n+1)/(b+1).

Actually, (b^n+1)/(b+1) is just U(b-1,-b,n).

Batalov · 2018-11-02, 05:22

Yeah, that's true, but a and b are not irrational and the number looks sort of plain.

Not clear, then, why in the UTM stamp collection Gaussian-Mersennes are not double listed as Generalized unique - but they are.

wpolly · 2018-11-02, 12:21

Quote:

Originally Posted by Batalov

Yeah, that's true, but a and b are not irrational and the number looks sort of plain.

Indeed. I think these negative-base GRUs should have a separate category, maybe "Generalized Wagstaff"?

paulunderwood · 2018-11-04, 22:53

The prime is in limbo. Please discuss with Prof. Chris Caldwell what's to be done.

Batalov · 2018-11-05, 02:27

You can also rewrite it in U() form (like this one).
But then again, maybe CC is not working too hard on weekends. Wait for Monday.

Batalov · 2018-11-05, 15:59

Quote:

Originally Posted by wpolly

Hey guys,

So I have a generalized Lucas PRP of ~13k digits, and N-1 has been factored to about 25.55%.

The first question is would this percentage allow the CHG test to be done in a reasonable time?

So, just yesterday I started CHG with 26.85% ratio, and then found a 41-digit ECM factor that allowed to start another CHG with 27.05% ratio. It turns out that the speed is at least 4x faster with 27.05% (at 20k digit size). D.Broadhurst keeps the hardest CHG list somewhere. I believe the record is somewhere around 26%? With lower ratio, thousands iterations will be needed - with enormous time.

Anyway a 13069 number will now be out of top20 and will not be accepted.

paulunderwood · 2018-11-06, 20:24

wpolly's number has been adjusted and has been accepted as a top20 Gen. Lucas number. However Serge's larger number does not have the right colour for the top20. I think CC has another adjustment to do.

2018-10-27, 17:11	#1
wpolly Sep 2002 Vienna, Austria 3×73 Posts	A few questions about CHG Hey guys, So I have a generalized Lucas PRP of ~13k digits, and N-1 has been factored to about 25.55%. The first question is would this percentage allow the CHG test to be done in a reasonable time? I would also like to ask, is it feasible to include the factors of N+1 (about 20 total digits) in the process? I've read that considering factors of both N+1 and N-1 requires two CHG processes for factors congruent to 1 and N respectively, so it might be counter-productive. Please correct me if I'm wrong here. For the third question, I'm thinking about doing the interval selection manually instead of relying on the script. Am I correct in the following phrasing of the whole process? Choose several tuples of parameters $[h_i,u_i,\beta_i,\gamma_i]$ , such that $2(\alpha+\beta_i)u_ih_i>u_i(u_i+1)+\gamma_ih_i(h_i-1)$ , and the union of all intervals $[\beta_i,\gamma_i]$ covers $[0,1-3\alpha]$ . ( $\alpha$ is the factorization percentage of N-1) For each tuple of parameters, construct a matrix as in Corollary 3.1 of the CHG paper, use LLL reduction to find a short vector in its row space, and then attempt to show the polynomial induced by this short vector has no integer roots. The total running time is proportional to $\sum_{i}h_i^4$ , so this is what I should be minimizing when choosing the intervals. Many thanks for your help!

2018-11-01, 16:58	#2
paulunderwood Sep 2002 Database er0rr 3,739 Posts	Is this the number in question? I guess not because it is much bigger than ~13k digits. You should email Prof. Chis Caldwell to change it to a CHG prover code from a primeform one. Also the syntax is wrong. It should use U(?,-1,?). And the comment should say "Generalized Lucas number". Congrats. I am interested in the proof method. Please post its output here. Last fiddled with by paulunderwood on 2018-11-01 at 17:07

2018-11-06, 20:24	#11
paulunderwood Sep 2002 Database er0rr 3,739 Posts	wpolly's number has been adjusted and has been accepted as a top20 Gen. Lucas number. However Serge's larger number does not have the right colour for the top20. I think CC has another adjustment to do. Last fiddled with by paulunderwood on 2018-11-06 at 20:26

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GPU LL Questions	Primeinator	GPU Computing	40	2013-10-20 06:20
gmp-ecm questions	yoyo	GMP-ECM	34	2009-03-20 18:06
Some questions...	OmbooHankvald	PSearch	3	2005-09-17 19:29
5 questions	OmbooHankvald	Factoring	6	2005-08-28 19:31
Questions	OmbooHankvald	Prime Sierpinski Project	2	2005-08-01 20:18

2018-11-01, 17:48	#3
wpolly Sep 2002 Vienna, Austria 3·73 Posts	No, the PRP I was referring to is Phi(3121,-15439) at 13069 digits. Phi(4201,-5798) is a much lighter CHG proof with 28% factored, thanks to a P1740 factor of N-1.

2018-11-02, 05:22	#6
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	Yeah, that's true, but a and b are not irrational and the number looks sort of plain. Not clear, then, why in the UTM stamp collection Gaussian-Mersennes are not double listed as Generalized unique - but they are.

2018-11-04, 22:53	#8
paulunderwood Sep 2002 Database er0rr 3,739 Posts	The prime is in limbo. Please discuss with Prof. Chris Caldwell what's to be done.

2018-11-05, 02:27	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10010100000101₂ Posts	You can also rewrite it in U() form (like this one). But then again, maybe CC is not working too hard on weekends. Wait for Monday.