If you have to iterate to find loop size, you might as well use the same loop to generate the private key as a simple multiplication and modulus is cheap:

long findPrivate (long card, long door)

{

while (card != cardPublic)

{

card = (7*card) % 20201227;

door = (doorPublic*door) % 20201227;

}

return door;

}

Sure that gets you the answer, but far from optimal.

For this problem even the most naive solution gives the answer quite quickly, but there are better ways to do it (as someone has mentioned already). If the question had much bigger numbers the naive solution would not have been workable.

If you want to get something to the power of 8 you can do it the naive way and use 7 multiplications and 7 modulus operations, e.g.

x=7

x*=7 ; x%=m;

x*=7 ; x%=m;

x*=7 ; x%=m;

x*=7 ; x%=m;

x*=7 ; x%=m;

x*=7 ; x%=m;

x*=7 ; x%=m;

Or you can do it in 3 multiplications and 3 modulus operations:-

x=7

x*=x ; x%=m; # current value is x^2 mod m

x*=x ; x%=m; # current value is x^4 mod m

x*=x ; x%=m; # current value is x^8 mod m

To raise to an arbitrary exponent you effectively look at the binary representation of the exponent and sometimes multiply in another x before you square the number you have as you go along.

So to raise something to the power 12413864 (for example) you can do 12413863 mulitply/modulus operations, or just ~30 by using the more optimal way.

As always with AoC, you can stop as soon as you've got the answer, or you can choose to delve a little deeper.