clear

a   = hex( 10 )
m   = hex( 17 )
x   = call modinv( $a, $m )

tmp = big_mul( $a, $x )
tmp = big_mod( $tmp, $m )
if $tmp != 01
    ? "求逆失败"
    pause
endif

a   = int2hex( 0987654321012345678909876543210123456789 )
m   = int2hex( 1000000000000000000000000000000000000037 )
x   = call modinv( $a, $m )

tmp = big_mul( $a, $x )
tmp = big_mod( $tmp, $m )
if $tmp != 01
    ? "求逆失败"
    pause
endif

a   = random( 40 )
a   = or( $a, 00000000000000000000000000000000000000000000000000000000000000000000000000000001 )
m   = shl( 01, 320 )
x   = call modinv( $a, $m )

tmp = big_mul( $a, $x )
tmp = big_mod( $tmp, $m )
if $tmp != 01
    ? "求逆失败"
    pause
endif

end

ExtEuclid:
    prompt off
    local a     = getpara
    local m     = getpara
    local inv   = getpara

    //     uint64_t r0 = a, r1 = m;
    //     uint64_t s0 = 1, s1 = 0;
    local r0    = $a
    local r1    = $m
    local s0    = 01
    local s1    = 00
    local tmp
    local r2
    local q
    local t
    local tmp1

    while $r1 > 00
        //      q = r0 / r1
        q   = big_div( $r0, $r1 )

        //    /* r0, r1 = r1, r0 - q*r1 */
        //    uint64_t r2 = r0 - q * r1;
        //    r0 = r1;
        //    r1 = r2;
        tmp = big_mul( $q, $r1 )        // tmp = q * s1
        r2  = big_sub( $r0, $tmp )      // r2 = r0 - (q*s1)

        r0  = $r1
        r1  = $r2

        //  /* s0, s1 = s1, s0 - q*s1 (mod m) */
        //  uint64_t t;
        //  if (s0 >= q * s1)
        //      t = s0 - q * s1;
        //  else
        //      t = (s0 + m - (q * s1) % m) % m;
        tmp = big_mul( $q, $s1 )
        if $s0 >= $tmp
            t       = big_sub( $s0, $tmp )  // t = s0 - (q*s1)
        else
            tmp     = big_mod( $tmp, $m )   // tmp = (q*s1) % m
            tmp1    = big_add( $s0, $m )    // tmp1 = s0 + m
            tmp1    = big_sub( $tmp1, $tmp )    // tmp1 = s0 + m - (q*s1) %m
            t       = big_mod( $tmp1, $m )  // tmp1 = (s0 + m - (q * s1) % m) % m
        endif

        //    s0 = s1;
        //    s1 = t;
        s0  = $s1
        s1  = $t
    loop

    r0          = big_add( $r0, 00 )

    if $r0 == 01
        tmp     = big_mod( $s0, $m )
        tmp1    = setvalue( $inv, $tmp )
    else
        tmp1    = setvalue( $inv, 00 )
    endif

    prompt on
return $r0

ModInv:
    local a = getpara
    local m = getpara
    local inv
    local g = call exteuclid( $a, $m, &inv )
    g       = big_add( $g, 00 )

    if $g != 01
        inv = 00
    endif

return $inv