mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-05-08, 12:44   #1
Alexander
 
May 2012

11102 Posts
Question 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?
Alexander is offline   Reply With Quote
Old 2012-05-08, 12:51   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2012-05-08, 16:06   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-05-08, 17:27   #4
Alexander
 
May 2012

E16 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
Alexander is offline   Reply With Quote
Old 2012-05-08, 17:33   #5
Alexander
 
May 2012

2×7 Posts
Default

Quote:
Originally Posted by akruppa View Post
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?
Alexander is offline   Reply With Quote
Old 2012-05-08, 17:57   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Alexander View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-05-08, 18:13   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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?
akruppa is offline   Reply With Quote
Old 2012-05-08, 18:15   #8
Alexander
 
May 2012

2·7 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
Alexander is offline   Reply With Quote
Old 2012-05-08, 18:25   #9
Alexander
 
May 2012

2×7 Posts
Default

Quote:
Originally Posted by akruppa View Post
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"
Alexander is offline   Reply With Quote
Old 2012-05-08, 18:25   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2012-05-08, 18:34   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Alexander View Post
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!
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
pari-algorithm for finding Gaussian integer bases devarajkandadai Software 0 2017-10-05 04:54
pari-algorithm for finding Gaussian integer bases devarajkandadai Software 0 2017-07-11 05:42
Spin-off from "Smooth integer in ..." literka Miscellaneous Math 35 2012-05-11 13:35
Quad Sieve - Finding B-Smooth Bound blackbriar Factoring 3 2011-12-28 14:31
Finding smooth numbers 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

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.