RSA Factoring

antiroach · 2003-07-05, 02:35

Hey, why not try factoring RSA576. Its only 174 digits :). And theres a 10,000 prize.

trif · 2003-07-05, 03:32

Quote:

Originally Posted by antiroach

Hey, why not try factoring RSA576. Its only 174 digits :). And theres a 10,000 prize.

Yeah, but there's zero hope of finding any small factors to whittle it down and make it more digestible.

ColdFury · 2003-07-05, 04:59

Quote:

Yeah, but there's zero hope of finding any small factors to whittle it down and make it more digestible.

Perhaps, but correct me if I'm wrong, but haven't some of the co-factors we've worked on been larger than 174 digits?

antiroach · 2003-07-05, 05:08

exactly what im saying. the current number being factored is about 227 digits. it would be pretty cool to factor an RSA number :)

Wacky · 2003-07-05, 11:52

Sorry to "rain on the parade" but it isn't that easy.....

First you need to understand more about how the NFS method works.

We select two polynomials that are related to the number which we are attempting to factor.

The sieving phase examines the norm of these polynomials at very many points and collects the "smooth" ones. The simpler the polynomial, the higher the density of acceptable points.

We can split the numbers to be factored into two broad groups. First, there are the cofactors which come from "simple" polynomials. For example, the M713 can be expressed as N|(2^713-1) or N|(2^714-2). The latter expression can be re-expressed as (2^119)^6 -2.

Thus, we will use the polynomials X^6-2 and Y-2^119.

Note that the complexity is about 215 digits (2^714) even though we already know some of the factors and are trying to factor a number that is only 171 digits. This approach is known as Simple NFS. (SNFS)

Many numbers cannot be represented by such simple polynomials. For these, we search for a pair of polynomials. The resulting polynomials have large coefficients and therefore have a much lower density of acceptable points. This approach is called the General NFS (GNFS).

