Cryptography Reference
In-Depth Information
Where
g
is the Goppa polynomial and the
v
if
is values will be computed through
the execution of Algorithm 1.
Algorithm 1.
Decoding
p
-ary square-free Goppa codes
Input:
Γ
(
L, g
), a Goppa code over
F
p
where
g
is square-free.
H ∈
F
r×n
q
Input:
, a parity-check matrix in the form of Equation 1.
Input:
c
=
c
+
e ∈
F
p
, the received codeword with errors.
Output:
set of corrected codeword
c ∈ Γ
(
L, g
)(
∅
upon failure).
s
T
← Hc
T
∈
F
q
,
s
e
(
x
)
←
if
s
if
x
if
.
N.B.
Hc
T
=
He
T
.
if
s
−
1
e
(
x
)mod
g
(
x
)
then
return
∅
g
(
x
)iscomposite
end if
S ←
∅
for
φ ←
1
to
p −
1
do
guess the correct scale factor
φ
for
k ←
1
to
p −
1
do
u
k
(
x
)
← x
k
+
φkx
k−
1
/s
e
(
x
)mod
g
(
x
)
if
p
u
k
(
x
)mod
g
(
x
)
then
try next
φg
(
x
)iscomposite
end if
v
k
(
x
)
←
p
u
k
(
x
)mod
g
(
x
)
end for
Build the lattice basis
A
defined by Equation 5.
Apply
WeakPopovForm
(Algorithm 2) to reduce the basis of Λ(
A
).
for
i ←
1
to
p
do
a ← A
if
with
a
j
indices in range 0
...p−
1
for
j ←
0
to
p −
1
do
if
deg(
a
j
)
>
(
t − j
)
/p
then
try next
if
not a solution
end if
end for
σ
(
x
)
←
j
x
j
a
j
(
x
)
p
Compute the set
J
such that
σ
(
L
j
)=0,
∀j ∈ J
.
for
j ∈ J
do
Compute the multiplicity
μ
j
of
L
j
.
e
j
← φμ
j
end for
if
He
T
=
s
T
then
S ← S ∪{c
− e}
end if
end for
return
S
end for
