mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-25, 20:24   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

2×35 Posts
Default 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?
WraithX is offline   Reply With Quote
Old 2021-06-25, 20:43   #2
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

10110000102 Posts
Default

Quote:
Originally Posted by WraithX View Post
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 = [1171], there are none, because there is no power of 1171 which satisfies the modular relation.
Viliam Furik is offline   Reply With Quote
Old 2021-06-25, 23:19   #3
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

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 View Post
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
charybdis is offline   Reply With Quote
Old 2021-06-26, 02:03   #4
axn
 
axn's Avatar
 
Jun 2003

7×743 Posts
Default

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
axn is offline   Reply With Quote
Old 2021-06-26, 02:54   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1000011111102 Posts
Default

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
a1call is offline   Reply With Quote
Old 2021-06-26, 12:22   #6
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2×353 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
Viliam Furik is offline   Reply With Quote
Old 2021-06-26, 12:55   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·5·257 Posts
Default

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).
Dr Sardonicus is online now   Reply With Quote
Old 2021-06-27, 20:18   #8
WraithX
 
WraithX's Avatar
 
Mar 2006

2·35 Posts
Default

Quote:
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.
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.
WraithX is offline   Reply With Quote
Old 2021-06-27, 21:04   #9
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

Quote:
Originally Posted by WraithX View Post
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
charybdis is offline   Reply With Quote
Old 2021-06-27, 21:50   #10
WraithX
 
WraithX's Avatar
 
Mar 2006

2·35 Posts
Default

Quote:
Originally Posted by charybdis View Post
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.
WraithX is offline   Reply With Quote
Old 2021-06-28, 00:51   #11
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

Quote:
Originally Posted by WraithX View Post
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
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to use PP1 method to find factors? Miszka PrimeNet 2 2021-04-24 08:36
Fails to find very small factors. Mr. P-1 FactorDB 6 2013-03-22 02:30
Best Way to find large factors mahnouman Information & Answers 19 2013-02-22 06:11
What way would you find numbers with a set number of factors? nibble4bits Puzzles 18 2006-01-07 10:40
How to find factors I found with TF? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.