Add N-1/N+1 primality testing and P-1/P+1 integer factoring to the integer factorization calculator

[xayahrainie4793]

Currently, for the integer factorization calculator, "Prime" (primality testing) only uses the Baillie-PSW probable primality testing (a probable primality testing, i.e. they might be pseudoprimes) and the ECPP primality testing, and "Factor" (integer factoring) only uses the trial division and the algebraic factorization (e.g. factor the number 25*36^166-1 to (5*6^166-1) * (5*6^166+1), and continue to factor the 118-digit composite cofactor (5*6^166-1)/1052921468429 and the 130-digit composite cofactor 5*6^166+1) and the ECM integer factoring, I think that "Prime" (primality testing) can also use the N-1/N+1 primality testing if N-1 or/and N+1 can be >= 1/3 factored (where N is the given number), and the "Factor" (integer factoring) can also use the P-1/P+1 integer factoring if P-1 or/and P+1 is smooth (where P is the prime factor of the given number).

[xayahrainie4793]

Also, I found that the integer factorization calculator only detects the algebraic factorization of difference-of-two-squares (try 10^300-4) and x^4+4*y^4 (try 10^300+4), but does not detects the algebraic factorization of sum/difference-of-two-cubes or higher powers (sum/difference-of-two-5th-powers, sum/difference-of-two-7th-powers, sum/difference-of-two-11th-powers, etc.), e.g. you can try 10^300+8, 10^300-8, 10^300+32, 10^300-32, it does not return their algebraic factors.

[alpertron]

With respect to your last post, I've just implemented it for exponents up to 18. Please refresh the web page and try it.

[xayahrainie4793]

Thanks, I have a page for the "primitive" factorization of x^n+-k*y^n for n up to 36, e.g.

• x^2-9*y^2 = (x - 3*y) * (x + 3*y) is not listed since it is a subset of x^2-y^2 = (x - y) * (x + y)
• x^3+8*y^3 = (x + 2*y) * (x^2 - 2*y*x + 4*y^2) is not listed since it is a subset of x^3+y^3 = (x + y) * (x^2 - y*x + y^2)
• x^6+y^6 = (x^2 + y^2) * (x^4 - y^2*x^2 + y^4) is not listed since it is a subset of x^3+y^3 = (x + y) * (x^2 - y*x + y^2)
• x^8+4*y^8 = (x^4 - 2*y^2*x^2 + 2*y^4) * (x^4 + 2*y^2*x^2 + 2*y^4) is not listed since it is a subset of x^4+4*y^4 = (x^2 - 2*y*x + 2*y^2) * (x^2 + 2*y*x + 2*y^2)

[alpertron]

I've just uploaded a new version that includes the other algebraic factorizations for exponents up to 18. Please refresh the page and try again.

[xayahrainie4793]

I try 8×18²⁹⁹+12 (the N+1 of the 547th minimal prime in base b = 18, 80₂₉₈B = 8×18²⁹⁹+11) (which has sum-of-two-cubes factorization and can be factored to 12 × (6×18⁹⁹+1) × (2×18¹⁹⁹−6×18⁹⁹+1)) and 9×21²⁹⁷+243 (the N−1 of the 13316th minimal prime in base b = 21, 90₂₉₅BD = 9×21²⁹⁷+244) (which has sum-of-two-cubes factorization and can be factored to 9 × (21⁹⁹+3) × (21¹⁹⁸−3×21⁹⁹+9)), they have "hidden" algebraic factors, but the calculator does not detect them (the interest of these two numbers are from my minimal prime project https://github.com/xayahrainie4793/minimal-elements-of-the-prime-numbers), the "hidden" algebraic factors is like (25*10^298+8)/3 (see https://stdkmd.net/nrr/8/83336.htm#N298), which has sum-of-two-5th-powers factorization, but when I try (25*10^298+8)/3, the calculator does not detect its algebraic factors.

[alpertron]

That is a very specific factorization. I do not see how the calculator can detect that the number has the form 8*18^2*x^3+12 where x = 18^99.

In general, I think it is difficult to write the number in the form A*x^e + B*y^e. If you have the procedure, please let me know. At this moment, I write it in the form x^e + B*y^e, which is easier to find.