'Pseudocubality' - fast tests for large possible-cubes

[CRGreathouse]

'Pseudocubality' -- fast tests for large possible-cubes

I'm looking for a way to quickly show that a huge number is not a cube. The numbers are of the form a^b + c^d where a and c are less than a million and b and d are under a hundred (give or take on both). a and c are also known to be odd, and the exponents are at least 3.

At the moment I'm checking a+c mod 8 (it must be 0) and the sum of the powers, calculated with fast modular exponentiation, mod 9, 13, and 19. (I'm also checking mod 7, but this doesn't seem to help -- any ideas on why that is the case?)

What I want are more tests, since far too many non-cubes slip through these tests. Since most of the inputs will be handled by one of these, the test doesn't have to be blazingly fast -- although faster is better, to be sure.

Is there a cubic reciprocity test that can practically handle numbers of this size? Can it be done (like modular exponentiation) without expanding the numbers?

 

[Hurkyl]

http://en.wikipedia.org/wiki/Cubic_reciprocity

 

[Hurkyl]

Is it not enough to simply check modulo more primes of the form 3k+1?

I suspect you could do the computation faster if you didn't check 7, 9, 13, and 19 separately... but instead computed it once modulo 7*9*13*19, and uesd that to compute the residue modulo your other moduli. (Or even just stored an array indicating whether an element modulo 7*9*13*19 is a cube)

 

[Hurkyl]

To save on modular exponentiation, observe that

(a^b) mod 13 = a^(b mod 12) mod 13

Even better, you could avoid doing any multiplies at all -- just store a 13 by 12 lookup table of the value of a^b. (Note that, since you have a fixed modulus, there are clever ways to compute the remainder without doing any division)

Even better -- why use a clever way to compute the remainder when you can just use a lookup table? You could store an array of the value of x mod 13 for every x under 2^20, and x mod 12 for x under 2^10. It's unclear to me which would win.

 

[CRGreathouse]

Is it not enough to simply check modulo more primes of the form 3k+1?

Not really; the higher the primes get the less useful they are, and the more modulus operations are needed.

I suspect you could do the computation faster if you didn't check 7, 9, 13, and 19 separately... but instead computed it once modulo 7*9*13*19, and uesd that to compute the residue modulo your other moduli. (Or even just stored an array indicating whether an element modulo 7*9*13*19 is a cube)

I'm already doing this, actually. It seemed like an obvious speedup, so I took it. The array hasn't proved useful yet, since the later tests don't come up much.

 

[CRGreathouse]

http://en.wikipedia.org/wiki/Cubic_reciprocity

I've read that and a number of other sources on cubic reciprocity (although I'll blush to admit I didn't look it up in my Ireland & Rosen), but I'm actually having trouble figuring out how to implement that test quickly for large numbers.

I'm still working on it.

 

[Hurkyl]

Not really; the higher the primes get the less useful they are, and the more modulus operations are needed.

This doesn't sound right -- a random number modulo a prime p = 3k+1 has a precisely one in three chance of being a cube, I would expect that each additional prime you tried kills off another 66% of the false positives. If either exponent you're using is relatively prime to 3k and the corresponding base is uniformly distributed mod p, then your final number should be uniformly distributed mod p!

So, I'm surprised to hear that larger primes are less useful. Nor can I explain why 7 isn't helping. Admittedly, I'm more inclined to suspect a bug in the program than number theoretic reasons... I'm going to have to code this up later, so that I can see it for myself!

 

[CRGreathouse]

This doesn't sound right -- a random number modulo a prime p = 3k+1 has a precisely one in three chance of being a cube, I would expect that each additional prime you tried kills off another 66% of the false positives.

Yes, but the larger the primes the more tests are needed to check the residue classes.

What I'd really like is to find some conditions that knock out 'most' in some sense of the false positives, then a test that will remove 'almost all' of the false positives. The whole program is designed to search a very large space for cubes -- although this is of itself just a multi-day preprocessing step for a larger search for powers.

 

[Hurkyl]

Yes, but the larger the primes the more tests are needed to check the residue classes.

I'm not sure what you mean -- as long as you stick to small primes, once you have the residue modulo the prime, it's just a single table lookup to tell if you have a cube or not. It would take a small miracle to pass the first 100 tests, so it doesn't really matter if you take a millisecond to test the next few thousand primes. (Or whatever method you intend to use to decide if it really is a cube)