 mersenneforum.org How to find a number with factors only from a set of primes?
 Register FAQ Search Today's Posts Mark Forums Read  2021-06-25, 20:24 #1 WraithX   Mar 2006 2×35 Posts How to find a number with factors only from a set of primes? 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?   2021-06-25, 20:43   #2
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

10110000102 Posts Quote:
 Originally Posted by WraithX 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?
That translates to finding B congruent to 83261 (mod 97929), with its factors being strictly from the set P.

If the modulus x is a prime, you can simply find a specific N for any of the primes in set P, name it p, for which pN is congruent to y (mod x). AFAIK, there should always be one in case x is prime.

When x is not prime, e.g. 97929, it may or may not work the same. Often you'll need to check for combinations of powers of primes in the set. There are cases when there are no such Bs. If you're given x=97929, y= 83261, P = , there are none, because there is no power of 1171 which satisfies the modular relation.   2021-06-25, 23:19   #3
charybdis

Apr 2020

547 Posts What's really being asked here is whether y is in the subgroup of the multiplicative group of Z/xZ generated by the set P - and, if so, how to find an expression for y as a product of elements of P.

Quote:
 Originally Posted by Viliam Furik If the modulus x is a prime, you can simply find a specific N for any of the primes in set P, name it p, for which pN is congruent to y (mod x). AFAIK, there should always be one in case x is prime.
Not necessarily, you need p to be a primitive root mod x. But you're right that it's easier when the modulus is prime, or indeed a prime power: find a primitive root mod x (znprimroot in PARI/GP), calculate the discrete logs of y and each prime in P wrt the primitive root (znlog in PARI), and see if you can make log(y) as a linear combination of the log(p). The answer will be yes unless the log(p) all share some factor with phi(x) that log(y) doesn't.

When the modulus is composite you'll need to do a calculation like this modulo each of the prime powers dividing x and put the solutions together using the Chinese Remainder Theorem to get a solution mod x. This will take some care, as you'll get conditions modulo phi(q^r) for each q^r dividing x, and the phi(q^r) will not necessarily be coprime to each other. At this point you could break the phi(q^r) up into *their* prime power divisors, group the conditions for each prime together, find solutions if they exist [this may involve solving a system of equations modulo several different powers of the same prime], and then safely apply CRT. In other words, it can be done. But there may be a better way :)

Or you could just brute force it by iterating over products of powers of the primes in your set, and with numbers this small you'll find a solution quickly if there is one...
Code:
gp > Mod(1171^2 * 1429^3 * 1811^4 * 2339, 97929)
%1 = Mod(83261, 97929)
There are 217 solutions with all 4 exponents at most 50. (notice this is approximately 50^4 * 2/phi(97929), suggesting that the 4 primes here generate a subgroup of (Z/97929Z)* of index 2, which is indeed the case)

Last fiddled with by charybdis on 2021-06-25 at 23:26   2021-06-26, 02:03 #4 axn   Jun 2003 7×743 Posts Code: chinese( chinese( chinese( chinese( Mod(83261, 97929), Mod(0, 1171) ), Mod(0,1429) ), Mod(0, 1811) ), Mod(0,2339) ) Does this not work? EDIT:- Never mind. Missed the "only" part" Last fiddled with by axn on 2021-06-26 at 02:04   2021-06-26, 02:54 #5 a1call   "Rashid Naimi" Oct 2015 Remote to Here/There 1000011111102 Posts Let's assume the P has 2 primes p & q. Then B would have to have the form p^m*q^n. It would be faster (for a general case) to brute-force over powers of p & q and subtract y and see if it is divisible by x. I think if brute-forcing over k yields faster results then those are the exceptions rather than the rule Since powers grow much faster than cycling through k constants would (eventually). Just my 2 cents. Last fiddled with by a1call on 2021-06-26 at 03:00   2021-06-26, 12:22   #6
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2×353 Posts Quote:
 Originally Posted by a1call Let's assume the P has 2 primes p & q. Then B would have to have the form p^m*q^n. It would be faster (for a general case) to brute-force over powers of p & q and subtract y and see if it is divisible by x. I think if brute-forcing over k yields faster results then those are the exceptions rather than the rule Since powers grow much faster than cycling through k constants would (eventually). Just my 2 cents. Or, as I mentioned, you could do the powers modulo x and look for a residue y.   2021-06-26, 12:55 #7 Dr Sardonicus   Feb 2017 Nowhere 22·5·257 Posts Oof. Tough problem! I assume that gcd(y,x) = 1 and that none of the primes in P divide x. The simplest possible case is if x = q, a prime number, y is not divisible by q, and P = {p}, p a prime number different from q. Then, there is a solution if the multiplicative order of y (mod q) divides the multiplicative order of p (mod q), but not otherwise. Even in this simplest case, actually finding a solution appears to be, uh, non-trivial. Here is one method. (Again, here x = q, a prime number). Let g = Mod(a, q) be a primitive root mod q, and assume that znorder(Mod(p,q))/znorder(Mod(y,q)) is an integer. Then p^e == y (mod q) where e = znlog(y,g)/znlog(p,g); e is defined modulo znorder(Mod(p,q)). In general, (Z/xZ)* is not a cyclic group. There are however "standard" ways of expressing it as a direct product of cyclic groups. Pari-GP's znstar() function does this, and also gives a set of generators for the direct factors. My old version of Pari-GP does not have a function to solve the discrete log problem when the multiplicative group is not cyclic, but it does have such a function - ideallog() - for the corresponding problem in number fields. I suppose you could reformulate the rationals as a number field using a degree-1 polynomial like T - 1 to gain the use of this function. With solutions of the discrete log problem for Mod(y,x) and Mod(p,x) for all the p in P, you can at least formulate things as a system of linear equations in the exponents for the p's, albeit to different moduli. In the general case I don't see a simple criterion for Mod(y,x) to be in the group generated by the Mod(p,x).   2021-06-27, 20:18   #8
