# Arithmetic Algorithm Specification v1.0

## Overview

This specification defines the normative algorithms for all big integer arithmetic operations in the ClockinChain ecosystem. All algorithms must execute in constant time and produce deterministic results.

## 1. Common Conventions

### 1.1 Limb Operations

```rust
// Basic limb arithmetic with carry/borrow
fn limb_add_carry(a: Limb, b: Limb, carry: Limb) -> (Limb, Limb) {
    let sum = a as u128 + b as u128 + carry as u128;
    (sum as Limb, (sum >> 64) as Limb)
}

fn limb_sub_borrow(a: Limb, b: Limb, borrow: Limb) -> (Limb, Limb) {
    let diff = a as i128 - b as i128 - borrow as i128;
    (diff as Limb, if diff < 0 { 1 } else { 0 })
}

fn limb_mul_wide(a: Limb, b: Limb) -> (Limb, Limb) {
    let product = a as u128 * b as u128;
    (product as Limb, (product >> 64) as Limb)
}
```

### 1.2 Fixed Loop Rule

**All algorithms MUST iterate over full declared limb length:**
- Never exit loops early
- Mask carries instead of branching
- Use constant-time condition selection
- Fixed execution paths regardless of input values

### 1.3 Algorithm Selection

Operations choose algorithms based on **public parameters only** (limb length), never secret values.

## 2. Addition Algorithm

### 2.1 Function Signature

```rust
fn add(a: &BigInt, b: &BigInt) -> Result<BigInt>
```

### 2.2 Precondition

- `a` and `b` have equal limb length `n`
- If dynamic-length, caller ensures sufficient capacity

### 2.3 Algorithm

```
For i = 0 .. n-1:
    (sum_i, carry) = adc(a.limbs[i], b.limbs[i], carry)
    c.limbs[i] = sum_i

After final limb:
    If carry = 1:
        If dynamic-length → append new limb = 1
        If fixed-length → overflow trap
```

### 2.4 Constant-Time adc

```rust
sum = x + y + carry
carry_out = (sum < x) OR ((carry == 1) AND (sum == x))
```

No branches allowed.

### 2.5 Sign Handling

- Same sign: `sign(c) = sign(a)`
- Different signs: invoke subtraction algorithm

### 2.6 Gas Cost

`G_add(n) = 3n`

## 3. Subtraction Algorithm

### 3.1 Function Signature

```rust
fn sub(a: &BigInt, b: &BigInt) -> Result<BigInt>
```

### 3.2 Algorithm (Magnitude)

```
For i = 0 .. n-1:
    (diff_i, borrow) = sbb(a.limbs[i], b.limbs[i], borrow)
    c.limbs[i] = diff_i

If final borrow = 1 → result negative:
    Compute two's complement of magnitude
    Flip sign bit
```

### 3.3 Constant-Time sbb

```rust
diff = x - y - borrow
borrow_out = (x < y) OR ((borrow == 1) AND (x == y))
```

No branches.

### 3.4 Sign Rule

`sign(c) = sign(a) XOR sign(b)`

### 3.5 Gas Cost

`G_sub(n) = 3n`

## 4. Multiplication Algorithm

### 4.1 Function Signature

```rust
fn mul(a: &BigInt, b: &BigInt) -> Result<BigInt>
```

### 4.2 Comba Method (Small Operands)

For operands ≤ 16 limbs:

```
Let n = limb count
Initialize c limbs length = 2n all zero

for i = 0 .. n-1:
    carry = 0
    for j = 0 .. n-1:
        (lo, hi) = mul64(a[i], b[j])
        (c[i+j], carry) = mac(c[i+j], lo, carry)
        carry += hi
    c[i+n] = carry
```

### 4.3 Karatsuba Method (Large Operands)

For operands > 16 limbs:

