Share N+/-1 Primality Proofs - Page 32

Dylan14 · 2017-10-26, 02:04

3^2225-3^225-1 has been proven prime by factoring 3^2225-3^225 to sufficient depth.

chris2be8 · 2017-10-26, 15:40

Or you can search for algebraic factors by brute force. Eg:

Code:

~/bin> findalg2.pl.txt '(935^1341-1)*(935^3-1)/(935^447-1)/(935^9-1)-1'
base is 935, exp is 1341, sign is -.
935^1+1
935^1-1
935^2+1
935^2-1
935^3+1
935^3-1
935^4-1
935^6+1
935^6-1
935^12-1
935^37+1
935^37-1
935^74+1
935^74-1
935^111+1
935^111-1
935^148-1
935^222+1
935^222-1
935^444-1

It's not elegant but it works.

Chris

rcv · 2017-10-27, 03:39

Quote:

Originally Posted by chris2be8

Or you can search for algebraic factors by brute force. ... It's not elegant but it works.
Chris

@Chris: Actually, I think that's a clever idea! Even though you call it "brute force" it's probably faster than asking my computer algebra system to perform the factorization.

Dr Sardonicus · 2017-10-27, 14:49

Quote:

Originally Posted by chris2be8

Or you can search for algebraic factors by brute force.
(snip)
It's not elegant but it works.

This "brute force" method has the great advantage that integer arithmetic is way, way faster than polynomial algebra. So, as long as the exponent is not very large, it is almost certain to find the cyclotomic factors much faster than any "elegant" algebraic method, even with all the trial and error.

One can use "elegant" algebra to check the answer. In this case, polcyclo(3^2 * 149) may be written

(x^9*149 - 1)/(x^3*149 - 1) * (x^9 - 1)/(x^3 - 1)

If x^3*148 = 1, then x^3*149 = x^3, so this reduces to

(x^9 - 1)/(x^3 - 1) *(x^9 - 1)/(x^3 - 1), or 1.

So x^444 - 1 is indeed an algebraic factor of polcyclo(9*149) - 1.

Incidentally, given the base b, the cyclotomic factors of b^n - 1 may also be computed expeditiously using integer arithmetic, via the formula

polcyclo(D)[b] = product, d divides D, (b^d - 1)^moebius(D/d)

for each divisor D of n.

These will be the primitive parts, apart from the occasional occurrence of an "intrinsic" prime factor.

rcv · 2017-10-27, 18:40

Following up on my post from a couple of days ago...

I don't think I have had a successful N-1 factorization of a primitive from a number of the form k^n+/-1. when 3 is not a divisor of n or if n is divisible by 3 or more distinct prime factors (including the 3).

Although I haven't proven that it's always true, the "big primitive" gets more than 2/3 of the total number of digits. Yes, you might get lucky, but I can't dependably count on being able to use the N-1 method in the cases noted above.

With that said, I'll extend my "cookbook" formula to finding the algebraic factors of the primitive minus 1 for primitives from numbers of the form k^(9*q)-1.

For the very special case of n=9q, where q is a distinct odd prime not equal to 3, the N-1 term can be factored as follows:
$\frac{(k^{9q}-1)(k^3-1)}{(k^9-1)(k^{3q}-1)}-1=k^3\quad\times\quad \frac{(k^{3q-3}-1)(k^{3q}+k^3+1)}{k^6+k^3+1}$ .

As before, if q mod 6 = 1, the small denominator polynomial divides the left-hand factor of the numerator. If q mod 6 = 5, the small denominator polynomial divides the right-hand factor of the numerator. So, it might be more correct to view this as two cases:

$\frac{(k^{9q}-1)(k^3-1)}{(k^9-1)(k^{3q}-1)}-1=k^3\quad\times\quad \frac{k^{3q-3}-1}{k^6+k^3+1}\quad\times\quad(k^{3q}+k^3+1), \quad q\equiv 1\pmod 6$ .

$\frac{(k^{9q}-1)(k^3-1)}{(k^9-1)(k^{3q}-1)}-1=k^3\quad\times\quad (k^{3q-3}-1)\quad\times\quad\frac{k^{3q}+k^3+1}{k^6+k^3+1}, \quad q\equiv 5\pmod 6$ .

