Share N+/-1 Primality Proofs - Page 2

wblipp · 2011-11-09, 05:24

I think I see the misunderstanding. Bob is imagining that I marshaled factoring effort to find the N-1 factors, and that I am encouraging others to also spend their resources finding factors that are wanted only to make the N-1 proofs. I agree that would be pointless effort. But all I really did was click a few buttons and manually type the expression of a few algebraic factors. The needed factors were all small enough that the factordb "scan" buttons, which run a small amount of ECM, P-1, and P+1, provided sufficient factors to make the proof (It's also possible some of the factors were already in the factordb). At these current size ranges - 1200 to 2000 digits - I see lots of cases where adding the algebraic factors and the scan buttons does not complete a proof. I haven't been mentioning these, nor working on them.

So my question was "What should you do if you already know over 33% factorization of N-1?" I thought Bob was saying there is something better. But Batalov's question is "What should you do if you do NOT have 33% factorization?" Within the context of factordb, the answer to that question is currently "Primo."

Random Poster · 2011-11-09, 12:36

Quote:

Originally Posted by Batalov

CHG is also fun to use at about 26 to 27% N+/-1 factored... just like solving a sudoku at a coffee break. (above 27%, it is simply not fun anymore :-) )

Example: 110·R5382-1 is prime. Proven with CHG. (not in FactorDB.)

What's CHG? (Google finds a lot of CHG primality certificates and a lot of unrelated crap, but not an explanation of the method in the first several result pages.)

R.D. Silverman · 2011-11-09, 14:07

Quote:

Originally Posted by wblipp

So my question was "What should you do if you already know over 33% factorization of N-1?" I thought Bob was saying there is something better. But Batalov's question is "What should you do if you do NOT have 33% factorization?" Within the context of factordb, the answer to that question is currently "Primo."

If you know > N^(1/3) factorization of N-1/N+1 then using the combined
Lehmer/Pomerance/Brillhart et.al. thm is fine. But, as you indicate,
factoring efforts on N-1/N+1 are pointless. I am guilty of failing to
convey this point. Note that APR-CL can take advantage of known
factors of N+1/N-1 to speed its proof.

I am unfamiliar with PRIMO. What method(s) does it employ?

bsquared · 2011-11-09, 14:14

Quote:

Originally Posted by R.D. Silverman

I am unfamiliar with PRIMO. What method(s) does it employ?

It uses ECPP.
http://www.ellipsa.eu/public/primo/primo.html

Batalov · 2011-11-09, 19:40

Quote:

Originally Posted by Random Poster

What's CHG? (Google finds a lot of CHG primality certificates and a lot of unrelated crap, but not an explanation of the method in the first several result pages.)

Oh, CHG full name is a mouthful. This is Coppersmith--Howgrave-Graham (this is only two people) lattice basis reduction method(s). The implementations are here and also
> "...If you do not already have it, my validation script is here:
> http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp
> \\ Coppersmith--Howgrave-Graham certificate tester, Version 0.8
> \\ David Broadhurst, 3 Mar 2006, with huge help from John Renze"

xilman · 2011-11-09, 19:49

Quote:

Originally Posted by Batalov

http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp

That could almost have come from the IOCC competition.

I like it!

Paul

wblipp · 2011-11-10, 03:50

Browsing through the PRPs tonight, I found (10^1662*82-73)/9. N-1 is divisible by 10^1662-1. Sufficient factors were previously known to finish the proof.

wblipp · 2011-11-12, 16:08

Just to be clear - what I'm doing is looking the list of already-found PRPs in the factordb, searching for ones where a primality proof can be created easily. I do it because it's fun. I share them because I think other people will find it fun, too.

Last night I spotted (10^1470*4-7)/3. The N+1 shares the cyclotomic form 10^1470-1, which has many algebraic factors, many of which were already factored or quickly succumbed to the scan button.

debrouxl · 2011-11-13, 08:08

