galois-constacyclic-implementation.magma•11.1 kB
// Galois Constacyclic Code Implementation
// Based on the algorithm in main.tex
// Function to calculate p-adic valuation
function pAdicValuation(n, p)
v := 0;
temp := n;
while temp mod p eq 0 do
v := v + 1;
temp := temp div p;
end while;
return v, temp;
end function;
// Function to compute modular inverse
function ModularInverse(a, m)
return InverseMod(a, m);
end function;
// Function to construct 1 + r*Z_{n'r}
function Construct1PlusRZnr(r, npr)
result := {};
for k := 0 to npr-1 do
val := (1 + r*k) mod npr;
if val ne 0 then
Include(~result, val);
end if;
end for;
return result;
end function;
// Function to compute q-cosets (orbits under multiplication by q)
function ComputeQCosets(S, q, npr)
cosets := [];
remaining := S;
while not IsEmpty(remaining) do
x := Representative(remaining);
orbit := {};
current := x;
repeat
Include(~orbit, current);
Exclude(~remaining, current);
current := (current * q) mod npr;
until current eq x or current notin S;
if #orbit gt 0 then
Append(~cosets, orbit);
end if;
end while;
return cosets;
end function;
// Function to compute (-p^h)-orbits on q-cosets
function ComputeMinusPHOrbits(cosets, p, h, npr)
orbits := [];
remaining := {@ i : i in [1..#cosets] @};
minusph := (-p^h) mod npr;
while not IsEmpty(remaining) do
start_idx := Representative(remaining);
orbit := [];
current_idx := start_idx;
repeat
Append(~orbit, current_idx);
Exclude(~remaining, current_idx);
// Find next coset under multiplication by -p^h
current_coset := cosets[current_idx];
rep := Representative(current_coset);
next_rep := (rep * minusph) mod npr;
// Find which coset contains next_rep
found := false;
for j in remaining do
if next_rep in cosets[j] then
current_idx := j;
found := true;
break;
end if;
end for;
if not found then
break;
end if;
until current_idx eq start_idx;
if #orbit gt 0 then
Append(~orbits, orbit);
end if;
end while;
return orbits;
end function;
// Main function implementing the algorithm
function GaloisConstacyclicCode(p, e, h, n, lambda)
printf "=== Galois Constacyclic Code Construction ===\n";
printf "Parameters: p=%o, e=%o, h=%o, n=%o, lambda=%o\n", p, e, h, n, lambda;
// Step 1: Calculate v_p(n) and n'
vp_n, n_prime := pAdicValuation(n, p);
printf "v_p(n) = %o, n' = %o\n", vp_n, n_prime;
// Calculate r (order of lambda)
q := p^e;
F := GF(q);
lambda_F := F!lambda;
r := Order(lambda_F);
printf "q = %o, r = order(lambda) = %o\n", q, r;
npr := n_prime * r;
printf "n'r = %o\n", npr;
// Step 2: Construct 1 + r*Z_{n'r}
S := Construct1PlusRZnr(r, npr);
printf "1 + r*Z_{n'r} = %o\n", S;
printf "|1 + r*Z_{n'r}| = %o\n", #S;
// Step 3: Calculate q-cosets
cosets := ComputeQCosets(S, q, npr);
printf "\nq-cosets:\n";
for i := 1 to #cosets do
printf "Q_%o = %o\n", Representative(cosets[i]), cosets[i];
end for;
printf "Number of q-cosets: %o\n", #cosets;
// Step 4: If p != 2, calculate (-p^h)-orbits
orbits := [];
if p ne 2 then
orbits := ComputeMinusPHOrbits(cosets, p, h, npr);
printf "\n(-p^h)-orbits on cosets:\n";
for i := 1 to #orbits do
orbit_reps := [Representative(cosets[j]) : j in orbits[i]];
printf "Orbit %o: %o\n", i, orbit_reps;
end for;
end if;
// Step 5: Define q-coset function phi
// For this example, we use the pattern from the paper
phi := AssociativeArray();
if p eq 2 then
// Case (i): p = 2
val := (1/2) * 2^vp_n;
for i := 1 to #cosets do
rep := Representative(cosets[i]);
phi[rep] := Integers()!val;
end for;
else
// Cases (ii)-(iv): Use the orbit pattern with d = 0
d := 0;
for i := 1 to #orbits do
orbit := orbits[i];
for j := 1 to #orbit do
coset_idx := orbit[j];
rep := Representative(cosets[coset_idx]);
if IsEven(j-1) then
phi[rep] := d;
else
phi[rep] := p^vp_n - d;
end if;
end for;
end for;
end if;
printf "\nq-coset function phi:\n";
for rep in Keys(phi) do
printf "phi(Q_%o) = %o\n", rep, phi[rep];
end for;
// Step 6: Construct polynomial f_phi(X)
// We need a primitive n'r-th root of unity
// Find the order of q in Z_{n'r}^*
d_order := 1;
temp := q mod npr;
while temp ne 1 do
d_order := d_order + 1;
temp := (temp * q) mod npr;
end while;
printf "\nOrder of q in Z_{n'r}^* = %o\n", d_order;
// Construct the extension field
Fext := GF(q^d_order);
printf "Working in extension field GF(%o)\n", q^d_order;
// Find a primitive npr-th root of unity
// We need an element of order npr in the multiplicative group
found := false;
theta := Fext!0;
for attempts := 1 to 100 do
candidate := Random(Fext);
if candidate ne 0 and Order(candidate) eq npr then
theta := candidate;
found := true;
break;
end if;
end for;
if not found then
printf "Warning: Could not find primitive %o-th root of unity, using generator^k\n", npr;
gen := PrimitiveElement(Fext);
k := (#Fext - 1) div npr; // This should make gen^k have order npr
theta := gen^k;
if Order(theta) ne npr then
printf "Error: Could not construct primitive root of unity\n";
return 0;
end if;
end if;
printf "Found primitive %o-th root of unity\n", npr;
// Step 7: Construct f_phi(X) polynomial
printf "\nConstructing polynomial f_phi(X)...\n";
// Create polynomial ring over the extension field
PX<X> := PolynomialRing(Fext);
// Construct f_phi(X) = prod_{Q in cosets} f_Q(X)^phi(Q)
// where f_Q(X) = prod_{i in Q} (X - theta^i)
f_phi := PX!1;
for i := 1 to #cosets do
coset := cosets[i];
rep := Representative(coset);
phi_val := phi[rep];
if phi_val gt 0 then
// Construct f_Q(X) = prod_{j in coset} (X - theta^j)
f_Q := PX!1;
for j in coset do
f_Q := f_Q * (X - theta^j);
end for;
// Raise to power phi(Q)
f_phi := f_phi * f_Q^phi_val;
printf "Added coset Q_%o with phi(Q) = %o, |Q| = %o\n", rep, phi_val, #coset;
end if;
end for;
printf "Constructed polynomial f_phi(X) of degree %o\n", Degree(f_phi);
// Convert polynomial to base field if possible
// For the constacyclic code, we need the polynomial over the base field F
try
// Get coefficients and try to express them in base field
coeffs := Coefficients(f_phi);
PX_base<X> := PolynomialRing(F);
f_phi_base := PX_base!0;
for k := 1 to #coeffs do
// Try to find the trace or norm that maps to base field
coeff_base := Trace(coeffs[k]) / Degree(Fext, F);
f_phi_base := f_phi_base + coeff_base * X^(k-1);
end for;
f_phi := f_phi_base;
printf "Converted polynomial to base field F\n";
catch e
printf "Warning: Could not convert to base field, using extension field polynomial\n";
end try;
// Step 8: Create the constacyclic code
printf "\nCreating constacyclic code...\n";
// Use MAGMA's ConstaCyclicCode function
// ConstaCyclicCode(length, generator_polynomial, lambda)
try
C := ConstaCyclicCode(n, f_phi, lambda);
printf "Successfully created constacyclic code: %o\n", C;
// Get basic properties
printf "Code parameters: [%o, %o, %o]\n", Length(C), Dimension(C), MinimumDistance(C);
return rec< recformat< p, e, h, n, lambda, vp_n, n_prime, r, npr,
S, cosets, orbits, phi, theta, f_phi, code > |
p := p, e := e, h := h, n := n, lambda := lambda,
vp_n := vp_n, n_prime := n_prime, r := r, npr := npr,
S := S, cosets := cosets, orbits := orbits, phi := phi,
theta := theta, f_phi := f_phi, code := C >;
catch e
printf "Error creating constacyclic code: %o\n", e;
printf "Using CyclicCode instead...\n";
// Fallback: try using CyclicCode if ConstaCyclicCode doesn't work
try
C := CyclicCode(f_phi);
printf "Created cyclic code as fallback: %o\n", C;
return rec< recformat< p, e, h, n, lambda, vp_n, n_prime, r, npr,
S, cosets, orbits, phi, theta, f_phi, code > |
p := p, e := e, h := h, n := n, lambda := lambda,
vp_n := vp_n, n_prime := n_prime, r := r, npr := npr,
S := S, cosets := cosets, orbits := orbits, phi := phi,
theta := theta, f_phi := f_phi, code := C >;
catch e2
printf "Error with CyclicCode: %o\n", e2;
return rec< recformat< p, e, h, n, lambda, vp_n, n_prime, r, npr,
S, cosets, orbits, phi, theta, f_phi > |
p := p, e := e, h := h, n := n, lambda := lambda,
vp_n := vp_n, n_prime := n_prime, r := r, npr := npr,
S := S, cosets := cosets, orbits := orbits, phi := phi,
theta := theta, f_phi := f_phi >;
end try;
end try;
end function;
// Example from the paper
function ExampleFromPaper()
printf "\n" * "=" * 60;
printf "\nRunning Example from Paper\n";
printf "=" * 60 * "\n";
// Parameters: p=5, e=2, h=1, r=2 (lambda=-1), n=26
p := 5; e := 2; h := 1; n := 26;
q := p^e; // q = 25
F := GF(q);
lambda := F!(-1); // lambda = -1, which should have order 2
result := GaloisConstacyclicCode(p, e, h, n, lambda);
printf "\n" * "=" * 60;
printf "\nConstruction completed successfully!\n";
printf "Parameters stored for further processing.\n";
printf "=" * 60 * "\n";
return result;
end function;
// Run the example
printf "Starting Galois Constacyclic Code Implementation\n\n";
example_result := ExampleFromPaper();