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."

[QUOTE=Batalov;277617]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: [URL="http://factordb.com/index.php?query=%2811*10%5E5383-119%29%2F9"]110·R5382-1[/URL] is prime. Proven with CHG. (not in FactorDB.)[/QUOTE]
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.)

[QUOTE=wblipp;277672]
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."[/QUOTE]

If you know > N^(1/3) factorization of N-1/N+1 then using the combined
Lehmer/Pomerance/Brillhart et.al. thm is [i]fine[/i]. 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?

[QUOTE=R.D. Silverman;277692]
I am unfamiliar with PRIMO. What method(s) does it employ?[/QUOTE]

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

[QUOTE=Random Poster;277685]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.)[/QUOTE]
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 [URL="http://primes.utm.edu/bios/page.php?id=797"]here[/URL] and also
> "...If you do not already have it, my validation script is here:
> [URL="http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp"][COLOR=#247cd4]http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp[/COLOR][/URL]
> \\ Coppersmith--Howgrave-Graham certificate tester, Version 0.8
> \\ David Broadhurst, 3 Mar 2006, with huge help from John Renze"

[QUOTE=Batalov;277722][URL="http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp"][COLOR=#247cd4]http://physics.open.ac.uk/~dbroadhu/cert/chgcertd.gp[/COLOR][/URL][/QUOTE]That could almost have come from the IOCC competition.

I like it!

Paul

Browsing through the PRPs tonight, I found [URL="http://factorization.ath.cx/index.php?id=1100000000291709216"](10^1662*82-73)/9[/URL]. N-1 is divisible by 10^1662-1. Sufficient factors were previously known to finish the proof.

Just to be clear - what I'm doing is looking the list of [URL="http://factorization.ath.cx/listtype.php?t=1"]already-found PRPs[/URL] 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 [URL="http://factorization.ath.cx/index.php?id=1000000000009951494"](10^1470*4-7)/3[/URL]. 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.

I once proved the primality of (2^2617+1)/3 (788 digits), which appeared in the PRP list at the time, by N-1.
[url=http://factordb.com/index.php?id=1100000000271726668](2^2617+1)/3-1[/url] has many small-ish factors, the unfactored part is currently a C322 (more than 450 digits smaller than the original C788 !).

[QUOTE=debrouxl;278103]I once proved the primality of (2^2617+1)/3 (788 digits), which appeared in the PRP list at the time, by N-1.
[URL="http://factordb.com/index.php?id=1100000000271726668"](2^2617+1)/3-1[/URL] has many small-ish factors, the unfactored part is currently a C322 (more than 450 digits smaller than the original C788 !).[/QUOTE]
Should be [URL="http://factordb.com/index.php?query=%282%5E2616-1%29"]completely[/URL] factored really. But factorDB doesn't know that these numbers are related, or that [URL="http://factordb.com/index.php?query=%282%5E2616-1%29%2F3"]this[/URL] is related.

Today's proof is a cheat. N=[URL="http://factorization.ath.cx/index.php?id=1100000000464035217"](10^318*911+419)/73082460569797[/URL] 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.