 mersenneforum.org > Math Finding a smooth integer in a given residue class
 Register FAQ Search Today's Posts Mark Forums Read  2012-05-08, 12:44 #1 Alexander   May 2012 11102 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 y-smooth number y < 2^32, a > 2^300, b > 2^300 Is there any methods to solve this problem except exhaustive search?   2012-05-08, 12:51 #2 akruppa   "Nancy" Aug 2002 Alexandria 1001101000112 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 2012-05-08 at 13:19   2012-05-08, 16:06   #3
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by akruppa 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?
The problem makes no sense. In the ring Z/MZ, every element
that is co-prime 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.   2012-05-08, 17:27   #4
Alexander

May 2012

E16 Posts Quote:
 Originally Posted by R.D. Silverman The problem makes no sense. In the ring Z/MZ, every element that is co-prime 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.
z is not an element of the ring.
Sorry, I use more symbols than it needs.
z = M*x + r. If I find such x that z is y-smooth, 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 2012-05-08 at 17:57   2012-05-08, 17:33   #5
Alexander

May 2012

2×7 Posts Quote:
 Originally Posted by akruppa 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?
r is really random number, I can't select it. Express r as a power of 2 (mod M) is suitable for me, but how to do it within a reasonable time?   2012-05-08, 17:57   #6
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by Alexander z is not an element of the ring. Sorry, I use more symbols than it needs. z = M*x + r. If I find such x that z is y-smooth, I can factorize z and it will be factorization of r modulo M with factors less than y.
r IS an element of the ring. I 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 y-smooth, 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.   2012-05-08, 18:13 #7 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts Do you mean by "small factors" such elements of the ring that the smallest non-negative integer representative is <2^32? Are elements with negative representative > -2^32 permissible, too?   2012-05-08, 18:15   #8
Alexander

May 2012

2·7 Posts Quote:
 Originally Posted by R.D. Silverman r IS an element of the ring. I 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 y-smooth, 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.
OK, let's try once again
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?   2012-05-08, 18:25   #9
Alexander

May 2012

2×7 Posts Quote:
 Originally Posted by akruppa Do you mean by "small factors" such elements of the ring that the smallest non-negative integer representative is <2^32? Are elements with negative representative > -2^32 permissible, too?
I use unsigned integers so there can't be "elements with negative representative"   2012-05-08, 18:25   #10
akruppa

"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 pair-wise 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:
 I use unsigned integers so there can't be "elements with negative representative"
What is the context for this problem?

Last fiddled with by akruppa on 2012-05-08 at 18:30   2012-05-08, 18:34   #11
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by Alexander OK, let's try once again 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?
You don't seem to get it. Stop arguing. I know what you asked for.

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
non-sequitur.

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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Software 0 2017-10-05 04:54 devarajkandadai Software 0 2017-07-11 05:42 literka Miscellaneous Math 35 2012-05-11 13:35 blackbriar Factoring 3 2011-12-28 14:31 Citrix Math 9 2005-12-31 11:07

All times are UTC. The time now is 00:17.

Sun May 16 00:17:45 UTC 2021 up 37 days, 18:58, 0 users, load averages: 1.98, 1.58, 1.50