Diffie-Hellman key exchange, choosing the secret key

Question

I very well understand the Diffie-Hellman key exchange method, at least I think I do. And I was trying to implement it to try it out.

I went and calculated a very large prime number $p$ about $400$ digits long. And I set $g$ to $5$.

I generated a random secret number $a$, for example : "$42523434$".

The problem I'm facing is when I calculate $g^a \operatorname{mod} p$, $g^a$ in particular, it seems to take my computer forever to calculate it, so it seems to be impractical to give $a$ such a number so I went for a smaller number (a five digit number) which takes about a second or two to calculate.

So now we have $A=g^a \operatorname{mod} p$, with the eavesdropper knowing $g$, $p$, and $A$.

But wouldn't it be possible to brute force $a$ by trying all $100000$ combinations until what he calculates matches $A$ which wouldn't take him that long if he good computing powers? A solution to this would be increasing $a$ but increasing $a$ would make the exchange take so long that it wouldn't be a good method to exchange the keys.

Edit:

We can compute g^a mod p using such a program:

for x in range(1,100000):
    if(((g**x)%p)==A):
        print x

Answer 1

You can increase the exponent, just use fast exponentiation algorithm. It is probably not natively implented in the exponential function you are using. And if you are using it, then you need a computer with processor that is not from the early 90's.

An example of such algorithm -

Function exp_by_squaring_iterative(g, e(xponent),p(rime))

if n = 0 then return 1
y := 1;
while n > 1 do
  if n is even then 
    e := (e * e) mod p;
    n := n / 2;
  else
    y := (e * y) mod p;
    e := (e * e) mod p;
    n := (n – 1) / 2;
return e * y

Algorithm taken from here https://en.wikipedia.org/wiki/Exponentiation_by_squaring, I just added the mod part and renamed some variables and removed the negative part, assuming you do not need to compute negative powers.

The other problem may be in implementation of the arbitrarily large numbers in the language you are using, in which case I recommend searching for a better library or language.

However this probably should have been posted on a crypto exchange or something to do with computers and programming languages, because I am convinced your problems are straightforward implementations of the arithmetic operations. But because you did not do that, I guess your implementation of the key exchange algorithm was done naively and that the above algorithm might help you to increase the exponent to any desired size with acceptable computational time.