I take a known prime and prove it to be a composite (..or maybe need help?)

[Batalov]

Originally Posted by danaj

What am I missing that makes that important enough to make a post about? It takes only a few milliseconds to determine that result.

You are not missing anything. The poster is an attention-seeker or a lame bot.

[TheMawn]

Tell us more about Patterns.

[danaj]

Originally Posted by CRGreathouse

Is there a special form for the divisors of a number of the form a*b^c + d, in cases like this where c is relatively large?

Short answer: PFGW claims it can optimize this with d "up to 42-bits" but I know nothing at all about the details. My pretests are just using basic trial division (gcd for tiny primes, then simple treesieve for larger).

In the case of the composite mentioned, there is a small factor so easily caught -- it takes under 0.04s for my is_prime to find it just using simple trial division tests based on the input size. OpenFPGW and Pari/GP don't do much trial division, but still don't take very long for the first PRP test to indicate composite (~30s and 4.5 minutes respectively). If I skip the pretests and force just BPSW or base-2 SPRP it's 2.5min for ntheory (as expected, PFGW is much faster at this size).

I don't think LLR would cover this, especially not with the /3. Ignoring the /3, PFGW-3.7.7 indicates it can optimize k * b^n +/- c for c to 42-bits. I haven't looked into it at all however -- the LLR code I've added to my software is braindead simple, just doing b=2, c = -1, k = not-div-by-3. c=+1 is easily done via BLS75-T5. Riesel discusses the k-div-3 case for k*2^n-1 Bosma (1993) has some info, and there's a good post from a few years ago on this forum that has a lot of details, but I haven't gone into it (and it doesn't answer your question anyway).

Berrizbeitia et al. have a generalization to A*m^s+w where w has restrictions.

[science_man_88]

Originally Posted by CRGreathouse

Is there a special form for the divisors of a number of the form a*b^c + d, in cases like this where c is relatively large?

I hope that's rhetorical if(gcd(a,d)!=1 or gcd(b,d)!=1, then gcd(a,d) or gcd(b,d) is a divsor) or a typo.

[CRGreathouse]

Originally Posted by science_man_88

I hope that's rhetorical if(gcd(a,d)!=1 or gcd(b,d)!=1, then gcd(a,d) or gcd(b,d) is a divsor) or a typo.

In this case (a = 23, b = 10, c = 46554, d = -11) both GCDs are 1. But I'm not talking about finding a single factor but a class of factors, just like prime factors of Mersenne numbers have a special form. In this case I checked for divisibility by all small primes directly (modular exponentiation) but I wondered if there was a faster way. (I was pretty sure that there was one and that people here would know more about this than I do.)

[CRGreathouse]

Originally Posted by danaj

In the case of the composite mentioned, there is a small factor so easily caught -- it takes under 0.04s for my is_prime to find it just using simple trial division tests based on the input size.

My experience was similar -- 57ms with modular trial division in PARI/GP*, or 92ms using a big GCD.

* Of course if I did it in PARI directly it would be a good bit faster but I just did it in gp.

Originally Posted by danaj

OpenFPGW and Pari/GP don't do much trial division, but still don't take very long for the first PRP test to indicate composite (~30s and 4.5 minutes respectively). If I skip the pretests and force just BPSW or base-2 SPRP it's 2.5min for ntheory (as expected, PFGW is much faster at this size).

I don't think LLR would cover this, especially not with the /3. Ignoring the /3, PFGW-3.7.7 indicates it can optimize k * b^n +/- c for c to 42-bits. I haven't looked into it at all however -- the LLR code I've added to my software is braindead simple, just doing b=2, c = -1, k = not-div-by-3. c=+1 is easily done via BLS75-T5. Riesel discusses the k-div-3 case for k*2^n-1 Bosma (1993) has some info, and there's a good post from a few years ago on this forum that has a lot of details, but I haven't gone into it (and it doesn't answer your question anyway).

Berrizbeitia et al. have a generalization to A*m^s+w where w has restrictions.

That's interesting, but you're talking about primality/compositeness testing, while I'm talking about (partial) factorization. That is: I want the equivalent of the 2kp + 1 for Mersenne numbers, not the equivalent of LLR/BLS.

[danaj]

Originally Posted by CRGreathouse

That's interesting, but you're talking about primality/compositeness testing, while I'm talking about (partial) factorization. That is: I want the equivalent of the 2kp + 1 for Mersenne numbers, not the equivalent of LLR/BLS.

I realized that partway through writing my reply, but kept on with it anyway . I claim ignorance of special factor forms, but would enjoy seeing any positive responses.

[R.D. Silverman]

Originally Posted by danaj

What am I missing that makes that important enough to make a post about? It takes only a few milliseconds to determine that result.

The last time that I dared to question the purpose of posting a result, I was (to summarize)
accused of being an asshole by Gordon in a fairly lengthy diatribe.

Allow me to point out that there has been no similar reply here.......

[LaurV]

To be back on track: just pointing out that, according with factorDB, this number is known to be composite since (about) March 2011. As Batalov said, the guy is either innocent (in the bad sense) or a bot.

[edit: I am also interested in the discussion started by CRG's question, for some "general" case]

[storflyt32]

Quoting here.

Batalov said:

I am moving this discussion to "Homework help".
It has nothing to do with new Fermat Factors.

If you take a hammer and a screw, hammer the screw into the wall and declare: "the hammer is not working and the screw is all bent", -- this whole thing only demonstrates that you use a hammer where you need a screwdriver.

-

Oh, definitely we missed some factors between the P252 and the P564 (Fermat).

Or, what the heck else.

Getting back to it, of course.

[TheMawn]

Originally Posted by storflyt32

Quoting here.

Batalov said:

I am moving this discussion to "Homework help".
It has nothing to do with new Fermat Factors.

If you take a hammer and a screw, hammer the screw into the wall and declare: "the hammer is not working and the screw is all bent", -- this whole thing only demonstrates that you use a hammer where you need a screwdriver.

-

Oh, definitely we missed some factors between the P252 and the P564 (Fermat).

Or, what the heck else.

Getting back to it, of course.

And that pretty much seals it. Bot.