新しい mod 逆元の求め方

重要な補足
$m$ は素数である必要があります．
$m$ が合成数の場合，計算途中で $a$ と $m$ が互いに素でなくなるかもしれません．

mod 逆元とは

整数 $m\ge 2$ 及び $m$ と互いに素な整数 $a(1\le a<m)$ について， $ab\equiv1\pmod m$ となる $b(1\le b<m)$ を $a$ の $m$ に関する mod 逆元という．これは一意に定まることが証明できる．以下，「$m$ に関する」を省略する．
mod 逆元の求め方は，拡張ユークリッドの互除法やフェルマーの小定理を使うなど様々ある．詳細はここやここが分かりやすいので，参照してほしい．
しかし，以下に述べるのは従来の方法とは異なる方法である． ただし， $m$ が素数の場合のみ可能である． もし既に発見されているのであればコメントをいただきたい．

本題

$a$ の mod 逆元を $f(a)$ と表す．
まず， $a=1$ のとき $f(a)=1$ よりよい．そうでない場合を考える．
整数 $q,r(0\le r<a)$ を用いて $m=qa+r$ と表す($q,r$ はそれぞれ商と余り)．ここで， $aq\equiv-r$ より $a(-qf(r))\equiv rf(r)\equiv1$ である．よって $f(r)$ を求めることで $f(a)$ が求められる．また， $a(q+1)\equiv a-r$ より $a((q+1)f(a-r))\equiv(a-r)f(a-r)\equiv1$ であるため， $f(a-r)$ を求めてもよい．
ここで， $\min(r,a-r)\le a/2$ に注目すると，適切に求めることで引数を $1/2$ にすることができる．また， $a$ と $m$ は互いに素なので $1\le r<a<m$ であり，よって $1\le a-r<a<m$ である． $m$ は素数と仮定したので，次の引数も $m$ と互いに素となる．
計算量は $O(\log a)$．

コード (Python)

def mod_inversion(a, mod):
    if a == 1:
        return 1
    q, r = divmod(mod, a)
    if r > a / 2:
        return (q + 1) * mod_inversion(a - r, mod) % mod
    return -q * mod_inversion(r, mod) % mod