What, if anything, can be said about the factors of 2^n - 1 when n is composite?

[alpertron]

Due to Hasse theorem, the prime factor p can be found by ECM if the number p-1+q is smooth with respect to the selected bounds, where the absolute value of q is less than twice the square root of p. The value of q is unknown and depends on p and the elliptic curve being used.

[LaurV]

Originally Posted by alpertron

Due to Hasse theorem, the prime factor p can be found by ECM if the number p-1+q is smooth with respect to the selected bounds, where the absolute value of q is less than twice the square root of p. The value of q is unknown and depends on p and the elliptic curve being used.

Correct.

[alpertron]

For example, in December 1995 Richard Brent found the prime factor p40 of the tenth Fermat number, completing its factorization.

p40 = 9409853205696664168149671432955079744397

The elliptic curve selected has sigma = 48998398, and the group order for the elliptic curve mod p40 can be computed as G = p40 - 1 + 149256697246264631024 that is smooth:

G = 2² * 3 * 5 * 17 * 31² * 53 * 67 * 233 * 739 * 5563 * 7901 * 20201 * 57163 * 309335137

Notice that p40 - 1 = 2² * 7715261 * 304910397901531269264567700073759 so this prime cannot be found using p-1 algorithm.

[rcv]

Originally Posted by LaurV

Thank you, RDS, for the marvelously simple condition for when the intrinsic factor occurs!

Also thank you for the information which leads to a clarification to my post #8 of this thread.

I said formula (1) was the "primitive". To clarify, I believe formula (1) is often called "phi". Where "phi" is usually the full "primitive", but "phi" may be the product of a small prime "intrinsic" times the "primitive". So, correcting formula (1) from my previous post:

The "phi" of that form is

My personal database (of slightly extended Cunningham forms) does have separate phi and primitive columns, so I have no excuse for being so careless with my explanation. An SQL query of my database shows 33 official Cunningham numbers with base 2 (exponent limits of 1300, 1300, and 2600) that possess an intrinsic factor in my database. That may or may not match the official count, but it should give the OP a rough (order of magnitude) estimate of how often intrinsic factors must be considered. (With the RDS-provided condition telling the OP exactly when intrinsic factors must be considered!)

[LaurV]

Originally Posted by alpertron

G = p40 - 1 + 149256697246264631024

Ok, and now you tell, for normal people like us who have no idea, where the 149256697246264631024 comes from?
Hehe...

[alpertron]

For prime numbers of that size, you can compute the group order by using Schoof's algorithm. There are faster algorithms for prime numbers greater than 100 digits, for example Schoof–Elkies–Atkin algorithm.

[Dr Sardonicus]

Originally Posted by alpertron

For example, in December 1995 Richard Brent found the prime factor p40 of the tenth Fermat number, completing its factorization.

p40 = 9409853205696664168149671432955079744397

The elliptic curve selected has sigma = 48998398, and the group order for the elliptic curve mod p40 can be computed as G = p40 - 1 + 149256697246264631024 that is smooth:

G = 2² * 3 * 5 * 17 * 31² * 53 * 67 * 233 * 739 * 5563 * 7901 * 20201 * 57163 * 309335137

Notice that p40 - 1 = 2² * 7715261 * 304910397901531269264567700073759 so this prime cannot be found using p-1 algorithm.

I don't know much at all about ECM. Hmm, I can probably look up the factorization of F₁₀ (google google) Ahh, there it is! (read read)

Two things: In

FACTORIZATION OF THE TENTH FERMAT NUMBER

they refer to the expression p + 1 - q, not p - 1 + q.

Let g = |G| be the order of G. We have g = p + 1 − t, where t satisfies Hasse’s inequality t^2 < 4p. The number of curves with given t can be expressed in terms of the Kronecker class number of t^2 − 4p (see [46]).

Second, the values you cite are for a different number:

In December 1995, using program C with B1 = 370,000, D = 255, e = 6, we found the 40-digit factor

p'₄₀ = 9409853205696664168149671432955079744397

of

p₂₅₂ − 1,

where p₂₅₂ is the largest prime factor of F10 . See §9 for the application to proving primality of p252 . The curve is defined as in §2.3 with

σ = 48998398,

and the group order is

g = 2^2*3*5*17*31^2*53*67*233*739*5563*7901*20201*57163*309335137.

You can check that for this p and g, p + 1 - g = 149256697246264631022.

As to the elliptic curve that found the p40 prime factor of F₁₀,

The group order is

g = p40 + 1 − 3674872259129499038 = 2^2*3^2*5*149*163*197*7187*18311*123677*226133*314263*4677853

[bhelmes]

Dear Charles,

the mersenne numbers are embedded in the quadratic function f(n)=2n²-1
where for all n equal powers of two the f(n) is a mersenne number.

All primes p sieves double periodically the function values of f(n)
p|f(n) -> p|f(n+kp) and p|f(n-kp), k element of N

The mersenne numbers build a folding of this quadratic function.

I think you can use the prime factors of the mersenne numbers in order to make a sieve if you consider the differences between the mersenne numbers based on the regarding n of the quadratic function.

Is it possible to calculate all factors of mersenne numbers
if p of Mp is not a prime ?

It might not be the fastest way.

The result of the factorisation of mersenne numbers
are part of the sieving construction of that quadratic function f(n)=2n^2-1

By the way the function f(n)=2n^2-1 is embedded in the
function f(u,v)=u^2 - v^2 +2uv which seems to be a metric ?

Was it proven that there are infinitive primes p=2n^2-1 ?

Greetings from the primes
Bernhard

[JeppeSN]

Originally Posted by LaurV

This reminds me that long ago I requested eliminating the "exponent must be prime" criteria from mfaktX, or giving the possibility to the user to have a command line switch to disable the primality test - there was the time when I was trying to factor 2^18xx-1 (I forgot the xx, sorry, but it was a composite exponent in 1800's, and right now the FDB looks down too, so I can not look for it) which had (and maybe still has) a composite cofactor of about 300 digits left.

(A long time after.)

I am thinking 2^1891 - 1 because 1891 = 31*61, so that famous primes M31 and M61 are the algebraic factors?

/JeppeSN

[LaurV]

That has a C5xx left, it was not so high, I may be wrong about the "18" part. Grr... I am getting older... Anyhow, the discussion is here on the forum somewhere, but it does not matter anymore.

[CRGreathouse]

Originally Posted by bhelmes

Is it possible to calculate all factors of mersenne numbers
if p of Mp is not a prime ?

In general this is very hard.

Originally Posted by bhelmes

Was it proven that there are infinitive primes p=2n^2-1 ?

No, this is beyond current capabilities.