Rational reconstruction via reconstruct

[JohnAAbbott]

Describe the bug
Seems not to work if the residue is large (compared the modulus)

To Reproduce
Steps to reproduce the behavior, please provide a code snippet that triggers
the bug.

using Oscar
m = ZZ(536870923);
m2 = m^2;

b = ZZ(-133938711504058062521343586503804797493927382774057437847102718821399120752284154595014137517805073862154012246567574121259948634520322906545919708367827740890559457959928206211377205431569213484206966838991149);

mod(27*b, m2)  # gives 1
reconstruct(mod(b,m2), m2)  # gives 1//27
reconstruct(mod(-b,m2), m2) # gives -1//27
reconstruct(b,m2)  # just returns b
reconstruct(-b,m2)  # gives "ERROR: Impossible rational reconstruction"

# Maybe I understand why the word "attempt" is in the doc!

Expected behavior
Either fix the doc so that its says that the residue must be reduced (and in what way), or fix the implementation so that it accepts large residues.

System (please complete the following information):
Please paste the output of Oscar.versioninfo(full=true) below. If this does
not work, please paste the output of Julia's versioninfo() and your Oscar
version.

julia> Oscar.versioninfo(full=true)
OSCAR version 1.2.0-DEV - #master, 38f37bc2ae -- 2024-09-23 13:32:14 +0000
  combining:
    AbstractAlgebra.jl   v0.43.1
    GAP.jl               v0.11.4
    Hecke.jl             v0.34.3
    Nemo.jl              v0.47.1
    Polymake.jl          v0.11.21
    Singular.jl          v0.23.7
  building on:
    FLINT_jll               v300.100.300+0
    GAP_jll                 v400.1300.102+0
    Singular_jll            v404.0.605+0
    libpolymake_julia_jll   v0.12.1+0
    libsingular_julia_jll   v0.45.4+0
    polymake_jll            v400.1200.1+0
See `]st -m` for a full list of dependencies.

Julia Version 1.10.5
Commit 6f3fdf7b362 (2024-08-27 14:19 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 20 × Intel(R) Core(TM) i9-10900 CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, skylake)
Threads: 1 default, 0 interactive, 1 GC (on 20 virtual cores)
Environment:
  JULIA_LOAD_PATH = @:@v#.#:@stdlib:/environments/globalenv
  JULIA_DEPOT_PATH = /home/zez25zuh/.julia:
Official https://julialang.org/ release
...

Additional context
@which says the relevant code is in ~/.julia/packages/Nemo/tzyHK/src/flint/fmpq.jl:793

[fieker]

On Tue, Sep 24, 2024 at 09:38:58AM -0700, JohnAAbbott wrote: **Describe the bug** Seems not to work if the residue is large (compared the modulus) **To Reproduce** Steps to reproduce the behavior, please provide a code snippet that triggers the bug. ``` using Oscar m = ZZ(536870923); m2 = m^2; b = ZZ(-133938711504058062521343586503804797493927382774057437847102718821399120752284154595014137517805073862154012246567574121259948634520322906545919708367827740890559457959928206211377205431569213484206966838991149); mod(27*b, m2) # gives 1 reconstruct(mod(b,m2), m2) # gives 1//27 reconstruct(mod(-b,m2), m2) # gives -1//27 reconstruct(b,m2) # just returns b reconstruct(-b,m2) # gives "ERROR: Impossible rational reconstruction" # Maybe I understand why the word "attempt" is in the doc! ``` **Expected behavior** Either fix the doc so that its says that the residue must be reduced (and in what way), or fix the implementation so that it accepts large residues. **System (please complete the following information):** Please paste the output of `Oscar.versioninfo(full=true)` below. If this does not work, please paste the output of Julia's `versioninfo()` and your Oscar version. ``` julia> Oscar.versioninfo(full=true) OSCAR version 1.2.0-DEV - #master, 38f37bc -- 2024-09-23 13:32:14 +0000 combining: AbstractAlgebra.jl v0.43.1 GAP.jl v0.11.4 Hecke.jl v0.34.3 Nemo.jl v0.47.1 Polymake.jl v0.11.21 Singular.jl v0.23.7 building on: FLINT_jll v300.100.300+0 GAP_jll v400.1300.102+0 Singular_jll v404.0.605+0 libpolymake_julia_jll v0.12.1+0 libsingular_julia_jll v0.45.4+0 polymake_jll v400.1200.1+0 See `]st -m` for a full list of dependencies. Julia Version 1.10.5 Commit 6f3fdf7b362 (2024-08-27 14:19 UTC) Build Info: Official https://julialang.org/ release Platform Info: OS: Linux (x86_64-linux-gnu) CPU: 20 × Intel(R) Core(TM) i9-10900 CPU @ 2.80GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-15.0.7 (ORCJIT, skylake) Threads: 1 default, 0 interactive, 1 GC (on 20 virtual cores) Environment: JULIA_LOAD_PATH = @***@***.******@***.***:/environments/globalenv JULIA_DEPOT_PATH = /home/zez25zuh/.julia: Official https://julialang.org/ release ... ``` **Additional context** ***@***.***` says the relevant code is in `~/.julia/packages/Nemo/tzyHK/src/flint/fmpq.jl:793` -- Reply to this email directly or view it on GitHub: #4146 You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

Wrong system: julia> methods(reconstruct) # 8 methods for generic function "reconstruct" from Nemo: [1] reconstruct(a::ZZRingElem, m::ZZRingElem) @ ~/.julia/dev/Nemo/src/flint/fmpq.jl:793

