One is the actual cost from the start node to the current node, one is a heuristic of the straight distance from the current node to the target disregarding any Wall.
A-Star uses the sum of those two, to determine what the most promising Node to continue with is!

It would be more interesting if this kata was about full transcription.

Which complexity is enough to solve this kata?

Insufficient testing...

But where are the solutions for 23, 25-29, 38-40, &c.?

Awaiting Python version :(

Very strange kata.

What for are two costs used?

Yes, the description is really not clear. I guessed the aim only thanks to the test code.

https://en.wikipedia.org/wiki/Elliptic_curve_primality#Example_of_Atkin%E2%80%93Morain_ECPP

If you would like to learn more about elliptic curves per se, I can recommend this article:
https://web.archive.org/web/20210513235048/https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

Any link to read about it? Thanks.

I am interesting whether anyone did this through elliptic curves? I was too lazy for something like that.