I once proved the primality of (2^2617+1)/3 (788 digits), which appeared in the PRP list at the time, by N-1.
(2^2617+1)/3-1 has many small-ish factors, the unfactored part is currently a C322 (more than 450 digits smaller than the original C788 !).

Batalov · 2011-11-13, 13:07

Quote:

Originally Posted by debrouxl

I once proved the primality of (2^2617+1)/3 (788 digits), which appeared in the PRP list at the time, by N-1.
(2^2617+1)/3-1 has many small-ish factors, the unfactored part is currently a C322 (more than 450 digits smaller than the original C788 !).

Should be completely factored really. But factorDB doesn't know that these numbers are related, or that this is related.

wblipp · 2011-11-13, 20:27

Today's proof is a cheat. N=(10^318*911+419)/73082460569797 is slightly larger the 300 digits. N-1 factored quickly with the scan buttons, having a largest factor a little below 300 digits. Factordb automatically proved the factor of N-1, enabling the proof of N.

2011-11-09, 05:24	#12
wblipp "William" May 2003 New Haven 2×7×13² Posts	I think I see the misunderstanding. Bob is imagining that I marshaled factoring effort to find the N-1 factors, and that I am encouraging others to also spend their resources finding factors that are wanted only to make the N-1 proofs. I agree that would be pointless effort. But all I really did was click a few buttons and manually type the expression of a few algebraic factors. The needed factors were all small enough that the factordb "scan" buttons, which run a small amount of ECM, P-1, and P+1, provided sufficient factors to make the proof (It's also possible some of the factors were already in the factordb). At these current size ranges - 1200 to 2000 digits - I see lots of cases where adding the algebraic factors and the scan buttons does not complete a proof. I haven't been mentioning these, nor working on them. So my question was "What should you do if you already know over 33% factorization of N-1?" I thought Bob was saying there is something better. But Batalov's question is "What should you do if you do NOT have 33% factorization?" Within the context of factordb, the answer to that question is currently "Primo." Last fiddled with by wblipp on 2011-11-09 at 05:46

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Can two Mersenne numbers share a factor?	James Heinrich	Math	57	2011-09-12 14:16
Avoidance of self- & other-deception in proofs	cheesehead	Soap Box	71	2010-01-14 09:04
Curious and want to share about Prime number 23	spkarra	PrimeNet	4	2009-11-20 03:54
Status of GIMPS proofs	Brian-E	Information & Answers	7	2007-08-02 23:15
Collection of Proofs?	Orgasmic Troll	Math	1	2004-12-30 15:10

2011-11-10, 03:50	#18
wblipp "William" May 2003 New Haven 2×7×13² Posts	Browsing through the PRPs tonight, I found (10^1662*82-73)/9. N-1 is divisible by 10^1662-1. Sufficient factors were previously known to finish the proof.

2011-11-12, 16:08	#19
wblipp "William" May 2003 New Haven 2×7×13² Posts	Just to be clear - what I'm doing is looking the list of already-found PRPs in the factordb, searching for ones where a primality proof can be created easily. I do it because it's fun. I share them because I think other people will find it fun, too. Last night I spotted (10^1470*4-7)/3. The N+1 shares the cyclotomic form 10^1470-1, which has many algebraic factors, many of which were already factored or quickly succumbed to the scan button.

2011-11-13, 08:08	#20
debrouxl Sep 2009 977 Posts	I once proved the primality of (2^2617+1)/3 (788 digits), which appeared in the PRP list at the time, by N-1. (2^2617+1)/3-1 has many small-ish factors, the unfactored part is currently a C322 (more than 450 digits smaller than the original C788 !).

2011-11-13, 20:27	#22
wblipp "William" May 2003 New Haven 2366₁₀ Posts	Today's proof is a cheat. N=(10^318*911+419)/73082460569797 is slightly larger the 300 digits. N-1 factored quickly with the scan buttons, having a largest factor a little below 300 digits. Factordb automatically proved the factor of N-1, enabling the proof of N.