clear

prompt on

len         = hex( 512 )

a           = hrandom( $len )
mask        = hdup( $len, 00 )
mask        = memset( $mask, hex( 0x$len - 1 ), 01, 01 )
a           = or( $a, $mask )

n           = shl( 01, int( 0x$len * 8 ) )
s           = timer
inv         = call modinv( $a, $n )
e           = timer

used_time   = sub( $e, $s )
? "耗时 " expr10( 0x$used_time, 302 ) " 毫秒"

tmp         = big_mul( $a, $inv )
remain      = big_mod( $tmp, $n )
if $remain != 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 )

    if $g != 01
        inv = 00
    endif

return $inv
//len = 0200
//a = C0CB729C72E1EE2905B317183B50C7AADBAE350DEE04C7DD2D7427EABBED993C10508C5435D16EB537A1C5A3D6CA7C2B7D5A7A6377C37AF35F8216D4D8FF24587FB4466B1E92BD1823A07E4F50E688E5B38974DCD9374EE53FC5A3230917DB32F641C96894EB815AB0FA6AA2116D94E066844BFF7C28ECBAB487F75EB5FF66D15E3D3DD3FEA66384C8F5B026812647257C942654C85EFB7AA80E390D437D6C3D9DF1CA35C6890A9D52DB796308DB4ABBDFFF2D6426A0242D02A492B91D5A957F9DA59614535D1FAD35F2ECE00F5244AA750D8AB6FCB70FDCAA8F2AE9AA5D8B9E44A1CCFB0DE949BD5B833225FC54DEFB280862D3B36C638F871728255250F3A27C2C926F5CF731D3ABD572BA39A9C0B5DE36E041B485C84C8386B5F57DF978942C8F10FAA84D7EFA0D32D5282C1991E081E1298A66CAE81D8522F8E29322C07B3C13702359B4D93769E083F63F6CF985F84F68353005680976351A73FC91735F93FDD772D7F4EA94A728A3ACD969A2AA2BC8C3CB7CFCF3183C054231210F3A481B986F708BD55818B0525DD261DA315A029662D3B1782F53C0DB99A26863BD3FBB2B60A4DB1FCCCB6AA6DBF14185519A65006ED53641C4C1EAFE47503A57A34B5BFDD2973099EDB6BE6C4290E032A8743C4D0F5A751F5B6BA3B873C300B19475E357ECCFF30D64E094EBBD38A6ABDEEF6FC66CE9D5DA9C57D14F4581203A3AC4
//mask = 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
//mask = 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
//a = C0CB729C72E1EE2905B317183B50C7AADBAE350DEE04C7DD2D7427EABBED993C10508C5435D16EB537A1C5A3D6CA7C2B7D5A7A6377C37AF35F8216D4D8FF24587FB4466B1E92BD1823A07E4F50E688E5B38974DCD9374EE53FC5A3230917DB32F641C96894EB815AB0FA6AA2116D94E066844BFF7C28ECBAB487F75EB5FF66D15E3D3DD3FEA66384C8F5B026812647257C942654C85EFB7AA80E390D437D6C3D9DF1CA35C6890A9D52DB796308DB4ABBDFFF2D6426A0242D02A492B91D5A957F9DA59614535D1FAD35F2ECE00F5244AA750D8AB6FCB70FDCAA8F2AE9AA5D8B9E44A1CCFB0DE949BD5B833225FC54DEFB280862D3B36C638F871728255250F3A27C2C926F5CF731D3ABD572BA39A9C0B5DE36E041B485C84C8386B5F57DF978942C8F10FAA84D7EFA0D32D5282C1991E081E1298A66CAE81D8522F8E29322C07B3C13702359B4D93769E083F63F6CF985F84F68353005680976351A73FC91735F93FDD772D7F4EA94A728A3ACD969A2AA2BC8C3CB7CFCF3183C054231210F3A481B986F708BD55818B0525DD261DA315A029662D3B1782F53C0DB99A26863BD3FBB2B60A4DB1FCCCB6AA6DBF14185519A65006ED53641C4C1EAFE47503A57A34B5BFDD2973099EDB6BE6C4290E032A8743C4D0F5A751F5B6BA3B873C300B19475E357ECCFF30D64E094EBBD38A6ABDEEF6FC66CE9D5DA9C57D14F4581203A3AC5
//n = 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
//s = 754CECC9
//a = C0CB729C72E1EE2905B317183B50C7AADBAE350DEE04C7DD2D7427EABBED993C10508C5435D16EB537A1C5A3D6CA7C2B7D5A7A6377C37AF35F8216D4D8FF24587FB4466B1E92BD1823A07E4F50E688E5B38974DCD9374EE53FC5A3230917DB32F641C96894EB815AB0FA6AA2116D94E066844BFF7C28ECBAB487F75EB5FF66D15E3D3DD3FEA66384C8F5B026812647257C942654C85EFB7AA80E390D437D6C3D9DF1CA35C6890A9D52DB796308DB4ABBDFFF2D6426A0242D02A492B91D5A957F9DA59614535D1FAD35F2ECE00F5244AA750D8AB6FCB70FDCAA8F2AE9AA5D8B9E44A1CCFB0DE949BD5B833225FC54DEFB280862D3B36C638F871728255250F3A27C2C926F5CF731D3ABD572BA39A9C0B5DE36E041B485C84C8386B5F57DF978942C8F10FAA84D7EFA0D32D5282C1991E081E1298A66CAE81D8522F8E29322C07B3C13702359B4D93769E083F63F6CF985F84F68353005680976351A73FC91735F93FDD772D7F4EA94A728A3ACD969A2AA2BC8C3CB7CFCF3183C054231210F3A481B986F708BD55818B0525DD261DA315A029662D3B1782F53C0DB99A26863BD3FBB2B60A4DB1FCCCB6AA6DBF14185519A65006ED53641C4C1EAFE47503A57A34B5BFDD2973099EDB6BE6C4290E032A8743C4D0F5A751F5B6BA3B873C300B19475E357ECCFF30D64E094EBBD38A6ABDEEF6FC66CE9D5DA9C57D14F4581203A3AC5
//m = 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
//inv = 
//g = 01
//inv = F52C5D5801FD381D9EAD46E0EB72D34937D72E81486DA2755BFE90741FC87F5FE9461EF64E19D2F548A59DA3973B5662BDF6A65F1C1AAEB40D3D9FEB26B549F30D7E8763EEF913EC1C0F9FE7540EFF2636358C4CE0DFAF0BD59FE0B25C3E70AF9E18953BD6CB25B49D768834C3ED3B8E80CF0597DAA7193B837A137CCD50CC923B7BE774CAABF3D88AAA92B1089CF7734B1786019EE6194B57AFCFB5CDEA7A60F339324CCAF00453C08636DD35ACBC18CE225D3BB1475BAEC3A2F55D8A2CDF975E31BE829D03A42E42759ED7F9D45920F5EDC7894293E7B005A79549E895672DC807213A4C49FB35331DE8845B636658FE53485BDF6821D5D54297D1F3856D3C6C9BD66E0357F1EA083FA5A907B1B63027D96F76E290648675B362DC30CC343A2A2AABFA84C8ED18FCB8C330D57492B8027303C51D647182128B8D0FC7C1DEEE9856D385D0BC3F1C898A6F369478BE3976033573499AEC853DE7B63A081D84A3FD2D6A735E48653354792521153C2563BB8CB1BEE2782F8AA1042EAB63C862EDF7F6474D094865FDB655C0FC05B49B7A4F12EEE02F3B8ED56853A69E8807300DA5756BE2BC3FCAE733773A37CA8B1A4B5FC5148EC2E714905A491AB62EE5850C2A962F1FF2601C36FDF5C9979E86D34008712F0FE6E7AE51B28650A323BB3BC339BC229611E6863E8C93658E586A842A4FAE165B2AE522DB0412AB86725F340D
//e = 754F13BF
//used_time = 000226F6

