Re: Looking for a smaller solution...

[wraithx@morpheus.net]

On 2/2/2023 11:25 AM, Bill Allombert wrote:
> On Thu, Feb 02, 2023 at 12:10:44PM -0500, Max Alekseyev wrote:
> > This problem amounts to finding a closest vector to -E in the lattice
> > spanned by M.
> > It's called the closest vector problem (CVP):
> > https://en.wikipedia.org/wiki/Closest_vector_problem
> > and there exist specialized software such as fplll for solving it:
> > https://github.com/fplll/fplll
>
> Not if the exponents are required to be positive.
>
> Cheers,
> Bill.

Speaking of, thank you for the suggestions for finding all solutions with the 
extra option to matsolvemod.  And thank you for the suggestion of

A=matconcat([M,E;0,1]);U=qflll(A);A*U

I was finally able to run this on my full dataset (of 1248 primes) and A*U was a 
matrix of size 1249x1249, and it took about 25 minutes, and 42GB, to calculate. 
 There was only a single column that had a 1 in the last row (every other 
column had a 0 in the last row).  In that last column, 1068 entries were 0, 90 
were greater than 0, and 91 were less than 0.  The most negative number was 
-1365, the most positive was 1061.  I was hoping to get all non-negative values 
for the exponents.  Is there a way get all the entries to be >= 0?  Thanks again 
for any advice!

-David C.