2
$\begingroup$

I am trying to completely factor numbers of the form $b^n±1$ for some base $b$ $<$ $2^{32}$ and $n$ prime. I am doing this by trial dividing $b^n±1$ to $2^{32}$ and probable prime testing the remaining factor after dividing by all small factors $<$ $2^{32}$. This is for all prime $n$ $<$ $100000$.

Using the method and definition above, what is the chance that I will "completely factor" $b^n±1$ with random prime $n < 100000$ and a certain base $b$ ($±$ sign is fixed with $+1$ or $-1$)?

I find the theoretical value quite complicated for this, does anyone know one? Thanks.

$\endgroup$
2
$\begingroup$

You'll want to look at the Cunningham Project. $(12^{271} - 1)$ is divisible by 1858123207899504867154659615995726699906428378285166639532930145263805746638767329880410679791959, for example.

For $2^n-1$, on June 17, 2015, $n=991$ was completely factored, the last exponent under 1000. More recently, it looks like all the exponents under 1000 for $2^n+1$ have been factored.

Factorizing Mersenne Numbers

Based on the data available there, I'm going to say the odds that you'll find nice unknown complete small prime factorizations for any numbers of this type are zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.