As before, the "big primitive" contains about half the digits of N.

The middle factor, k^(3q-3)-1, can be factored into the product of a set of cyclotomic polynomials of order d, where d divides 3q-3. If 3q-3 has many factors, there will be many algebraic factors of k^(3q-3)-1.

The term k^6+k^3+1 represents the cyclotomic polynomial of order 9. So, if q mod 6 = 1, just toss out that one cyclotomic polynomial. Or if q mod 6 = 5, provide the quotient to factordb as the "big primitive".

The product of all the cyclotomic polynomials will contain about half the digits of N.

In case there's a typo in my formulas, here is one example.

The number 1301^909-1 was added to factordb on October 3, 2017. (k=1301; q=101.) The "primitive" (N) of this number has 1869 digits and was a probable prime. My copy of Primo required 792 seconds (4 cores, 8 threads, i7) to produce the certificate showing the number was prime.

Code:

 (1301^(3*101)+1301^3+1)/(1301^6+1301^3+1),  <---- This is the "big primitive"
 1301^3,  <----- This is the k cubed factor.

 (1301-1),
 (1301+1),
 (1301^3-1)/(1301-1),
 ((1301^2)+1),
 (1301^5-1)/(1301-1),
 (1301^3+1)/(1301+1),
 (1301^5+1)/(1301+1),
 ((1301^2)^3+1)/((1301^2)+1),
 ((1301^(3*5)-1)*(1301-1))/((1301^5-1)*(1301^3-1)),
 ((1301^2)^5+1)/((1301^2)+1),
 (1301^(5^2)-1)/(1301^5-1),
 ((1301^(3*5)+1)*(1301+1))/((1301^5+1)*(1301^3+1)),
 (1301^(5^2)+1)/(1301^5+1),
 (((1301^2)^(3*5)+1)*((1301^2)+1))/(((1301^2)^5+1)*((1301^2)^3+1)),
 ((1301^(5^2*3)-1)*(1301^5-1))/((1301^(5*3)-1)*(1301^(5^2)-1)),
 ((1301^2)^(5^2)+1)/((1301^2)^5+1),
 ((1301^(5^2*3)+1)*(1301^5+1))/((1301^(5*3)+1)*(1301^(5^2)+1)),
 (((1301^2)^(5^2*3)+1)*((1301^2)^5+1))/(((1301^2)^(5*3)+1)*((1301^2)^(5^2)+1))

The lower section shows factors representing the 18 cyclotomic polynomials that multiply to k^300-1. (I represent these factors in product/quotient form because the form is much more compact than the traditional polynomial form.)

After submitting these algebraic factors, the primitive minus 1 was completely factored, aside from the "big primitive". Even if the biggest cyclotomic factor (a c250) hadn't factored itself, the smaller algebraic primitives would have been sufficient to use the N-1 method to prove primality.

The folks clearing the probable primes have done an admirable job, so it's getting hard to find PRP's that could use N-1 proofs.

If anyone is interested, It should be fairly obvious how to extending the equations to cover exponents of the form 27q or 81q or etc.

The formulae for primitives from k^3q+1 and k^9q+1 are extremely similar to to the formulae I have provided for k^3q-1 and k^9q-1. (Just a couple of sign changes.) The constant (+1) term of the trinomial in the numerator changes sign (to -1). And the middle term of the trinomial in the denominator changes sign. (Which means those denominator terms are no longer the 3rd and 9th order cyclotomic polynomials -- they are now the 6th and 18th order cyclotomic polynomials.)

rcv · 2017-10-28, 04:49

Quote:

Originally Posted by rcv

The formulae for primitives from k^3q+1 and k^9q+1 are extremely similar to to the formulae I have provided for k^3q-1 and k^9q-1. (Just a couple of sign changes.) The constant (+1) term of the trinomial in the numerator changes sign (to -1). And the middle term of the trinomial in the denominator changes sign. (Which means those denominator terms are no longer the 3rd and 9th order cyclotomic polynomials -- they are now the 6th and 18th order cyclotomic polynomials.)

