Re: Looking for a smaller solution...

[Max Alekseyev <maxale@gmail.com>]

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

Regards,

Max

On Wed, Jan 25, 2023 at 5:14 AM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

On Tue, Jan 24, 2023 at 09:01:24PM -0600, wraithx@morpheus.net 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:
b(x,y,P)={G=znstar(x,1);matsolvemod(matconcat(vector(#P,i,znlog(P[i],G))),G.cyc~,znlog(y,G),1)}

? [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]~

Cheers,
Bill