bug? in amodgcd

[Qian Yun]

I hate the behavior that some people opening issues/pull requests
that are generated by LLM without human reviews to rule out
hallucination.

But this one is beyond my understanding of code.

From the surface of it, the original code is highly suspicious.

I have trace the value change of "t0" during execution of
src/input/agcd.input, it is different before/after the patch.

But it does not affect any results, because "extended_gcd"
returns [r1, s1, t1], and current code only uses r1 and s1.

- Qian

diff --git a/src/algebra/amodgcd.spad b/src/algebra/amodgcd.spad
index a4d2745b..4e39df7a 100644
--- a/src/algebra/amodgcd.spad
+++ b/src/algebra/amodgcd.spad
@@ -875,7 +875,7 @@
t0 := c1*t0 - cm*t1
r0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), r0)
s0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), s0)
- t0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), r0)
+ t0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), t0)
(r0, r1) := (r1, r0)
(s0, s1) := (s1, s0)
(t0, t1) := (t1, t0)

[Waldek Hebisch]

On Sun, Apr 19, 2026 at 06:52:29AM +0800, Qian Yun wrote:
> I hate the behavior that some people opening issues/pull requests
> that are generated by LLM without human reviews to rule out
> hallucination.
>
> But this one is beyond my understanding of code.

I wrote a comment in 'extended_gcd':

-- invariant r0 = s0*x + t0*y, r1 = s1*x + t1*y

which means that the equality is supposed to hold at start
and end of loop body (that is what "invariant" means).
Once you notice that in the inner loop we have

new_r0 = c1*old_r0 - cm*r1

you will see that in the inner loop assignments after assignment
to r1 restore the invariant (so invariant really holds for the inner
loop). The 'map' calls after inner loop should not change logical
value, they just change representation. So, having r1 in assignment
to t0 is wrong. And when this is fixed the 3 'map' calls
also preserve invariant. The final 3 assignments in the outer
loop just exchange both triples, so also preserve the invariant.

> >From the surface of it, the original code is highly suspicious.

Yes, we should change this.

> I have trace the value change of "t0" during execution of
> src/input/agcd.input, it is different before/after the patch.
>
> But it does not affect any results, because "extended_gcd"
> returns [r1, s1, t1], and current code only uses r1 and s1.

Yes.

> - Qian
>
> diff --git a/src/algebra/amodgcd.spad b/src/algebra/amodgcd.spad
> index a4d2745b..4e39df7a 100644
> --- a/src/algebra/amodgcd.spad
> +++ b/src/algebra/amodgcd.spad
> @@ -875,7 +875,7 @@
> t0 := c1*t0 - cm*t1
> r0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), r0)
> s0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), s0)
> - t0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), r0)
> + t0 := map((c : MP) : MP +-> mreduction1(c, lm, lv, p), t0)
> (r0, r1) := (r1, r0)
> (s0, s1) := (s1, s0)
> (t0, t1) := (t1, t0)
>

--
Waldek Hebisch

[Qian Yun]

Hi Waldek,

You should do the commit.

- Qian