WraithX

Mar 2006

2·35 Posts Quote:
 There are cases when there are no such Bs. If you're given x=97929, y= 83261, P = , there are none, because there is no power of 1171 which satisfies the modular relation.
Is there a way to test if a particular prime, p_i, from P could never be part of a solution? Either alone or in a group?
Like, test whether p_i^e_i == y (mod x) ever/never has a solution, or if p_i^e_i * p_j^e_j == y (mod x) ever/never has a solution?

My numbers x and y have a few hundred digits, and my set P has over 1000 primes. I think I'll try grabbing, say, 20 primes at a time, and multiplying powers of those together to see if they ever == y mod x.

Code:
chinese( chinese( chinese( chinese( Mod(83261, 97929), Mod(0, 1171) ), Mod(0,1429) ), Mod(0, 1811) ), Mod(0,2339) )
Thanks axn for the thought! I had thought of that too, but couldn't think of way to avoid unwanted factors.

Quote:
 When the modulus is composite you'll need to do a calculation like this modulo each of the prime powers dividing x and put the solutions together using the Chinese Remainder Theorem to get a solution mod x. This will take some care, as you'll get conditions modulo phi(q^r) for each q^r dividing x, and the phi(q^r) will not necessarily be coprime to each other. At this point you could break the phi(q^r) up into *their* prime power divisors, group the conditions for each prime together, find solutions if they exist [this may involve solving a system of equations modulo several different powers of the same prime], and then safely apply CRT. In other words, it can be done.
charybdis, I'd be very interested if you had a full algorithm [a pari/gp program would be even better! ;) ] that could do what you mention above. Since my set of primes is so large, I'm not sure how hard it will be to search for a set of them that multiply together to == y mod x.   2021-06-27, 21:04   #9
charybdis

Apr 2020

547 Posts Quote:
 Originally Posted by WraithX My numbers x and y have a few hundred digits, and my set P has over 1000 primes. I think I'll try grabbing, say, 20 primes at a time, and multiplying powers of those together to see if they ever == y mod x.
Ah, this completely changes the nature of the problem. Brute force has no chance of working when x and y are this large. If x is prime, then even if we are told that for a given p there exists e such that p^e == y mod x, actually finding such an e is totally out of reach in general (the current record is for a 240-digit prime, using CADO-NFS, which was 3 times as difficult as 240-digit GNFS factorization).

Do you know the factorization of x?

Last fiddled with by charybdis on 2021-06-27 at 21:16   2021-06-27, 21:50   #10
WraithX

Mar 2006

2·35 Posts Quote:
 Originally Posted by charybdis Do you know the factorization of x?
Yes, 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.   2021-06-28, 00:51   #11
charybdis

Apr 2020

547 Posts Quote:
 Originally Posted by WraithX Yes, 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.
This is doable as the prime factors are all small. I thought this might be hard to program but it turns out PARI has some helpful functions:
Code:
WraithX(x,y,P)={G=znstar(x,1);matsolvemod(matconcat(vector(#P,i,znlog(P[i],G))),G.cyc~,znlog(y,G))}
outputs a vector giving the exponents that each of the primes in P need to be raised to in the product. Unfortunately this isn't going to find a small solution: if x has hundreds of digits then the exponents you get will likely have hundreds of digits too. With some clever programming you might be able to adapt this to find somewhat smaller exponents, but you're not going to get anywhere near the smallest solution. If you want a value of k small enough to compute and store explicitly, then you're probably out of luck unless someone can come up with a much better method.

Last fiddled with by charybdis on 2021-06-28 at 00:58 Reason: clarify   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Miszka PrimeNet 2 2021-04-24 08:36 Mr. P-1 FactorDB 6 2013-03-22 02:30 mahnouman Information & Answers 19 2013-02-22 06:11 nibble4bits Puzzles 18 2006-01-07 10:40 edorajh PrimeNet 3 2004-10-01 19:16

All times are UTC. The time now is 23:04.

Mon Dec 6 23:04:26 UTC 2021 up 136 days, 17:33, 1 user, load averages: 1.07, 1.44, 1.57