The number may be very large (think: much bigger than 2^64). The reason it’s possible to compute these in logarithmic time (ie linear in the number of bits of t

The number may be very large (think: much bigger than 2^64). The reason it’s possible to compute these in logarithmic time (ie linear in the number of bits of the key) is the same reason that it is possible to compute a^b (mod c) even when b is very large: there are operations in elliptic curves akin to multiplying and squaring so a^(2b_1 + b_2) = a^(b_2) (a^2)^(b_1) can have the cost of computing a^(b_1) (say b_1 is 0 or 1, so this is constant), the cost of a multiply (constant), the cost of a square (constant), and the cost of an exponentiation of a number with one less bit, hence by induction the cost is linear in the number of bits.