Large exponentials and 8-bit PIC processors
Any math can be done on any processor.  The only question is how many operations, and therefore how much time it will take.

515 = 234.8, so requires at least 35 bits to express.  Bits come in bytes of 8 each on a PIC 18, so you'd use 40 bits or 5 bytes to represent this value.

So all you have to write is a routine that multiplies a 1 byte number by a 5 byte number into the 5 byte number.  This is actually pretty easy since the PIC 18 has a hardware 8x8 into 16 bit multiplier.  Basically, you multiply the one input byte by each of the wide number bytes separately and add up the results.  I'd probably write this as a unrolled loop, so the guts would be 5 sets of a multiply and two adds, or 15 instructions.

Added

As Dan D correctly pointed out in a comment, I forgot to address the modulo part.  That is significantly more complicated than computing 515.  Basically, you do a divide by 23 and keep only the remainder.  You may be able to save a few instructions because you don't need the quotient at the end, but mostly you still have to write a 5-byte divided by 1-byte with 1-byte remainder algorithm.

Again, this can all be done on a PIC 18 or other small processors, but will take many more instructions than on a processor that can manipulate 40 bit numbers natively.