20210625, 20:24  #1 
Mar 2006
5·101 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? 
20210625, 20:43  #2  
"Viliam Furík"
Jul 2018
Martin, Slovakia
2×373 Posts 
Quote:
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 p^{N} 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 = [1171], there are none, because there is no power of 1171 which satisfies the modular relation. 

20210625, 23:19  #3  
Apr 2020
3×199 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:
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) Last fiddled with by charybdis on 20210625 at 23:26 

20210626, 02:03  #4 
Jun 2003
5^{2}×211 Posts 
Code:
chinese( chinese( chinese( chinese( Mod(83261, 97929), Mod(0, 1171) ), Mod(0,1429) ), Mod(0, 1811) ), Mod(0,2339) ) EDIT: Never mind. Missed the "only" part" Last fiddled with by axn on 20210626 at 02:04 
20210626, 02:54  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
100010011111_{2} 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 bruteforce over powers of p & q and subtract y and see if it is divisible by x. I think if bruteforcing 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 20210626 at 03:00 
20210626, 12:22  #6  
"Viliam Furík"
Jul 2018
Martin, Slovakia
2·373 Posts 
Quote:


20210626, 12:55  #7 
Feb 2017
Nowhere
12376_{8} 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, nontrivial. 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. PariGP's znstar() function does this, and also gives a set of generators for the direct factors. My old version of PariGP 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 degree1 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). 
20210627, 20:18  #8  
Mar 2006
5×101 Posts 
Quote:
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) ) Quote:


20210627, 21:04  #9  
Apr 2020
1125_{8} Posts 
Quote:
Do you know the factorization of x? Last fiddled with by charybdis on 20210627 at 21:16 

20210627, 21:50  #10 
Mar 2006
5×101 Posts 

20210628, 00:51  #11  
Apr 2020
3·199 Posts 
Quote:
Code:
WraithX(x,y,P)={G=znstar(x,1);matsolvemod(matconcat(vector(#P,i,znlog(P[i],G))),G.cyc~,znlog(y,G))} Last fiddled with by charybdis on 20210628 at 00:58 Reason: clarify 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to use PP1 method to find factors?  Miszka  PrimeNet  2  20210424 08:36 
Fails to find very small factors.  Mr. P1  FactorDB  6  20130322 02:30 
Best Way to find large factors  mahnouman  Information & Answers  19  20130222 06:11 
What way would you find numbers with a set number of factors?  nibble4bits  Puzzles  18  20060107 10:40 
How to find factors I found with TF?  edorajh  PrimeNet  3  20041001 19:16 