clear
len = 0400
e   = prime_gen( hex( 0x$len / 16 ) )
// e    = 010001
x   = new_rsa_genstd( $len, $e )
n   = hmid( $x, 00, hex( 0x$len / 8 ) )
d   = hmid( $x, hex( 0x$len / 8 ) )

// e    = 05
// d    = int2hex(88447120342035329077203801890175181441227843548712394915405983098804986074228491993716303861346713336901472423214577098721961679062412555594462454080858396158886857405021364693424253936899868042331165487633709535319154171592544118785565876198853503758641178366299573880796663815089204345025378660387680199869)

// n    = 9d70ebf2737cb43a7e0ef17b6ce467ab9a116efedbecf1ead94c83e5a082811009100708d690c43c3297b787426b926568a109894f1c48257fc826321177058418e595d16aed5b358d61069150cea832cc7f2df884548f92801606dd3357c39a7ddc868ca8fa7d64d6b64a7395a3247c069112698a365a77761db6b97a2a03a5
// len  = 0400

// 已知
// N = P*Q
// FN = (P-1)*(Q-1)
// 得到
// P*Q- (P-1)*(Q-1) = PQ -(PQ-P-Q+1) = PQ-PQ+P+Q-1 = PQ-1
// 所以
// N - FN + 1 = P + Q
// 所以可构造一个方程组中包含(P+Q)，pq，比如(x-p)(x-q)
// = x^2 -px - qx + pq
// = x^2 -(p+q)x + pq

// = x^2 -(n-fn+1)x + n = (x-p)(x-q)
// +----------------------------+
// |  -b +/-sqrt(b^2-4*a*c)     |
// | ------------------------   |
// |          2a                |
// +----------------------------+

// +--------------------------------------------------------+
// |  另一种方法                                            |
// |  看链接 https://www.40huo.cn/blog/get-pq-from-ned.html |
// +--------------------------------------------------------+

step1:
    inc_indent
        //   1. let k = de - 1
        k   = big_mul( $d, $e )
        k   = big_sub( $k, 01 )
        //   2. write k as k = 2^t * r, where r is the largest odd integer
        //     dividing k, and t >= 1. or
        //     in simpler terms, divide k repeatedly by 2 until you
        //     reach an odd number
        t   = 00
        r   = $k
step2:
    inc_indent
        len = strlen( $r )
        len = sub( $len, 01 )
        bit = memgetbit( $r, $len, 00, 00 )
        if $bit == 00
            r   = big_div( $r, 02 )
            t   = add( $t, 01 )
            goto step2
        endif

        //r = big_mod( $r, $n )

step3:
    inc_indent
        //   3. for i = 1 to 100 do
        nlen    = strlen( $n )
        n_1     = big_sub( $n, 01 )
        one     = hdup( $nlen, 00 )
        one     = big_add( $one, 01 )
        success = 00

        i       = 01
step3_1:
    inc_indent
        inc_indent
            //     a. generate a random interger g in the range[ 0..n-1]
            g       = hrandom( $nlen )
            g       = big_mod( $g, $n )
            //     b. let y = g^r mod n
            y       = big_mod_exp( $g, $r, $n )
            nlen_10 = hex2int( $nlen )
            y       = leftpack( $y, $nlen_10 )
            //     c. if y == 1 or y == n-1, then goto step3.1
            if $y == $one
                goto continue
            endif
            if $y == $n_1
                goto continue
            endif
            //     d. for j = 1 to t-1 do
            j   = 01
step_d:
    inc_indent
        inc_indent
            inc_indent

                //          i. let x = y^2 mod n
                x   = big_mod_mul( $y, $y, $n )
                x   = leftpack( $x, $nlen_10 )
                if $x == $one
                    //      ii. if x == 1 goto(outer)step 5
                    success = 01
                    goto step5
                else if $x == $n_1
                    //      iii. if x == n-1 goto step 3.1

                    goto continue
                else
                    //      iv. let y = x
                    y       = $x
                endif
                j   = add( $j, 01 )
                if $j <= $t
                    goto step_d
                endif

                // g. continue
continue:
    inc_indent
        inc_indent

            i   = add( $i, 01 )
            if $i <= 0065
                goto step3_1
            endif

step4:
    inc_indent
        ? "prime factors not found"
        pause


step5:
    inc_indent

        if $success == 01
            y_1     = big_sub( $y, 01 )
            p       = big_gcd( $y_1, $n )
            q       = big_div( $n, $p )
            x       = new_rsa_calculate_other_by_pqe( hex( 0x$nlen * 08 ), $e, $p, $q )
            len     = div( $nlen, 02 )
            len     = hex2int( $len )

            n2      = mid( $x, 0, int( $len * 2 ) )
            d2      = mid( $x, int( $len * 2 ), int( $len * 2 ) )
            dp2     = mid( $x, int( $len * 4 ), $len )
            dq2     = mid( $x, int( $len * 5 ), $len )
            qinv2   = mid( $x, int( $len * 6 ), $len )

            if $n != $n2
                ?
                pause
            endif
            if $d != $d2
                ?
                pause
            endif
            
            ? "再次使用snooper提供的函数来计算"
            x = new_rsa_calculate_other_by_nde( hex( 0x$nlen * 08 ), $e, $n, $d )
            p3      = mid( $x, 0, int( $len ) )
            q3      = mid( $x, int( $len * 1 ), $len )
            dp3     = mid( $x, int( $len * 2 ), $len )
            dq3     = mid( $x, int( $len * 3 ), $len )
            qinv3   = mid( $x, int( $len * 4 ), $len )
            
            if $p == $p3
                ? "p = p3"
            else if $p == $q3
                ? "p = q3"
            else
                ? "脚本与snooper计算不一致"
                pause
            endif
            if $q == $q3
                ? "q = q3"
            else if $q == $p3
                ? "q = p3"
            else
                ? "脚本与snooper计算不一致"
                pause
            endif
            
            ? "ok"
        else
            ? " cannot computer p and q"
        endif