factor.py 文件源码

def period_to_factors(base, modulus, period):
    half_period = period // 2
    x = pow(base, half_period, modulus)
    if x**2 % modulus != 1 or x == 1 or x == -1 % modulus:
        return None

    # (x + 1) * (x - 1) = x^2 - 1^2 = 1 - 1 = 0
    # therefore (x+1)*(x-1) * k = k * modulus
    # but (x+1) and (x-1) can't be multiples of modulus
    # therefore they contain factors

    factors_1 = fractions.gcd(x + 1, modulus)
    factors_2 = fractions.gcd(x - 1, modulus)

    assert factors_1 * factors_2 == modulus
    return sorted([factors_1, factors_2])