RSA576 was particularly chosen to be difficult. As you note, it is 174 digits. But since it requires the GNFS, it is as hard as perhaps a 260 digit SNFS number. (I may be off a bit. I'm sure Paul will correct me).

Now, the effort to sieve is exponential in the size. RSA576 is perhaps 50 times as difficult as M713. It might take our present pool a couple years to do the sieving.

There are additional problems. We are already pushing the limits of 32 bit numbers. The solution of RSA576 will likely require 64 bit machines or many more 32 bit machines to compensate for the lost efficiency in handling the larger numbers.

So, the bottom line is that we will not be doing RSA576 any time soon because it is much harder than the numbers that we can presently handle.

I'll also comment on the prize money. In my opinion, this is a disincentive. If we won such a prize, what would we do with it? Should we spread it according to effort? A dollar here and ten there would be both unworkable and insignificant. Perhaps we could give it to the largest contributor. Would $10k really mean much to MSFT? Or you could give it to me. :) But that is hardly fair. A charity perhaps... But which one?

It's much easier to divide up $0.00. We don't have to discuss it and generate hard feelings. Everyone gets their fair share.

ColdFury · 2003-07-05, 20:49

I've actually been studying the NFS for a while, but I never stopped to compute the speed difference between the special and general variant. I didn't realize the special had such a speed up.

This brings me to a question I've been thinking about for a while. Now, it's known that good polynomials can drastically cut-down on the effort spent sieving. Has anyone ever considered distributing the polynomial search phase as well? Different systems can generate different polynomials according to certain rules and give them a "test run" to try out their efficiency. The systems could send the results back to the central server, which would keep track of the most efficient polynomial currently found. It seems to me that a day or two of many computers searching for polynomials would uncover a better one than maybe one or two computers looking for a week.

Quote:

I'll also comment on the prize money. In my opinion, this is a disincentive. If we won such a prize, what would we do with it? Should we spread it according to effort? A dollar here and ten there would be both unworkable and insignificant. Perhaps we could give it to the largest contributor. Would $10k really mean much to MSFT? Or you could give it to me. But that is hardly fair. A charity perhaps... But which one?

I think if we ever did run into the situation, it would be wise to consider how some other projects handled it. You'd have to state clearly beforehand where the prize money would go. I'd suggest simply giving it all away to some charity, perhaps keeping a small amount to offset the costs of running the system. Or you could get more fancy like distributed.net did and implement a vote system. Each user can choose from a list of charities or other organizations. Every line sieved (or relation found) by that user constituets 1 "vote". When the money is obtained, you simply add up all the votes and the charity with the most votes gets the money.

Wacky · 2003-07-05, 21:36

Quote:

Originally Posted by ColdFury

I didn't realize the special had such a speed up.

Small coefficients and low degrees give much smoother norms.

Quote:

It's known that good polynomials can drastically cut-down on the effort spent sieving. Has anyone ever considered distributing the polynomial search phase as well? ... It seems to me that a day or two of many computers searching for polynomials would uncover a better one than maybe one or two computers looking for a week.

It has been considered. At least for us, since some of the principals have access to a reasonable number of machines, we have not felt that the computing resources were sufficiently limiting to warrant the extra management effort. That may change in the future.

Quote:

I'll also comment on the prize money. ... A charity perhaps

I'd suggest simply giving it all away to some charity ... the charity with the most votes gets the money.

But that requires an effort and no matter who "wins", those who supported an alternate will be less happy. Besides, I haven't seen any prizes offered that are really worth the effort.

trif · 2003-07-05, 22:59

Quote:

Originally Posted by Wackerbarth

I'll also comment on the prize money. In my opinion, this is a disincentive. If we won such a prize, what would we do with it? Should we spread it according to effort? A dollar here and ten there would be both unworkable and insignificant. Perhaps we could give it to the largest contributor. Would $10k really mean much to MSFT? Or you could give it to me. :) But that is hardly fair. A charity perhaps... But which one?

It's much easier to divide up $0.00. We don't have to discuss it and generate hard feelings. Everyone gets their fair share.

I agree that headaches over prize money oftentimes make it not worth it. But given that some problems have prize money attached to them, I'd like to suggest something I've been thinking about for quite awhile.

Everybody reinvents the wheel when a new DC project gets started. I'd like to see a repository of techniques and methods common to DC projects that could be drawn on by new DC projects. Perhaps a way of sponsoring the server needs of qualifying projects. There's lots of volunteer time floating around, but some resources have to be paid for, especially disk space and bandwidth.

I don't think that BOINC or Adam Beberg's V3, or even the DC framework that Scott is working on are going to be a one size fits all answer. That much became obvious to me when I was asked to see if distributed.net could help out with GIMPS. The distributed computing model they used (including V3) didn't account for long running WU that needed status updates without returning results. Nor did they account for the amount of participant freedom that GIMPS runs with. We don't know what kinds of needs future projects will have in terms of technical, political, and operational constraints, both on the client end and server end, so it makes more sense to build a toolbox than a framework.

There are also projects that founder only for lack of a server and bandwidth. Resources permitting, it would a good thing to be able to help defray costs for good projects in an organized way.

In this way, the prizes could be used to benefit distributed computing as a whole, rather than one particular project that happened to have prize money attached to it. And it removes the prize money as a source of contention.

This is rather a more Loungish topic, so if it goes any further, I'd suggest a new thread there.

Exluminis · 2003-07-13, 21:30

NFS? This is quite funny.
Be a number engineer and find something even further. A even smaller than exponential time series. That's the new age of the encryption factorization challenges.

ewmayer · 2003-07-22, 18:14

Quote:

Originally Posted by Wackerbarth

Many numbers cannot be represented by such simple polynomials. For these, we search for a pair of polynomials. The resulting polynomials have large coefficients and therefore have a much lower density of acceptable points. This approach is called the General NFS (GNFS).

A e-mail exchange Peter Montgomery and I had on this subject follows. I had some numbers I was interested in factoring which had resisted fairly deep ECM efforts, and was trying to learn more about the differences between the special and general NFS.

-----------------

[code:1]Another question about SNFS polynomials, which seems especially relevant to the case where the input number has no obvious special form, but is too large for GNFS. (Another example I have in mind is the case where we are factoring a number which *does* have a nice form for SNFS, but which in its raw form is too large for SNFS, and where we have a fairly deep partial factorization, which leaves a cofactor N of feasible size for SNFS but no longer of nice algebraic form, and also too large for GNFS.) Is it feasible to search numerically for some integer X which allows N to be expressed as a polynomial in X of convenient order for SNFS, and with decently small coefficients?

For instance, I notice that the C135 cofactor I want to factor (and there the full number is small enough for SNFS, but just by way of example),

N = 570262229321929824871858839122891676716126463565895757793607870653597282165957653592803888395593959868233879964970398426621091298635839

has a sixth root that is quite close to integral:

N^(1/6) = 28796901966283355693382.98849...

Now if I set r=28796901966283355693383, I have

N = r^6 - 1362344705796597183482725783805680802732323062427951798203963215024480705425407051176442282546965559515123838930 .

The zeroth-order coefficient is still fairly unwieldy, but it is significantly smaller than N, and of course I didn't search very hard. It seems for a given polynomial order O, as O increases there should be a large number of Oth-order polys which = N and have coefficients less than some desired bound, e.g. N^(1/O), of which we only need to find one. If I continue the above brute-force approach, I can write

N = r^6 - 1981088772476547848802*r^4 + 5990531477601275988384*r^3 + 11422764268863511805333*r^2 - 8401591645029116675071*r - 4118215695723934696540 .

But I'm fairly sure if it were that easy, it would've been done already. Is the problem that coefficients of the same order as N^(1/O) are still much too large for SNFS?

-Ernst[/code:1]

Quote:

You have re-discovered the base-m method for GNFS. With O = 6 and m = round(N^(1/O)) you get a monic degree-O polynomial with coefficients below m/2 in absolute value. A variation uses m ~= round(N^(1/7)), with all coefficients (except the first) bounded by m/2.

Use GNFS if over 1/3 of the SNFS number has already been factored by ECM or other means. [`Other means' can include algebraic factors -- if you are factoring b^35 - 1 for some integer b, then SNFS might use m = b^7 and f(x) = (x^5 - 1)/(x - 1). Here we know a factor (b^5 - 1)/(b - 1) of f(m). This algebraic factor accounts for 4/28 = 14% of f(m).]

Peter

hyh1048576 · 2003-07-28, 04:56

Quote:

Originally Posted by antiroach

Hey, why not try factoring RSA576. Its only 174 digits :). And theres a 10,000 prize.

But where can I find the number of RSA576? :? ;) ;) ;)

2003-07-05, 02:35	#1
antiroach Jun 2003 2²×61 Posts	RSA Factoring Hey, why not try factoring RSA576. Its only 174 digits :). And theres a 10,000 prize.

2003-07-05, 05:08	#4
antiroach Jun 2003 2²·61 Posts	exactly what im saying. the current number being factored is about 227 digits. it would be pretty cool to factor an RSA number :)

2003-07-05, 11:52	#5
Wacky Jun 2003 The Texas Hill Country 441₁₆ Posts	Sorry to "rain on the parade" but it isn't that easy..... First you need to understand more about how the NFS method works. We select two polynomials that are related to the number which we are attempting to factor. The sieving phase examines the norm of these polynomials at very many points and collects the "smooth" ones. The simpler the polynomial, the higher the density of acceptable points. We can split the numbers to be factored into two broad groups. First, there are the cofactors which come from "simple" polynomials. For example, the M713 can be expressed as N\|(2^713-1) or N\|(2^714-2). The latter expression can be re-expressed as (2^119)^6 -2. Thus, we will use the polynomials X^6-2 and Y-2^119. Note that the complexity is about 215 digits (2^714) even though we already know some of the factors and are trying to factor a number that is only 171 digits. This approach is known as Simple NFS. (SNFS) Many numbers cannot be represented by such simple polynomials. For these, we search for a pair of polynomials. The resulting polynomials have large coefficients and therefore have a much lower density of acceptable points. This approach is called the General NFS (GNFS). RSA576 was particularly chosen to be difficult. As you note, it is 174 digits. But since it requires the GNFS, it is as hard as perhaps a 260 digit SNFS number. (I may be off a bit. I'm sure Paul will correct me). Now, the effort to sieve is exponential in the size. RSA576 is perhaps 50 times as difficult as M713. It might take our present pool a couple years to do the sieving. There are additional problems. We are already pushing the limits of 32 bit numbers. The solution of RSA576 will likely require 64 bit machines or many more 32 bit machines to compensate for the lost efficiency in handling the larger numbers. So, the bottom line is that we will not be doing RSA576 any time soon because it is much harder than the numbers that we can presently handle. I'll also comment on the prize money. In my opinion, this is a disincentive. If we won such a prize, what would we do with it? Should we spread it according to effort? A dollar here and ten there would be both unworkable and insignificant. Perhaps we could give it to the largest contributor. Would $10k really mean much to MSFT? Or you could give it to me. :) But that is hardly fair. A charity perhaps... But which one? It's much easier to divide up $0.00. We don't have to discuss it and generate hard feelings. Everyone gets their fair share.

2003-07-13, 21:30	#9
Exluminis Mar 2003 3² Posts	NFS? This is quite funny. Be a number engineer and find something even further. A even smaller than exponential time series. That's the new age of the encryption factorization challenges.