```
fn karatsuba_mul(a: &[Limb], b: &[Limb]) -> Vec<Limb> {
    let n = a.len();
    let m = n / 2;

    // Split operands
    let (a0, a1) = a.split_at(m);
    let (b0, b1) = b.split_at(m);

    // Compute z0 = a0*b0
    let z0 = karatsuba_mul(a0, b0);

    // Compute z2 = a1*b1
    let z2 = karatsuba_mul(a1, b1);

    // Compute z1 = (a0+a1)*(b0+b1) - z0 - z2
    let a01 = add_limbs(a0, a1);
    let b01 = add_limbs(b0, b1);
    let z1 = karatsuba_mul(&a01, &b01);
    sub_limbs_inplace(&mut z1, &z0);
    sub_limbs_inplace(&mut z1, &z2);

    // Combine results
    return combine_karatsuba_results(z0, z1, z2, m);
}
```

### 4.4 Threshold Selection

- Threshold MUST be fixed constant: `KARATSUBA_THRESHOLD = 16`
- Execution path depends only on public limb length
- Never on operand values

### 4.5 Sign Rule

`sign(c) = sign(a) XOR sign(b)`

### 4.6 Gas Cost

`G_mul(n) = 2n²`

## 5. Division Algorithm

### 5.1 Function Signatures

```rust
fn div_rem(a: &BigInt, b: &BigInt) -> Result<(BigInt, BigInt)>
fn div(a: &BigInt, b: &BigInt) -> Result<BigInt>
fn rem(a: &BigInt, b: &BigInt) -> Result<BigInt>
```

### 5.2 Knuth Algorithm D

1. **Normalize divisor**: Left-shift so highest bit set
2. **Left-shift dividend** equally
3. **Main loop**:

```
for i from high_limb downto low_limb:
    // Estimate quotient digit q̂
    q̂ = estimate_quotient_digit(dividend, divisor, i)

    // Multiply and subtract
    (partial_product, borrow) = mul_sub(divisor, q̂, dividend_slice)

    // Correct if overestimated
    while borrow != 0:
        q̂ -= 1
        add_back(divisor, dividend_slice)
        borrow = check_borrow(dividend_slice)
```

### 5.3 Constant-Time Corrections

- All correction steps use **masked subtraction**
- No branches based on borrow values
- Fixed iteration count based on limb length

### 5.4 Division by Zero

Must return deterministic `DivisionByZero` error.

### 5.5 Sign Rules

```
quotient_sign = sign(a) XOR sign(b)
remainder_sign = sign(a)
```

### 5.6 Gas Cost

`G_div(n) = 4n²`

## 6. Squaring Algorithm

### 6.1 Function Signature

```rust
fn sqr(a: &BigInt) -> Result<BigInt>
```

### 6.2 Specialized Algorithm

Squaring uses optimized algorithm for `a²`:

- Exploits symmetry: `a² = (a0 + a1*B)² = a0² + 2*a0*a1*B + a1²*B²`
- Fewer multiplications than general multiplication
- Same constant-time properties

### 6.3 Gas Cost

`G_sqr(n) = 1.6n²` (cheaper than multiplication)

## 7. Bitwise Operations

### 7.1 Bit Shift

```rust
fn shift_left(a: &BigInt, bits: usize) -> Result<BigInt>
fn shift_right(a: &BigInt, bits: usize) -> Result<BigInt>
```

### 7.2 Algorithm

- Convert bit shifts to limb shifts + intra-limb shifts
- Handle carry/borrow across limb boundaries
- Constant-time regardless of shift amount

### 7.3 Gas Cost

`G_shift(n) = 2n`

## 8. Comparison Operations

### 8.1 Comparison Functions

```rust
fn cmp(a: &BigInt, b: &BigInt) -> Ordering
fn eq(a: &BigInt, b: &BigInt) -> bool
fn lt(a: &BigInt, b: &BigInt) -> bool
```

### 8.2 Constant-Time Implementation

- Compare magnitudes first
- Then compare signs if magnitudes equal
- No early exit on first difference

### 8.3 Gas Cost

`G_cmp(n) = 2n`

## 9. Error Conditions

| Condition | Result |
|-----------|--------|
| Overflow (fixed) | VM Trap |
| Overflow (dynamic beyond max) | Overflow error |
| Division by zero | Deterministic error |
| Non-canonical input | Decode rejection |

## 10. Determinism Guarantee

Given identical inputs, all implementations MUST:

- Produce identical limb outputs
- Execute identical iteration counts
- Consume identical gas cost
- Never branch on secret data