Are there any moderately-reliable primality testing algorithms that are simple enough to be done on pen and paper for 512-bit primes?

I'm mostly wondering because I think it'd be cool to teach my daughter (who I'm teaching basic cryptography to) how to exchange secrets over realistically-sized textbook RSA, using nothing but a pen, paper, and dice.

And obviously I don't want to make her go through miller-rabin primality tests hundreds of times before finding even one prime, and I feel like it's cheating to just... hand over pre-made prime numbers.

I don't think even 512 bit multiplication is feasible to do with pen and paper. It's 154 digits. And RSA uses a product of two primes and multiple modular multiplications.

How about teaching programming? Python has big int math and mod exponentiation built-in. Learning how to implement miller-rabin is probably better than doing the purely mechanical work of doing the same arithmetic by hand.

(Although I think Java or C# are better first languages.)

She already knows her way around bash and knows (a very very small amount of) C. Perhaps it would be practical with a TI-83 calculator or something similar?

Maybe I'm just thinking too far forward.

I wonder of TI-BASIC is powerful enough to do that.

@LevKnoblock intuitively speaking I'd say that "Ed521" is "EdDSA on the E-521 curve"

@LevKnoblock github.com/coruus/E521

^ you can use this as a reference (and apparently they call the curve "Ed521" too which means Ed25519 ruined it all because now everybody is confused whether the curve is meant or the signature scheme :/ )

@forest actually, like 2-4 rounds of Miller-Rabin should establish a very high confidence in the primality already

@forest you may want to have a look at this chapter of the handbook of applied crypto (PDF): cacr.uwaterloo.ca/hac/about/chap4.pdf

(it contains primality tests and prime generation strategies)

TI-83 (and 84) I think only supports floating point arithmetic.

I wrote a primality test / prime factorization program in ti-basic as a kid that used a list of primes and the built in gcd function. It worked fine for small numbers but got very slow for larger ones.

"Small" being algebra-2-small numbers, as in < 1000. I could have wrote a more advanced program, but I did gcd because more complex programs were too slow in the interpreter

@FutureSecurity You're right. The 68k is needed for large integer math.

@SEJPM I meant runs on hundreds of candidate numbers, not hundreds of runs on a single candidate number.