[fieker]

On Tue, Sep 24, 2024 at 09:38:58AM -0700, JohnAAbbott wrote: **Describe the bug** Seems not to work if the residue is large (compared the modulus) **To Reproduce** Steps to reproduce the behavior, please provide a code snippet that triggers the bug. ``` using Oscar m = ZZ(536870923); m2 = m^2; b = ZZ(-133938711504058062521343586503804797493927382774057437847102718821399120752284154595014137517805073862154012246567574121259948634520322906545919708367827740890559457959928206211377205431569213484206966838991149); mod(27*b, m2) # gives 1 reconstruct(mod(b,m2), m2) # gives 1//27 reconstruct(mod(-b,m2), m2) # gives -1//27 reconstruct(b,m2) # just returns b reconstruct(-b,m2) # gives "ERROR: Impossible rational reconstruction" # Maybe I understand why the word "attempt" is in the doc! ``` **Expected behavior** Either fix the doc so that its says that the residue must be reduced (and in what way), or fix the implementation so that it accepts large residues. **System (please complete the following information):** Please paste the output of `Oscar.versioninfo(full=true)` below. If this does not work, please paste the output of Julia's `versioninfo()` and your Oscar version. ``` julia> Oscar.versioninfo(full=true) OSCAR version 1.2.0-DEV - #master, 38f37bc -- 2024-09-23 13:32:14 +0000 combining: AbstractAlgebra.jl v0.43.1 GAP.jl v0.11.4 Hecke.jl v0.34.3 Nemo.jl v0.47.1 Polymake.jl v0.11.21 Singular.jl v0.23.7 building on: FLINT_jll v300.100.300+0 GAP_jll v400.1300.102+0 Singular_jll v404.0.605+0 libpolymake_julia_jll v0.12.1+0 libsingular_julia_jll v0.45.4+0 polymake_jll v400.1200.1+0 See `]st -m` for a full list of dependencies. Julia Version 1.10.5 Commit 6f3fdf7b362 (2024-08-27 14:19 UTC) Build Info: Official https://julialang.org/ release Platform Info: OS: Linux (x86_64-linux-gnu) CPU: 20 × Intel(R) Core(TM) i9-10900 CPU @ 2.80GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-15.0.7 (ORCJIT, skylake) Threads: 1 default, 0 interactive, 1 GC (on 20 virtual cores) Environment: JULIA_LOAD_PATH = @***@***.******@***.***:/environments/globalenv JULIA_DEPOT_PATH = /home/zez25zuh/.julia: Official https://julialang.org/ release ... ``` **Additional context** ***@***.***` says the relevant code is in `~/.julia/packages/Nemo/tzyHK/src/flint/fmpq.jl:793` -- Reply to this email directly or view it on GitHub: #4146 You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

Dispatches directly to c/flint int fmpq_reconstruct_fmpz(fmpq_t res, const fmpz_t a, const fmpz_t m) Reconstructs a rational number from its residue a modulo m, returning 1 if successful and 0 if no solution exists. Uses the balanced bounds My guess is that this implies input to be 0 <= a < m as residues in Nemo are non-negative and bounded.

[JohnAAbbott]

@fieker says that the Flint documentation does clarify the conditions on the args.
@fieker and I propose removing the current reconstruct, and renaming unsafe_reconstruct to reconstruct: this effectively eliminate the throwing version, and replaces it with a version returning a tuple (Bool, QQFieldElem) where the first component is true iff reconstruction succeeded (in which case the second component contains the reconstructed value, obviously).
Note that there is also the function (family) rational_reconstruction which seems to duplicate the functionality, but is implemented in pure Julia (i.e. independent of Flint). Can these two families be (euphemistically) ) "rationalized"?

[JohnAAbbott]

A quick check (for just a single "random" input) suggests that reconstruct and rational_reconstruction have essentially identical performance according to @time: namely, same time and same memory allocation, within experimental error.

[JohnAAbbott]

There appears to be a bug in the call to fmpq_reconstruct_fmpz in file Hecke/src/Misc/RatRecon.jl near lines 92 and 110: the 2nd arg to ccall should be Cint rather than Int

[thofma]

@fieker says that the Flint documentation does clarify the conditions on the args. @fieker and I propose removing the current reconstruct, and renaming unsafe_reconstruct to reconstruct: this effectively eliminate the throwing version, and replaces it with a version returning a tuple (Bool, QQFieldElem) where the first component is true iff reconstruction succeeded (in which case the second component contains the reconstructed value, obviously). Note that there is also the function (family) rational_reconstruction which seems to duplicate the functionality, but is implemented in pure Julia (i.e. independent of Flint). Can these two families be (euphemistically) ) "rationalized"?

Does this mean changing the behaviour of reconstruct? If so, since this is exported and part of the API, it is a bit cumbersome to do this properly. See also Nemocas/Nemo.jl#1599 regarding the naming.

[JohnAAbbott]

On my local machine I commented out all the reconstruct methods, and the corresponding tests (in the Nemo subtree). All remaining Oscar tests passed (ah, but I didn't try the doctests). I find the name reconstruct is less mnemonic than rational_reconstruct. It makes sense to me to render reconstruct obsolete/deprecated, and make it indicate rational_reconstruct as a drop-in replacement. This would require a minor change to the code referred to in #1599; that PR does already refer to this issue.