---
title: "algorithm-berlekamp-massey — Mova code model"
description: "Mova code model of algorithms/src/berlekamp_massey/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/berlekamp_massey/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/berlekamp_massey/mod.rs.groupant/>

# algorithm-berlekamp-massey

The groupant beside algorithms/src/berlekamp_massey/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant
- **status:** partial source derived instance
- **source:** [`algorithms/src/berlekamp_massey/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/berlekamp_massey/mod.rs)
- **source SHA-256:** `024f8c4d532a3580…`
- **repository folder:** [`algorithms/src/berlekamp_massey/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/berlekamp_massey/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [Forward](#forward) |
| **ast** | partial | `syntax.json` |
| **cost** | conditional | [Cost](#cost) |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [Invariant](#invariant) |
| **tests** | bounded executed | [evidence](#evidence) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `behavior_complement` | behavior_complement | partial relational specification | [behavior_complement](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial relational specification | [reverse_reconstruction](#reverse-reconstruction) |
| `minimality_rank` | minimality_rank | partial relational specification | [minimality_rank](#minimality-rank) |
| `finite_prefix_ambiguity` | finite_prefix_ambiguity | partial relational specification | [finite_prefix_ambiguity](#finite-prefix-ambiguity) |
| `lag_orientation` | lag_orientation | partial relational specification | [lag_orientation](#lag-orientation) |
| `field_inversion` | field_inversion | partial relational specification | [field_inversion](#field-inversion) |
| `normalization_overflow` | normalization_overflow | partial relational specification | [normalization_overflow](#normalization-overflow) |
| `validation_partition` | validation_partition | partial relational specification | [validation_partition](#validation-partition) |

## Model text


### descriptant

#### Modeling epoch, 2026-10-30

Original implementation and finite oracle. For normalized finite s, find minimum L such that s[t]=sum(c[j]*s[t-1-j]) for L<=t<n. The connection polynomial starts with1. A nonzero discrepancy is canceled using a shifted prior polynomial and its nonzero discrepancy inverse; when 2L<=t update L=t+1-L. Return negated nonconstant coefficients in lag order. The concrete update schedule chooses one compatible solution, not all solutions.

The first epoch retains ambiguity explicitly: finite recurrence prefixes can have multiple minimum-order continuations, and convolution cannot uniquely identify operands. Independent Gaussian/matrix/direct-sum checks avoid relying only on reciprocal algorithms. Arithmetic is exact; there is no approximate production profile. Partial source projections do not resolve names, expand macros or prove semantics. Resource caps bound work but do not guarantee performance; allocator refusal is unforced.

The 2026-11-01 independent review separated the vacuous order-n compatibility fiber of a delayed nonzero prefix from the implementation's selected vector. Its first all-zero-output hypothesis failed on a one-term prefix; the corrected source-derived schedule and bounded probe are recorded in the model and evidence. No production implementation or approximation changed.

### model

## berlekamp_massey mod.rs

### Forward

For normalized finite s, find minimum L such that s[t]=sum(c[j]*s[t-1-j]) for L<=t<n. The connection polynomial starts with1. A nonzero discrepancy is canceled using a shifted prior polynomial and its nonzero discrepancy inverse; when 2L<=t update L=t+1-L. Return negated nonconstant coefficients in lag order. The concrete update schedule chooses one compatible solution, not all solutions.

### Invariant

c[0]=b[0]=1; previous is nonzero; after each prefix the current connection polynomial annihilates every required index at its current order. The Massey length update tracks minimal compatible order. Finite Gaussian checks test this claim independently.

### Cost

For n<=4096, O(n²+n log p) modular operations and three O(n) vectors. Fixed prime inversion is bounded; copying full vectors keeps worst-case quadratic work even for smaller order. Cap is a resource policy.

### behavior_complement

Within validated calls and candidate coefficients, incompatible recurrences or a compatible recurrence of nonminimal order are absent. Invalid over-cap calls paired with Ok are absent. Compatibility/minimality alone is an outer description of possible output: deterministic tie choice imposes extra constraints.

### reverse_reconstruction

For observed c, retain all prefixes whose deterministic discrepancy schedule returns c. The looser algebraic fiber contains every prefix compatible with c and no shorter order, but may include prefixes selecting another tie. All-zero prefixes of every admissible length share empty output; uniqueness is absent.

### minimality_rank

For candidate order k form rows (s[t-1],...,s[t-k]|s[t]) for k<=t<n. Feasibility is rank(A)=rank(A|b); returned L is the least feasible k. Gaussian rank is an independent finite oracle; it neither identifies future terms nor claims uniqueness.

### finite_prefix_ambiguity

Prefix [1,2,3] has minimum order2 and admits [1,1] and [0,3], predicting5 and6 respectively at the next position. A chosen recurrence is a compatible continuation, not inference of a uniquely determined infinite source.

### lag_orientation

Return c[j]=-connection[j+1] modulo p so c[0] multiplies the immediately previous term. For positive L use initial=s[..L] with linear_recurrence::nth_term and modulus p. Empty L must be handled separately because nth_term rejects empty order.

### field_inversion

Every saved previous discrepancy is nonzero and p=998244353 is prime, so previous^(p-2) is its inverse. Composite or caller-selected moduli are outside this API. Zero discrepancy performs no inversion and only increments shift.

### normalization_overflow

All raw u64 values are reduced before multiplication. For p=998244353, (p-1)^2<2^60; multiplication fits u64, and addition/subtraction intermediates are below2p. With n<=4096, n+1,2L and shifts fit usize. Congruent representatives yield identical output.

### validation_partition

n>4096 returns TooManyTerms before any allocation; otherwise fallible reservations can return AllocationFailed. Empty prefixes still allocate connection arrays and may fail allocation. No allocator-failure injection or memory exhaustion guarantee is claimed.

#### Delayed nonzero prefix (review 2026-11-01)

For n>=1 and a nonzero residue a, the prefix 0^(n-1),a has minimum order n: for each k<n its last required equation has zero lag inputs and nonzero right side, whereas k=n has no required equations. The concrete discrepancy schedule returns [0^(n-1),a], even though every length-n coefficient vector is compatible with this prefix. Before the last term all discrepancies vanish; at the last, shift=n, previous=1, and the update puts -a in connection position n. Thus compatibility and minimality do not determine the chosen coefficients. For n=3, [0,0,1] is compatible with [0,0,0] but the API selects [0,0,1]. Congruent raw inputs share the output; this is a partial converse fiber, not a complete characterization. The separate all-zero prefix returns empty. This source argument assumes successful allocation and the declared prime field; finite probes are not a formal proof of the implementation.

### evidence

#### Evidence, 2026-10-30

Four tests per module pass twice debug and twice release with equal normalized identities. Independent production and oracle mutations compile and fail named assertions; exact source bytes are restored and positives rerun. Strict algorithm all-target Clippy and narrow formatting are checked. Raw logs: $MOVA_DATA/runs/octopus-wave11-numeric-2026-10-30/.

- berlekamp_massey-false-1.log: `3d0c05e1f337d6eec3620a0dcd4d81014c4099882f5b71529b0bf80ad2ba737f`
- berlekamp_massey-true-2.log: `128b20a6296b8e867006955772095ce97146c8c5feee18e9cbca549573a2f8cb`
- control-berlekamp_massey-mod.rs.log: `428009d17205e1508fae49cf8ad7337ae3acca42a7cf085e3812390231acce56`

##### Independent review, 2026-11-01

A source-bound standalone Rust probe exercised 320 delayed-nonzero prefixes (lengths 1 through 64 and five nonzero raw representatives), independently checked the contradictory last equation for every shorter order, and checked the concrete selected coefficients and a congruent-input fiber. Two outputs matched. An initial hypothesis that the selected vector was all zeros failed immediately on [1]: the implementation returns [1]. The all-zero vector is compatible at order one, but compatibility does not specify the deterministic tie choice. Allocator failure, other prefixes and a formal source proof remain outside this observation. Raw probe, failed exploration, hypothesis and logs are retained in the independent review cycle directory under `$MOVA_DATA/runs/`.