How to find multiplicative inverse of a very large number when the number and field is divided into parts?

Question

I have 2 numbers a and p ($0<a<p$) and p is prime. Both are of 256 bits. To represent them in a computer, I have divided each number into 4 parts of 64 bits each ($a0, a1, a2, a3$ and $p0, p1, p2, p3$).
How to calculate the multiplicative inverse of a over field p? ($(a*b)modp=1$)
$b$ is of 256 bits and is stored as $b0, b1, b2, b3$.

Answer 1

Two options:

1. Compute $a^n \mod p$ until $a^{n_0} = 1 \mod p$, you then have $a^{-1} = a^{n_0 -1} \mod p$. Complexity of $p$.
2. Use the extended Euclide's algorithm which gives you $r$ and $s$ such that $a r + ps = 1$, you then have $a^{-1} = r \mod p$. Complexity : $O(\log^2(\sup(a, p))) = O($number of bits$)$.

I am not sure that your representation of big integers is efficient, there are some models that already exist in many languages.