wraithx on Thu, 02 Feb 2023 20:23:58 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Looking for a smaller solution... |
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/fplllNot 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*UI 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.