The left-hand side of the equation must also be tweaked to represent the sign change in the primitive of k^3q+1 and k^9q+1 (from k^3q-1 and k^9q-1). For each of the binomials in the numerator and the denominator of the left-hand side, the sign of the constant (-1) must be changed (to +1).

rcv · 2017-10-30, 04:12

A fun one. And presently the 5th largest in the combined N-1/N+1 category at factordb.

A 4385-digit number 579^(3*23^2)-1, a was added to factordb on September 30, 2017. It's algebraic primitive, (579^1587-1)*(579^23-1)/(579^529-1)/(579^69-1), a probable prime of 2796 digits, was factored out within 24 hours.

Using a minor extension of the methods of my previous post, I decided to give the N-1 method a shot. The primitive minus 1, (579^1587-1)*(579^23-1)/(579^529-1)/(579^69-1)-1 was a new number to factordb, yesterday afternoon. I submitted the algebraic factors:

Code:

579^(23^1), 
(579^(23^(1+1))+579^(23^1)+1)/(579^(2*23^1)+579^(23^1)+1), 

(579-1), 
(579+1), 
(579^11-1)/(579-1), 
(579^11+1)/(579+1), 
(579^23-1)/(579-1), 
(579^23+1)/(579+1), 
((579^(11*23)-1)*(579-1))/((579^23-1)*(579^11-1)), 
((579^(11*23)+1)*(579+1))/((579^23+1)*(579^11+1))

Not enough, but tantalizingly close. I collected a 24-digit factor of 579^243-1 from myfactorcollection.mooo.com, which was missing from factordb.com. Still not enough.

The 5th B1=2k curve gave me a 14-digit factor from the c1332. The "Proof" button was present, but it only got this prp2796 to a 99.58% proof.

Finally, almost before I could blink, yafu's rho method and then it's PM1 method found 8- and 9-digit factors from N+1. This time, the "Proof" button had enough information:

Code:

