20120508, 12:44  #1 
May 2012
1110_{2} Posts 
Finding a smooth integer in a given residue class
In my current investigations I've faced with folowing problem:
I have random number 2^300 < r < 2^600 which I need represent in the form of product of rather small factors (each of them < 2^32) modulo M > 2^600. It sounds like smooth number in the residue ring of integers modulo M. Current idea of solving this problem is to solve next task: We have big numbers a and b, gcd(a,b) = 1 Find such x that z = a*x + b will be a ysmooth number y < 2^32, a > 2^300, b > 2^300 Is there any methods to solve this problem except exhaustive search? 
20120508, 12:51  #2 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
Edit: Coffee not found error. Nonsense deleted, of course they are equivalent.
Also, the problem seems to have a lot of simple solutions. Depending on M, you may well be able to express r as a power of 2 (mod M). Are there some further restrictions you haven't told us? Last fiddled with by akruppa on 20120508 at 13:19 
20120508, 16:06  #3  
Nov 2003
2^{2}×5×373 Posts 
Quote:
that is coprime to M is a UNIT. Thus, if z= ax + b is an element of the ring, to talk about z being "smooth" is nonsense, because z is divisible by every unit. Indeed, in Z/MZ there isn't even such as thing as unique factorization....... e.g. let M = (say) 24. a = 7, b = 11. Let x = (say) 5. Then ax + b = 22 mod M = 2*11, but it also equals 2 * 5 * 7 mod M because 7 = (11/5) mod 24. It also equals 2 * 5^2 * 11 mod M, etc. etc. 

20120508, 17:27  #4  
May 2012
E_{16} Posts 
Quote:
Sorry, I use more symbols than it needs. z = M*x + r. If I find such x that z is ysmooth, I can factorize z and it will be factorization of r modulo M with factors less than y. P.S. I've just set a=M, b=r in my first equtation Last fiddled with by Alexander on 20120508 at 17:57 

20120508, 17:33  #5  
May 2012
2×7 Posts 
Quote:


20120508, 17:57  #6  
Nov 2003
2^{2}·5·373 Posts 
Quote:
"random number 2^300 < r < 2^600 which I need represent in the form of product of rather small factors (each of them < 2^32) modulo M" It is clear from this statement that you are working mod M. Under the stated conditions the phrase "product of rather small factors modulo M" is nonsense. Even Alex suggested working with a power of 2 mod M!!!! You also say: "z = M*x + r. If I find such x that z is ysmooth, I can factorize z and it will be factorization of r modulo M with factors less than y. " i.e. "factorization of r modulo M". ===>> This is nonsense Furthermore, the phrase "factors less than y" is also nonsense because there is no proper ordering of elements working mod M. I suggest that you stop arguing and start listening. You need to reword your problem. 

20120508, 18:13  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Do you mean by "small factors" such elements of the ring that the smallest nonnegative integer representative is <2^32? Are elements with negative representative > 2^32 permissible, too?

20120508, 18:15  #8  
May 2012
2·7 Posts 
Quote:
Yes, I work with modular arithmetics. I need to express big number r as a product of small factors modulo M. "Small" here means that these factors I can fit in machine word. So I want to find such integer coefficients s1,s2,s3, ..., sn that r = 2^s1 * 3^s2 * 5^s3 * ... * y^sn mod M where y < 2^32. Is this sample clear enough? 

20120508, 18:25  #9 
May 2012
2×7 Posts 
I use unsigned integers so there can't be "elements with negative representative"

20120508, 18:25  #10  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Working modulo M means we're in the residue class ring Z/MZ where each element isn't just an integer, it is an infinite set of integers whose pairwise differences are multiples of M. There is no order defined on these residue classes, so we can't talk of "small" elements per se. We can slap on an artificial ordering, as I suggest in #7, but we have to agree on what that ordering is before we can look for something that is "small" according to that ordering.
Edit: Quote:
Last fiddled with by akruppa on 20120508 at 18:30 

20120508, 18:34  #11  
Nov 2003
2^{2}×5×373 Posts 
Quote:
You wrote: " I need to express big number r as a product of small factors modulo M" This CAN NOT BE DONE. There is no such thing as "smooth numbers" in a ring with finite characteristic. It is not a UFD. Indeed, the very concept of "factoring an integer" in such a domain is a nonsequitur. It is also impossible to talk about ordering of elements, even in a defined canonical way. This is because multiplication or addition of elements does not preserve the ordering. If A > x and B > x, it is quite often the case that A*B < x under any ordering that you try to impose! 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
parialgorithm for finding Gaussian integer bases  devarajkandadai  Software  0  20171005 04:54 
parialgorithm for finding Gaussian integer bases  devarajkandadai  Software  0  20170711 05:42 
Spinoff from "Smooth integer in ..."  literka  Miscellaneous Math  35  20120511 13:35 
Quad Sieve  Finding BSmooth Bound  blackbriar  Factoring  3  20111228 14:31 
Finding smooth numbers  Citrix  Math  9  20051231 11:07 