//[]=======================[]
//[]  耗时 141,046 毫秒    []
//[]=======================[]
//tmp = B8A41DF39CE7B20B735ED4B92C70E7BA5A23FA5DA1D7AC53718161CA93703F1D80524F764207E9F7B9FA41AD09E84A88693E6AEE2301B5C4C95BDCE95B20C6C7F6E6833890EFAA0E04E230BA0D657896551319667742913D9E7709914060F01F6308E60F41FD757081ACCD3C788D01018DE5BD29AA6D08CAAB3ABAA94BDD280A1167DB71D3255E6956737158CD2D43941470D83EAB8EA8EA4A06506260937DE530BDF3B2B35DB852F0210FC7C3D1ABBABEA04E565DF764E1C9299B9065832756BFD334531B79AA5FCFC98B9373AF50BF2E30AE021A2D83D83BE223283174CF6D064E519F2FA31430643F65A8E26E31C7722A0A1AC3E11987FBE99738E284CEB6750615BBCC5FB3DDF9A5D50A9C44011BAC4AD10B645259EAD640F0B737691283031F177F8435A13D7CE63F06C1BB83A6125880CD57F117322A9F2D820673991D5A79AA59CC6188F804527E7F45B3BE72B60D63EC654F8CA694BAD8DD364352C1D33B56BDE7BA3D97F470ECF2F26D1A2E46EDCD102FBFA67EB862DC566EEECAF9E2B4B9044718B464AF539DFA5D3DC4DE2C57A3C3262666A41183E02D0726E6A6E51B2BAE75625287F79EA68503CAB9C3D22BE8DFE29EA5E897ACD7A665D8C408AD04B96E8393AD4F40DB87B57306AA2F94647EA3664EB445014C3F7988EA1E1EF6DE78EEBBBB71073C8477C55A5C8C67E97F6CCAC466376A1610EF19927A26DF0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
//remain = 01
//Script File  D:\扩展欧几里得-4096-迭代版.txt
//The script has finished running at line 27, 2025-12-24 11:32:55