Max Alekseyev on Thu, 02 Feb 2023 18:12:29 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Looking for a smaller solution...

This problem amounts to finding a closest vector to -E in the lattice spanned by M. 
It's called the closest vector problem (CVP):
and there exist specialized software such as fplll for solving it:


On Wed, Jan 25, 2023 at 5:14 AM Bill Allombert <> wrote:
On Tue, Jan 24, 2023 at 09:01:24PM -0600, wrote:
> Hello,
> While I was working on a problem, someone offered a Pari/GP solution.  While
> it works great, the solution is larger than I'd like.  I was wondering if
> there was an alternate way to compute the solution that results in a smaller
> answer?
> Here is a simplified version of the problem I'm working on:
> --------------------------------------------------------------------------
> Does anyone know of a way to find, or construct, a number B = k*x + y with x
> and y given, that is only divisible by primes from a finite set of primes P?
> For example, if x=97929 and y=83261 and P = [1171, 1429, 1811, 2339], how
> would we find or construct B? Or, perhaps show that one doesn't exist?
> I know we could do a brute force search, looping over k values and checking
> the factors of B, but I'm hoping someone might know of a way to construct,
> or constructively find, B. Is this possible?
> --------------------------------------------------------------------------
> In the full problem I'm working on, my numbers x and y have a few hundred
> digits, and my set P has over 1000 primes.  Also, x has only small prime
> factors p^e, with p a prime < 1000 and where e is usually 1, but can be
> higher, like 2^13, or 3^8, 7^5, etc. Also, all p are less than the smallest
> prime in P, ie no prime is in both sets.
> The code that was offered is:
> b(x,y,P)={G=znstar(x,1);matsolvemod(matconcat(vector(#P,i,znlog(P[i],G))),G.cyc~,znlog(y,G))}
> which "outputs a vector giving the exponents that each of the primes in P
> need to be raised to in the product."  ie B = product(P[i]^e[i]) where e[i]
> is the output of the above function.

There is an option to matsolvemod to give all solutions:

? [E,M]=b(97929,83261,[1171, 1429, 1811, 2339])
%5 = [[843,1311,325,330]~,[270,204,204,23;0,18,12,6;0,0,6,3;0,0,0,1]]

All the solutions can be written as E+M*v where v is a column vector with integral entries.

So you can try to pick v to get smaller entries, for example take v=[0,0,0,-36]~
? E+M*[0,0,0,-36]~
%13 = [15,1095,217,294]~