Primality testing (579^1587-1)*(579^23-1)/(579^529-1)/(579^69-1) [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 19
Running N+1 test using discriminant 41, base 12+sqrt(41)
Calling N-1 BLS with factored part 32.82% and helper 1.71% (100.18% proof) (579^1587-1)*(579^23-1)/(579^529-1)/(579^69-1) is prime! (0.3883s+0.0001s

chris2be8 · 2017-12-21, 19:42

Proving http://factordb.com/index.php?id=1100000001076669695 (300 digits) will enable a N-1 proof that (7726567607203^53-1)/7726567607202 http://factordb.com/index.php?id=1100000001076616385 (671 digits) is prime. It's 32.465% factored now so I tried a little ECM on the other algebraic factor, no luck.

Chris

paulunderwood · 2017-12-21, 20:15

Quote:

Originally Posted by chris2be8

Proving http://factordb.com/index.php?id=1100000001076669695 (300 digits) will enable a N-1 proof that (7726567607203^53-1)/7726567607202 http://factordb.com/index.php?id=1100000001076616385 (671 digits) is prime. It's 32.465% factored now so I tried a little ECM on the other algebraic factor, no luck.

Chris

I am a little confused. What is "32.465% factored"? Have you tried for N+1 factors -- so that a combined N-1/N+1 test can be applied? Have you thought of using Konyagin-Pomerance, which is good for 30%?

chris2be8 · 2017-12-22, 16:35

Quote:

Originally Posted by paulunderwood

I am a little confused. What is "32.465% factored"? Have you tried for N+1 factors -- so that a combined N-1/N+1 test can be applied? Have you thought of using Konyagin-Pomerance, which is good for 30%?

I meant that factordb said (7726567607203^53-1)/7726567607202-1 was 32.465% factored.

I tried for N+1 factors but could not find enough to make a combined test work.

Factordb doesn't use Konyagin-Pomerance so that's not an option (it's been suggested as an enhancement some years ago).

Chris

chris2be8 · 2017-12-28, 19:51

Proving http://factordb.com/index.php?id=1100000001079250125 (454 digits) will enable a N-1 proof that (715^1381-1)/714 http://factordb.com/index.php?id=1100000001021743662 (3939 digits) is prime.

Chris

2017-10-26, 02:04	#342
Dylan14 "Dylan" Mar 2017 3·193 Posts	3^2225-3^225-1 has been proven prime by factoring 3^2225-3^225 to sufficient depth. Last fiddled with by Dylan14 on 2017-10-26 at 02:09 Reason: links didn’t work

2017-10-27, 18:40	#346
rcv Dec 2011 143₁₀ Posts	Following up on my post from a couple of days ago... I don't think I have had a successful N-1 factorization of a primitive from a number of the form k^n+/-1. when 3 is not a divisor of n or if n is divisible by 3 or more distinct prime factors (including the 3). Although I haven't proven that it's always true, the "big primitive" gets more than 2/3 of the total number of digits. Yes, you might get lucky, but I can't dependably count on being able to use the N-1 method in the cases noted above. With that said, I'll extend my "cookbook" formula to finding the algebraic factors of the primitive minus 1 for primitives from numbers of the form k^(9q)-1. For the very special case of n=9q, where q is a distinct odd prime not equal to 3, the N-1 term can be factored as follows: $\frac{(k^{9q}-1)(k^3-1)}{(k^9-1)(k^{3q}-1)}-1=k^3\quad\times\quad \frac{(k^{3q-3}-1)(k^{3q}+k^3+1)}{k^6+k^3+1}$ . As before, if q mod 6 = 1, the small denominator polynomial divides the left-hand factor of the numerator. If q mod 6 = 5, the small denominator polynomial divides the right-hand factor of the numerator. So, it might be more correct to view this as two cases: $\frac{(k^{9q}-1)(k^3-1)}{(k^9-1)(k^{3q}-1)}-1=k^3\quad\times\quad \frac{k^{3q-3}-1}{k^6+k^3+1}\quad\times\quad(k^{3q}+k^3+1), \quad q\equiv 1\pmod 6$ . $\frac{(k^{9q}-1)(k^3-1)}{(k^9-1)(k^{3q}-1)}-1=k^3\quad\times\quad (k^{3q-3}-1)\quad\times\quad\frac{k^{3q}+k^3+1}{k^6+k^3+1}, \quad q\equiv 5\pmod 6$ . As before, the "big primitive" contains about half the digits of N. The middle factor, k^(3q-3)-1, can be factored into the product of a set of cyclotomic polynomials of order d, where d divides 3q-3. If 3q-3 has many factors, there will be many algebraic factors of k^(3q-3)-1. The term k^6+k^3+1 represents the cyclotomic polynomial of order 9. So, if q mod 6 = 1, just toss out that one cyclotomic polynomial. Or if q mod 6 = 5, provide the quotient to factordb as the "big primitive". The product of all the cyclotomic polynomials will contain about half the digits of N. In case there's a typo in my formulas, here is one example. The number 1301^909-1 was added to factordb on October 3, 2017. (k=1301; q=101.) The "primitive" (N) of this number has 1869 digits and was a probable prime. My copy of Primo required 792 seconds (4 cores, 8 threads, i7) to produce the certificate showing the number was prime. Code: (1301^(3101)+1301^3+1)/(1301^6+1301^3+1), <---- This is the "big primitive" 1301^3, <----- This is the k cubed factor. (1301-1), (1301+1), (1301^3-1)/(1301-1), ((1301^2)+1), (1301^5-1)/(1301-1), (1301^3+1)/(1301+1), (1301^5+1)/(1301+1), ((1301^2)^3+1)/((1301^2)+1), ((1301^(35)-1)(1301-1))/((1301^5-1)(1301^3-1)), ((1301^2)^5+1)/((1301^2)+1), (1301^(5^2)-1)/(1301^5-1), ((1301^(35)+1)(1301+1))/((1301^5+1)(1301^3+1)), (1301^(5^2)+1)/(1301^5+1), (((1301^2)^(35)+1)((1301^2)+1))/(((1301^2)^5+1)((1301^2)^3+1)), ((1301^(5^23)-1)(1301^5-1))/((1301^(53)-1)(1301^(5^2)-1)), ((1301^2)^(5^2)+1)/((1301^2)^5+1), ((1301^(5^23)+1)(1301^5+1))/((1301^(53)+1)(1301^(5^2)+1)), (((1301^2)^(5^23)+1)((1301^2)^5+1))/(((1301^2)^(53)+1)*((1301^2)^(5^2)+1)) The lower section shows factors representing the 18 cyclotomic polynomials that multiply to k^300-1. (I represent these factors in product/quotient form because the form is much more compact than the traditional polynomial form.) After submitting these algebraic factors, the primitive minus 1 was completely factored, aside from the "big primitive". Even if the biggest cyclotomic factor (a c250) hadn't factored itself, the smaller algebraic primitives would have been sufficient to use the N-1 method to prove primality. The folks clearing the probable primes have done an admirable job, so it's getting hard to find PRP's that could use N-1 proofs. If anyone is interested, It should be fairly obvious how to extending the equations to cover exponents of the form 27q or 81q or etc. The formulae for primitives from k^3q+1 and k^9q+1 are extremely similar to to the formulae I have provided for k^3q-1 and k^9q-1. (Just a couple of sign changes.) The constant (+1) term of the trinomial in the numerator changes sign (to -1). And the middle term of the trinomial in the denominator changes sign. (Which means those denominator terms are no longer the 3rd and 9th order cyclotomic polynomials -- they are now the 6th and 18th order cyclotomic polynomials.)

2017-10-30, 04:12	#348
rcv Dec 2011 11×13 Posts	A fun one. And presently the 5th largest in the combined N-1/N+1 category at factordb. A 4385-digit number 579^(323^2)-1, a was added to factordb on September 30, 2017. It's algebraic primitive, (579^1587-1)(579^23-1)/(579^529-1)/(579^69-1), a probable prime of 2796 digits, was factored out within 24 hours. Using a minor extension of the methods of my previous post, I decided to give the N-1 method a shot. The primitive minus 1, (579^1587-1)(579^23-1)/(579^529-1)/(579^69-1)-1 was a new number to factordb, yesterday afternoon. I submitted the algebraic factors: Code: 579^(23^1), (579^(23^(1+1))+579^(23^1)+1)/(579^(223^1)+579^(23^1)+1), (579-1), (579+1), (579^11-1)/(579-1), (579^11+1)/(579+1), (579^23-1)/(579-1), (579^23+1)/(579+1), ((579^(1123)-1)(579-1))/((579^23-1)(579^11-1)), ((579^(1123)+1)(579+1))/((579^23+1)(579^11+1)) Not enough, but tantalizingly close. I collected a 24-digit factor of 579^243-1 from myfactorcollection.mooo.com, which was missing from factordb.com. Still not enough. The 5th B1=2k curve gave me a 14-digit factor from the c1332. The "Proof" button was present, but it only got this prp2796 to a 99.58% proof. Finally, almost before I could blink, yafu's rho method and then it's PM1 method found 8- and 9-digit factors from N+1. This time, the "Proof" button had enough information: Code: Primality testing (579^1587-1)(579^23-1)/(579^529-1)/(579^69-1) [N-1/N+1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 19 Running N+1 test using discriminant 41, base 12+sqrt(41) Calling N-1 BLS with factored part 32.82% and helper 1.71% (100.18% proof) (579^1587-1)(579^23-1)/(579^529-1)/(579^69-1) is prime! (0.3883s+0.0001s Last fiddled with by rcv on 2017-10-30 at 04:16

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

2017-12-21, 19:42	#349
chris2be8 Sep 2009 2·1,039 Posts	Proving http://factordb.com/index.php?id=1100000001076669695 (300 digits) will enable a N-1 proof that (7726567607203^53-1)/7726567607202 http://factordb.com/index.php?id=1100000001076616385 (671 digits) is prime. It's 32.465% factored now so I tried a little ECM on the other algebraic factor, no luck. Chris

2017-12-28, 19:51	#352
chris2be8 Sep 2009 2·1,039 Posts	Proving http://factordb.com/index.php?id=1100000001079250125 (454 digits) will enable a N-1 proof that (715^1381-1)/714 http://factordb.com/index.php?id=1100000001021743662 (3939 digits) is prime. Chris