nmod_poly_sqrt method does not work for ZZ_16 and some non integral domains #2508
Description
Describe the bug
for non-integral domain ZZ_n, we can not verify an element in its polynomial ring is is_square or not
An Example:
If f is a poynomial in ZZ_16[x], for f=x+4, then f^2==x^2+8x, but flint said it is not is_square. I think it is not the normal behavior. And the document does not require it must be a prime number.
Steps to reproduce
#include <stddef.h>
#include <stdio.h>
#include "flint.h"
#include "nmod_poly.h"
static void print_poly(const char *label, const nmod_poly_t poly)
{
flint_printf("%s", label);
nmod_poly_print_pretty(poly, "x");
flint_printf("\n");
}
static int verify_modulus(ulong modulus)
{
nmod_poly_t lin, square, root, check;
slong failures = 0;
ulong special_const = modulus / 4; /* demonstration shift */
nmod_poly_init(lin, modulus);
nmod_poly_init(square, modulus);
nmod_poly_init(root, modulus);
nmod_poly_init(check, modulus);
nmod_poly_zero(lin);
nmod_poly_set_coeff_ui(lin, 1, 1);
nmod_poly_set_coeff_ui(lin, 0, special_const);
nmod_poly_mul(square, lin, lin);
if (!nmod_poly_sqrt(root, square))
{
flint_printf("Failed demonstration sqrt for modulus %lu\n", (unsigned long) modulus);
failures = 1;
goto cleanup;
}
nmod_poly_mul(check, root, root);
if (!nmod_poly_equal(check, square))
{
flint_printf("Failed demonstration sqrt for modulus %lu\n", (unsigned long) modulus);
failures = 1;
goto cleanup;
}
print_poly("Test square = ", square);
print_poly("Recovered sqrt = ", root);
for (ulong a = 0; a < modulus; a++)
{
for (ulong b = 0; b < modulus; b++)
{
nmod_poly_zero(lin);
nmod_poly_set_coeff_ui(lin, 0, b);
if (a != 0)
nmod_poly_set_coeff_ui(lin, 1, a);
nmod_poly_mul(square, lin, lin);
if (!nmod_poly_sqrt(root, square))
{
flint_printf("sqrt failed for modulus %lu, (%lu x + %lu)^2\n",
(unsigned long) modulus, (unsigned long) a, (unsigned long) b);
failures++;
continue;
}
nmod_poly_mul(check, root, root);
if (!nmod_poly_equal(check, square))
{
flint_printf("sqrt mismatch for modulus %lu, (%lu x + %lu)^2\n",
(unsigned long) modulus, (unsigned long) a, (unsigned long) b);
failures++;
}
}
}
cleanup:
if (failures == 0)
flint_printf("All (ax + b)^2 polynomials over Z/%luZ were confirmed as squares.\n",
(unsigned long) modulus);
else
flint_printf("Encountered %ld failures for modulus %lu.\n", (long) failures,
(unsigned long) modulus);
nmod_poly_clear(lin);
nmod_poly_clear(square);
nmod_poly_clear(root);
nmod_poly_clear(check);
return failures == 0;
}
int main(void)
{
const ulong moduli[] = {6, 9, 12, 16, 24, 36};
int overall = 1;
for (size_t i = 0; i < sizeof(moduli) / sizeof(moduli[0]); i++)
{
flint_printf("\n--- Testing modulus %lu ---\n", (unsigned long) moduli[i]);
if (!verify_modulus(moduli[i]))
overall = 0;
}
return overall ? 0 : 1;
}
It raise error, can not reconginzed it is square.
Expected behavior
It should pass the test.
System (please complete the following information):
- System CPU: Ubuntu-25.10 -x86-64
- Version of FLINT (if using Git, please specify commit): 3.4.0
- How FLINT was configured (i.e. options pushed): normal, do not add another flags
Output of
configurechecking build system type... x86_64-pc-linux-gnu checking host system type... x86_64-pc-linux-gnu checking how to print strings... printf checking for gcc... gcc checking whether the C compiler works... yes checking for C compiler default output file name... a.out checking for suffix of executables... checking whether we are cross compiling... no checking for suffix of object files... o checking whether the compiler supports GNU C... yes checking whether gcc accepts -g... yes checking for gcc option to enable C11 features... none needed checking for a sed that does not truncate output... /usr/bin/sed checking for grep that handles long lines and -e... /usr/bin/grep checking for egrep... /usr/bin/grep -E checking for fgrep... /usr/bin/grep -F checking for ld used by gcc... /usr/bin/x86_64-linux-gnu-ld checking if the linker (/usr/bin/x86_64-linux-gnu-ld) is GNU ld... yes checking for BSD- or MS-compatible name lister (nm)... /usr/bin/nm -B checking the name lister (/usr/bin/nm -B) interface... BSD nm checking whether ln -s works... yes checking the maximum length of command line arguments... 1572864 checking how to convert x86_64-pc-linux-gnu file names to x86_64-pc-linux-gnu format... func_convert_file_noop checking how to convert x86_64-pc-linux-gnu file names to toolchain format... func_convert_file_noop checking for /usr/bin/x86_64-linux-gnu-ld option to reload object files... -r checking for file... file checking for objdump... objdump checking how to recognize dependent libraries... pass_all checking for dlltool... no checking how to associate runtime and link libraries... printf %s\n checking for ranlib... ranlib checking for ar... ar checking for archiver @FILE support... @ checking for strip... strip checking for gawk... gawk checking command to parse /usr/bin/nm -B output from gcc object... ok checking for sysroot... no checking for a working dd... /usr/bin/dd checking how to truncate binary pipes... /usr/bin/dd bs=4096 count=1 checking for mt... no checking if : is a manifest tool... no checking for stdio.h... yes checking for stdlib.h... yes checking for string.h... yes checking for inttypes.h... yes checking for stdint.h... yes checking for strings.h... yes checking for sys/stat.h... yes checking for sys/types.h... yes checking for unistd.h... yes checking for dlfcn.h... yes checking for objdir... .libs checking if gcc supports -fno-rtti -fno-exceptions... no checking for gcc option to produce PIC... -fPIC -DPIC checking if gcc PIC flag -fPIC -DPIC works... yes checking if gcc static flag -static works... yes checking if gcc supports -c -o file.o... yes checking if gcc supports -c -o file.o... (cached) yes checking whether the gcc linker (/usr/bin/x86_64-linux-gnu-ld -m elf_x86_64) supports shared libraries... yes checking whether -lc should be explicitly linked in... no checking dynamic linker characteristics... GNU/Linux ld.so checking how to hardcode library paths into programs... immediate checking whether stripping libraries is possible... yes checking if libtool supports shared libraries... yes checking whether to build shared libraries... yes checking whether to build static libraries... no checking for a race-free mkdir -p... mkdir -p checking how to run the C preprocessor... gcc -E checking if compiler is GCC... yes checking if compiler is Clang... no checking for inline... inline checking whether byte ordering is bigendian... no checking if memory is strongly-ordered... yes checking for gmp.h... yes checking if version of GMP is greater than 6.2.1... yes checking if GMP defines mp_limb_t as unsigned long long int... no checking for mpfr.h... yes checking if version of MPFR is greater than 4.1.0... yes checking for desired ABI... 64 checking for stdarg.h... yes checking for math.h... yes checking for float.h... yes checking for errno.h... yes checking for fenv.h... yes checking for alloca.h... yes checking for malloc.h... yes checking for sys/param.h... yes checking for windows.h... no checking for pthread_np.h... no checking for pthread.h... yes checking for library containing atan2... -lm checking for library containing __gmpz_init... -lgmp checking for library containing __gmpn_mul_basecase... none required checking for library containing __gmpn_gcd_11... none required checking for library containing __gmpn_div_q... none required checking for library containing __gmpn_invert_limb... none required checking for library containing __gmpn_modexact_1_odd... none required checking for library containing __gmpn_addmul_2... none required checking for library containing __gmpn_add_n_sub_n... none required checking for library containing __gmpn_add_nc... none required checking for library containing __gmpn_sub_nc... none required checking for library containing __gmpn_addlsh1_n... none required checking for library containing __gmpn_addlsh1_n_ip1... no checking for library containing __gmpn_rsh1sub_n... none required checking for library containing __gmpn_rsh1add_n... none required checking for library containing mpfr_init... -lmpfr checking for library containing mpfr_round_p... none required checking for library containing mpfr_mulhigh_n... none required checking for library containing mpfr_sqrhigh_n... none required checking whether gcc accepts -pthread... yes checking if cpu_set_t is supported... yes checking if alloca works... yes checking for aligned_alloc... yes checking for _aligned_malloc... no checking whether gcc accepts -O3... yes checking whether gcc accepts -pedantic... yes checking whether gcc accepts -std=c11... yes checking whether gcc accepts -Wall... yes checking whether gcc accepts -Werror=implicit-function-declaration... yes checking whether gcc accepts -Werror=newline-eof... no checking whether gcc accepts -Wno-stringop-overread... yes checking whether gcc accepts -Wno-stringop-overflow... yes checking whether gcc accepts -Wmissing-prototypes... yes checking whether gcc accepts -funroll-loops... yes checking for immintrin.h... yes checking if system have required x86_64 instruction set for fft_small... no checking if system can use FLINT's fft_small module... no configure: WARNING: Currently no assembly available for x86_64-pc-linux-gnu. Disabling assembly... checking how to switch to text section... .text checking for assembler label suffix... : checking for assembler local label prefix... .L configure: creating ./config.status config.status: creating Makefile config.status: creating flint.pc config.status: creating src/flint.h config.status: creating src/config.h config.status: src/config.h is unchanged config.status: creating src/flint-config.h config.status: src/flint-config.h is unchanged config.status: linking src/gmpcompat.h.in to src/gmpcompat.h config.status: linking src/mpn_extras/x86_64/flint-mparam.h to src/flint-mparam.h config.status: linking src/fmpz/link/fmpz_single.c to src/fmpz/fmpz.c config.status: executing libtool commands
Additional context
I think it is not proper implemented. It should be implemented with CRT and Hensel lift to deal with the problem in each ZZ_p^n. The method implemented now is only proper for n=p, but not for a non-integral ring