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 < [B]r[/B] < 2^600 which I need represent in the form of product of rather small factors (each of them < 2^32) modulo [B]M[/B] > 2^600.
It sounds like smooth number in the residue ring of integers modulo [B]M[/B].

Current idea of solving this problem is to solve next task:
We have big numbers [B]a[/B] and [B]b[/B], [B]gcd[/B]([B]a[/B],[B]b[/B]) = 1
Find such [B]x[/B] that [B]z[/B] = [B]a[/B]*[B]x[/B] + [B]b[/B] will be a [B]y[/B]-smooth number
[B]y[/B] < 2^32, [B]a[/B] > 2^300, [B]b[/B] > 2^300

Is there any methods to solve this problem except exhaustive search?

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?

[QUOTE=akruppa;298782]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?[/QUOTE]

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 [b]nonsense[/b], because z
is divisible by [i]every[/i] 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.

[QUOTE=R.D. Silverman;298797]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 [b]nonsense[/b], because z
is divisible by [i]every[/i] 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.[/QUOTE]

[B]z[/B] is not an element of the ring.
Sorry, I use more symbols than it needs.
[B]z[/B] = [B]M[/B]*[B]x[/B] + [B]r[/B]. If I find such [B]x[/B] that [B]z[/B] is [B]y[/B]-smooth, I can factorize [B]z[/B] and it will be factorization of [B]r[/B] modulo M with factors less than [B]y[/B].

P.S. I've just set a=M, b=r in my first equtation

[QUOTE=akruppa;298782]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?[/QUOTE]

[B]r[/B] 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?

[QUOTE=Alexander;298802][B]z[/B] is not an element of the ring.
Sorry, I use more symbols than it needs.
[B]z[/B] = [B]M[/B]*[B]x[/B] + [B]r[/B]. If I find such [B]x[/B] that [B]z[/B] is [B]y[/B]-smooth, I can factorize [B]z[/B] and it will be factorization of [B]r[/B] modulo M with factors less than [B]y[/B].[/QUOTE]

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 [b] mod M[/b]!!!!

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 [b]nonsense[/b]
Furthermore, the phrase "factors less than y" is [b]also[/b] 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.

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?

[QUOTE=R.D. Silverman;298806]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 [b] mod M[/b]!!!!

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 [b]nonsense[/b]
Furthermore, the phrase "factors less than y" is [b]also[/b] 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.[/QUOTE]

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?

[QUOTE=akruppa;298807]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?[/QUOTE]
I use unsigned integers so there can't be "elements with negative representative"

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 [I]per se[/I]. 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"
[/quote]

What is the context for this problem?

[QUOTE=Alexander;298808]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?[/QUOTE]

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 [b] CAN NOT BE DONE[/b]. 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!