#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL n AS LONG
    LOCAL modulus AS LONG
    LOCAL k AS LONG
    LOCAL mu AS LONG
    LOCAL a_val AS LONG
    LOCAL q_val AS LONG
    LOCAL r_val AS LONG
    LOCAL t1 AS LONG
    LOCAL t2_val AS LONG
    LOCAL temp_str AS STRING
    LOCAL i AS LONG

    ' Barrett reduction: compute r = a mod n using precomputed mu
    ' mu = floor(b^2k / n) where b = 2, k = log2(n)
    ' r = a - floor(a * mu / b^2k) * n

    PRINT "Barrett Modular Reduction"
    PRINT "========================"
    PRINT ""

    n = 97
    modulus = n

    k = 0
    t1 = n
    WHILE t1 > 0
        t1 = t1 / 2
        k = k + 1
    WEND

    mu = 1
    t1 = 0
    WHILE t1 < 2 * k
        mu = mu * 2
        t1 = t1 + 1
    WEND
    mu = mu / n

    temp_str = STR$(k)
    PRINT "Modulus n = " + STR$(n) + ", k = " + temp_str + ", mu = " + STR$(mu)

    ' Test reductions
    a_val = 200
    q_val = a_val * mu
    i = 0
    WHILE i < k
        q_val = q_val / 2
        i = i + 1
    WEND
    r_val = a_val - q_val * n
    IF r_val >= n THEN
        r_val = r_val - n
    END IF
    IF r_val < 0 THEN
        r_val = r_val + n
    END IF

    temp_str = STR$(a_val MOD n)
    PRINT "200 mod 97 = " + STR$(r_val) + " (expected " + temp_str + ")"

    a_val = 500
    q_val = a_val * mu
    i = 0
    WHILE i < k
        q_val = q_val / 2
        i = i + 1
    WEND
    r_val = a_val - q_val * n
    IF r_val >= n THEN
        r_val = r_val - n
    END IF
    IF r_val < 0 THEN
        r_val = r_val + n
    END IF

    temp_str = STR$(a_val MOD n)
    PRINT "500 mod 97 = " + STR$(r_val) + " (expected " + temp_str + ")"

    a_val = 1000
    q_val = a_val * mu
    i = 0
    WHILE i < k
        q_val = q_val / 2
        i = i + 1
    WEND
    r_val = a_val - q_val * n
    IF r_val >= n THEN
        r_val = r_val - n
    END IF
    IF r_val < 0 THEN
        r_val = r_val + n
    END IF

    temp_str = STR$(a_val MOD n)
    PRINT "1000 mod 97 = " + STR$(r_val) + " (expected " + temp_str + ")"

    ' Test with different modulus
    n = 50
    modulus = n

    k = 0
    t1 = n
    WHILE t1 > 0
        t1 = t1 / 2
        k = k + 1
    WEND

    mu = 1
    t1 = 0
    WHILE t1 < 2 * k
        mu = mu * 2
        t1 = t1 + 1
    WEND
    mu = mu / n

    temp_str = STR$(k)
    PRINT ""
    PRINT "Modulus n = " + STR$(n) + ", k = " + temp_str + ", mu = " + STR$(mu)

    a_val = 123
    q_val = a_val * mu
    i = 0
    WHILE i < k
        q_val = q_val / 2
        i = i + 1
    WEND
    r_val = a_val - q_val * n
    IF r_val >= n THEN
        r_val = r_val - n
    END IF
    IF r_val < 0 THEN
        r_val = r_val + n
    END IF

    temp_str = STR$(a_val MOD n)
    PRINT "123 mod 50 = " + STR$(r_val) + " (expected " + temp_str + ")"

    ' Modular arithmetic with Barrett
    PRINT ""
    PRINT "Modular arithmetic with Barrett reduction:"
    PRINT "  (1 + 2) mod 97:"
    a_val = 1
    t1 = 1 + 2
    q_val = t1 * mu
    i = 0
    WHILE i < k
        q_val = q_val / 2
        i = i + 1
    WEND
    r_val = t1 - q_val * n
    IF r_val >= n THEN
        r_val = r_val - n
    END IF
    IF r_val < 0 THEN
        r_val = r_val + n
    END IF
    PRINT "    = " + STR$(r_val)

    ' Modular multiplication
    PRINT "  (10 * 10) mod 97:"
    t1 = 10 * 10
    q_val = t1 * mu
    i = 0
    WHILE i < k
        q_val = q_val / 2
        i = i + 1
    WEND
    r_val = t1 - q_val * n
    IF r_val >= n THEN
        r_val = r_val - n
    END IF
    IF r_val < 0 THEN
        r_val = r_val + n
    END IF
    PRINT "    = " + STR$(r_val)

    PRINT ""
    PRINT "Barrett reduction is efficient for repeated"
    PRINT "modular operations with the same modulus."
    PRINT ""
    PRINT "Barrett reduction demo complete."

    FUNCTION = 0
END FUNCTION
