So if 2^phi(n) = 1, then 2^(2 * phi(n)) = 1 and 2^(3 * phi(n)) = 1 and so on, so we really only need to know the value of 2^t mod phi(n). We can compute this value in O(log(t)) operations via repeated squaring, and once we know this value (let's call it k), then we just need to compute 2^k mod n to finish, which again, can be done quickly using repeated squaring.
Here's a quick demo in python:
$ python
>>> p = 8721676787107355947610787701585837629266743108012786178142468507932506290346645194233003705268505408163930982434418938387386290453411395078603729114734341
>>> q = 8903989072246145056499086678843460912573461209473391355874543630090691433843393509873230695095738299681258115825746186699033768361727241007153178256782969
>>> n = p * q
>>> phi = (p - 1)*(q - 1)
>>> t = 1000
>>> x = 2
>>> for _ in range(t):
... x = (x*x) % n
...
>>> x
71836162857086924742436011377120654460634075903529962708552402169419490230741381078707287421912274480993140536800209014695404113617083557073377609336198536584108952782855884250603887258689220754542881131492565231964253742236040236745851352559544932355488898852071685626631281275266638607487563485757328752568L
>>> k = pow(2, t, phi)
>>> y = pow(2, k, n)
>>> y
71836162857086924742436011377120654460634075903529962708552402169419490230741381078707287421912274480993140536800209014695404113617083557073377609336198536584108952782855884250603887258689220754542881131492565231964253742236040236745851352559544932355488898852071685626631281275266638607487563485757328752568L
>>> x == y
True
>>>
The key here (as in the RSA cryptosystem) is that we have no way of computing phi(n) without knowing the factorization of n.
We want to find the value of 2^(2^t) mod n where n = pq. It's a well known number-theoretic fact that 2^phi(n) mod n = 1, where phi is the Euler totient function (https://en.wikipedia.org/wiki/Euler%27s_totient_function).
This theorem is called Euler's theorem (https://en.wikipedia.org/wiki/Euler%27s_theorem). For n = pq, phi(n) = (p-1)(q-1)
So if 2^phi(n) = 1, then 2^(2 * phi(n)) = 1 and 2^(3 * phi(n)) = 1 and so on, so we really only need to know the value of 2^t mod phi(n). We can compute this value in O(log(t)) operations via repeated squaring, and once we know this value (let's call it k), then we just need to compute 2^k mod n to finish, which again, can be done quickly using repeated squaring.
Here's a quick demo in python:
The key here (as in the RSA cryptosystem) is that we have no way of computing phi(n) without knowing the factorization of n.