Class for residue rings

ring-integers.ts

class MathUtils {
	static mod(x: number, n: number): number {
		return ((x % n) + n) % n
	}

	static gcd(a: number, b: number) {
		while (b !== 0) {
			;[a, b] = [b, a % b]
		}
		return Math.abs(a)
	}

	static is_prime_number(n: number): boolean {
		if (!Number.isInteger(n) || n <= 1) return false
		for (let d = 2; d * d <= n; d++) {
			if (n % d === 0) return false
		}
		return true
	}

	static quotient_remainder(a: number, b: number) {
		if (b === 0) throw new Error('Zero is not allowed in quotient')
		const r = MathUtils.mod(a, b)
		const q = (a - r) / b
		return [q, r]
	}

	static get_bezout_decomposition(a: number, b: number): [number, number] {
		if (b === 0) return [Math.sign(a), 0]
		if (a === 0) return [0, Math.sign(b)]
		const [q, r] = MathUtils.quotient_remainder(a, b)
		const [v, u] = MathUtils.get_bezout_decomposition(b, r)
		return [u, v - u * q]
	}

	static prime_factors(n: number): number[] {
		if (!Number.isInteger(n) || n == 0) throw new Error(`Invalid number: ${n}`)
		if (Math.abs(n) === 1) return []
		let factor = 1
		while (!(MathUtils.is_prime_number(factor) && n % factor === 0)) factor++
		return [factor, ...MathUtils.prime_factors(n / factor)]
	}
}

class ResidueRing {
	readonly order: number
	readonly primes: number[]
	readonly residues: number[]

	constructor(order: number) {
		if (!(Number.isInteger(order) && order >= 1)) {
			throw new Error(`Invalid order: ${order}`)
		}
		this.order = order
		this.primes = MathUtils.prime_factors(this.order)
		this.residues = Array.from({ length: order }, (_, i) => i)
	}

	get name() {
		return `Ring of integers modulo ${this.order}`
	}

	get is_local() {
		return this.primes.length === 1
	}

	add(a: number, b: number): number {
		return MathUtils.mod(a + b, this.order)
	}

	subtract(a: number, b: number): number {
		return MathUtils.mod(a - b, this.order)
	}

	multiply(a: number, b: number): number {
		return MathUtils.mod(a * b, this.order)
	}

	is_invertible(a: number): boolean {
		return MathUtils.gcd(a, this.order) === 1
	}

	get units(): number[] {
		return this.residues.filter((r) => this.is_invertible(r))
	}

	is_nilpotent(a: number): boolean {
		return this.primes.every((p) => a % p === 0)
	}

	get nilpotents(): number[] {
		return this.residues.filter((r) => this.is_nilpotent(r))
	}

	inverse(a: number): number | undefined {
		if (this.is_invertible(a)) {
			const [u] = MathUtils.get_bezout_decomposition(a, this.order)
			return MathUtils.mod(u, this.order)
		}
	}
}