from math import gcd

def period_trace(modulus, base):
    if modulus < 3 or not 1 < base < modulus or gcd(modulus, base) != 1:
        raise ValueError("base must be nontrivial and coprime to modulus")
    values, current = [], 1
    while current not in values:
        values.append(current)
        current = current * base % modulus
    return {"period": len(values), "orbit": values}

def factor_from_period(modulus, base):
    trace = period_trace(modulus, base)
    period = trace["period"]
    if period % 2 or pow(base, period // 2, modulus) == modulus - 1:
        return {**trace, "factors": set()}
    factors = {gcd(pow(base, period // 2) - 1, modulus),
               gcd(pow(base, period // 2) + 1, modulus)} - {1, modulus}
    return {**trace, "factors": factors}

fifteen = factor_from_period(15, 2)
twenty_one = factor_from_period(21, 2)
invalid_rejected = False
try:
    factor_from_period(15, 3)
except ValueError:
    invalid_rejected = True
assert fifteen["period"] == 4 and fifteen["factors"] == {3, 5}
assert twenty_one["period"] == 6 and twenty_one["factors"] == {3, 7}
assert invalid_rejected
print(f"PASS: 33 period finding N15_r={fifteen['period']} factors={sorted(fifteen['factors'])} N21_r={twenty_one['period']} factors={sorted(twenty_one['factors'])}")