Mod poly and mpn_mod random generation

[dlesnoff]

Follow-up of #2430 . Adds a rand function:

• [x] nmod_poly
• [x] nmod_poly_mat
• [x] mpn_mod
• [x] fmpz_mod_poly

It seems that implementations of nmod_mpoly randtest functions generate uniformly random coefficients. I did not add rand functions for basic types like fmpz_mod nor nmod. I plan to add a rand function for mpn_mod_poly and mpn_mod_mat. Please forgive me, I based my branch on my previously non-merged branch and it needs some cleanup.

[fredrik-johansson]

Please forgive me, I based my branch on my previously non-merged branch and it needs some cleanup.

I think you need to rebase on main and force-push to get a clean diff.

[vneiger]

I cancelled the CI workflow because they were still in testing after almost 4 hours. Please review the code carefully to see what changes to existing functions could have led to this, thanks! (I pointed at some modifications in my comments, but there may be others)

[dlesnoff]

fmpz_randtest does not generate a coefficient with increased sparsity (here, 0 with increased probability) but generates a coefficient using a number of bits. For mod functions, it requires to be reduced after being generated. fmpz_randm generates directly a coefficient in the range [0, m) where m is a bound, but I am unsure if this function has some pseudo-uniformity guarantee (the algorithm is unspecified). So randtest has a slight different meaning for fmpz than for structures in mod n source files.

There is probably an infinite loop, I'll do a manual bisect.

[dlesnoff]

The tests halt indefinitely after gr_special_fac. ~I am unsure if it's related to my PR.~ This commit is the culprit: Add fmpz_mod_poly_rand, rand_monic, irred funcs

[dlesnoff]

Ok, I guess that if a polynomial has nonzero coefficients, it is irreducible with much less probability. This could slow down the tests. I should indeed give up on a "randfull-like" functionality for fmpz_mod_poly_randtest functions but then what would be the point of making another rand function?

[vneiger]

Ok, I guess that if a polynomial has nonzero coefficients, it is irreducible with much less probability. This could slow down the tests. I should indeed give up on a "randfull-like" functionality for fmpz_mod_poly_randtest functions

This is likely indeed. I haven't looked closely at the test files and the one that is failing, but let's suppose that some test includes working modulo 2, then the new randtest using randm_nonzero will only generate coefficients that are 1 ! I don't think randtest should ban 0.

but then what would be the point of making another rand function?

In my last batch of comments, you can see that I suggest using fmpz_randtest_mod instead of fmpz_randm_nonzero. Then the randtest and rand functions for fmpz_mod_poly would become rather different and I think it would make sense to have both. (However, one question that remains, is whether this change will suffice to solve the "infinite test" issue.)

[dlesnoff]

I changed randm_non_zero t to randtest calls. I gave one extra bit for the random generation before taking the modulus. If you think it is not necessary, I will remove it. ~I have still a few changes to perform.~