oarust 0.9.0

GPU-first semantic computing engine written in Rust
// Public-data modular arithmetic over little-endian 32-bit limbs.
// No qualified OA C++ BigInt donor exists. New implementation from integer
// remainder, Euclidean coefficient recurrence and binary exponentiation
// identities; see Handbook of Applied Cryptography, chapter 14.
// No constant-time, secret-placement or competitive-performance claim.
import bigint_words;
import bigint_montgomery;

bool bigint_is_zero(
	uint value[128],
	uint words
) {
	uint combined = 0u;
	for (uint i = 0u; i < words; ++i) combined |= value[i];
	return combined == 0u;
}

// Precondition: 1 <= words <= 128, 0 <= input_words <= 256. Ordinary residues.
// A zero modulus returns false and a completely zero result.
bool bigint_reduce_wide(
	uint input[256],
	uint input_words,
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	bigint_zero(result);
	if (bigint_is_zero(modulus, words)) return false;
	[loop]
	for (uint bit = input_words * 32u; bit != 0u; --bit) {
		uint index = bit - 1u;
		uint carry = (input[index / 32u] >> (index % 32u)) & 1u;
		[loop]
		for (uint i = 0u; i < words; ++i) {
			uint next = result[i] >> 31u;
			result[i] = (result[i] << 1u) | carry;
			carry = next;
		}
		if (carry != 0u || bigint_compare(result, modulus, words) >= 0) {
			uint borrow = 0u;
			[loop]
			for (uint i = 0u; i < words; ++i) {
				uint difference = result[i] - modulus[i];
				uint borrow_ab = uint(result[i] < modulus[i]);
				uint value = difference - borrow;
				borrow = borrow_ab | uint(difference < borrow);
				result[i] = value;
			}
		}
	}
	return true;
}

bool bigint_reduce(
	uint input[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	uint quotient[128];
	bool valid = bigint_divide(input, modulus, words, quotient, result);
	if (!valid) bigint_zero(result);
	return valid;
}

bool bigint_add_mod(
	uint a[128],
	uint b[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	uint sum[128];
	uint carry = bigint_add(a, b, words, sum);
	uint wide[256];
	for (uint i = 0u; i < 256u; ++i) wide[i] = 0u;
	for (uint i = 0u; i < words; ++i) wide[i] = sum[i];
	wide[words] = carry;
	return bigint_reduce_wide(wide, words + 1u, modulus, words, result);
}

bool bigint_subtract_mod(
	uint a[128],
	uint b[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	bigint_zero(result);
	uint left[128], right[128], difference[128];
	if (!bigint_reduce(a, modulus, words, left)) return false;
	bigint_reduce(b, modulus, words, right);
	uint borrow = bigint_subtract(left, right, words, difference);
	if (borrow != 0u) bigint_add(difference, modulus, words, result);
	else for (uint i = 0u; i < 128u; ++i) result[i] = difference[i];
	return true;
}

bool bigint_multiply_mod(
	uint a[128],
	uint b[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	uint product[256];
	bigint_multiply(a, b, words, words * 2u, product);
	return bigint_reduce_wide(product, words * 2u, modulus, words, result);
}

// Euclidean coefficients are stored modulo m, avoiding signed fixed-width
// temporaries. This accepts odd/even and composite moduli; non-units return
// false and zero. The modulus-one ring follows Python's inverse convention.
bool bigint_inverse_mod(
	uint input[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	bigint_zero(result);
	uint old_r[128], r[128], old_t[128], t[128];
	if (!bigint_reduce(input, modulus, words, r)) return false;
	for (uint i = 0u; i < 128u; ++i) old_r[i] = modulus[i];
	bigint_zero(old_t);
	uint one[128];
	bigint_zero(one);
	one[0] = 1u;
	bigint_reduce(one, modulus, words, t);
	[loop]
	while (!bigint_is_zero(r, words)) {
		uint quotient[128], next_r[128], product[128], next_t[128];
		bigint_divide(old_r, r, words, quotient, next_r);
		bigint_multiply_mod(quotient, t, modulus, words, product);
		bigint_subtract_mod(old_t, product, modulus, words, next_t);
		for (uint i = 0u; i < 128u; ++i) {
			old_r[i] = r[i]; r[i] = next_r[i];
			old_t[i] = t[i]; t[i] = next_t[i];
		}
	}
	if (bigint_compare(old_r, one, words) != 0) return false;
	for (uint i = 0u; i < 128u; ++i) result[i] = old_t[i];
	return true;
}

bool bigint_montgomery_multiply(
	uint a[128],
	uint b[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	bigint_zero(result);
	if ((modulus[0] & 1u) == 0u) return false;
	uint left[128], right[128];
	bigint_reduce(a, modulus, words, left);
	bigint_reduce(b, modulus, words, right);
	bigint_montgomery_product(left, right, modulus, words, bigint_montgomery_factor(modulus[0]), result);
	return true;
}

bool bigint_to_montgomery(
	uint input[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	bigint_zero(result);
	if ((modulus[0] & 1u) == 0u) return false;
	uint shifted[256];
	for (uint i = 0u; i < 256u; ++i) shifted[i] = 0u;
	for (uint i = 0u; i < words; ++i) shifted[i + words] = input[i];
	return bigint_reduce_wide(shifted, words * 2u, modulus, words, result);
}

bool bigint_from_montgomery(
	uint input[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	uint one[128];
	bigint_zero(one); one[0] = 1u;
	return bigint_montgomery_multiply(input, one, modulus, words, result);
}

bool bigint_pow_mod(
	uint base[128],
	uint exponent[128],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	bigint_zero(result);
	uint power[128], accumulator[128], one[128];
	if (!bigint_reduce(base, modulus, words, power)) return false;
	bigint_zero(one); one[0] = 1u;
	bigint_reduce(one, modulus, words, accumulator);
	bool montgomery = (modulus[0] & 1u) != 0u;
	uint negative_inverse = 0u;
	if (montgomery) {
		uint encoded_power[128], encoded_one[128];
		bigint_to_montgomery(power, modulus, words, encoded_power);
		bigint_to_montgomery(accumulator, modulus, words, encoded_one);
		for (uint i = 0u; i < 128u; ++i) {
			power[i] = encoded_power[i]; accumulator[i] = encoded_one[i];
		}
		negative_inverse = bigint_montgomery_factor(modulus[0]);
	}
	uint bits = 0u;
	for (uint i = 0u; i < words; ++i) {
		if (exponent[i] != 0u) bits = i * 32u + uint(firstbithigh(exponent[i])) + 1u;
	}
	[loop]
	for (uint bit = 0u; bit < bits; ++bit) {
		uint product[128];
		if (((exponent[bit / 32u] >> (bit % 32u)) & 1u) != 0u) {
			if (montgomery)
				bigint_montgomery_product(accumulator, power, modulus, words, negative_inverse, product);
			else bigint_multiply_mod(accumulator, power, modulus, words, product);
			for (uint i = 0u; i < 128u; ++i) accumulator[i] = product[i];
		}
		if (bit + 1u < bits) {
			if (montgomery)
				bigint_montgomery_product(power, power, modulus, words, negative_inverse, product);
			else bigint_multiply_mod(power, power, modulus, words, product);
			for (uint i = 0u; i < 128u; ++i) power[i] = product[i];
		}
	}
	if (montgomery) {
		uint ordinary_one[128];
		bigint_reduce(one, modulus, words, ordinary_one);
		bigint_montgomery_product(accumulator, ordinary_one, modulus, words, negative_inverse, result);
	} else for (uint i = 0u; i < 128u; ++i) result[i] = accumulator[i];
	return true;
}