mersenneforum.org Factoring Big Numbers In c#
 Register FAQ Search Today's Posts Mark Forums Read

 View Poll Results: Factoring can be completed using Windows YES 2 15.38% NO 1 7.69% Depends 2 15.38% The question as stated is meaningless 8 61.54% Voters: 13. You may not vote on this poll

 2008-03-20, 06:22 #1 ShridharRasal   2·17·73 Posts Factoring Big Numbers In c# We are working for Factoring Challenge of RSA .. We are using Grid Infrastructure with the help of Alchemi Middleware .. Alchemi Middleware uses C# Language .We have developed Class in c# which works for numbers less than 1024 bits.. We have to factorize n (of RSA) into p and q .. can anybody help me to start with project .. The class which we developed works for any number less than 1024 bits for any kind of simple arithmetic operations .. As we are using Grid Computing We need to create threads(Parallelize).. Which algorithm can i use for project .. Please give me links giving source codes of algorithms which works under windows platform ..
 2008-03-20, 09:41 #2 akruppa     "Nancy" Aug 2002 Alexandria 246710 Posts The fact that you talk only about modular arithmetic suggests that you are not familiar with the Number Field Sieve, NFS, where high-precision modular arithmetic plays a relatively minor role in the computation. Have you heard of NFS before? If not, I'd recommend "A Tale of Two Sieves" by Carl Pomerance as a very first introduction. Jason Papadopoulos (jasonp on this forum) has written a self-contained implementation (at http://www.boo.net/~jasonp/qs.html) but it's not ready for 1024 bit GNFS. In fact, no software anywhere is - 1024 bits can just barely be done with by SNFS these days (if you have acess to a large grid for several months), but is completely out of reach for GNFS. Alex
 2008-03-20, 15:34 #3 ewmayer ∂2ω=0     Sep 2002 República de California 2×32×653 Posts Wasn't Java the last programming language that was going to make all these integer factorizations trivial to perform? Guess Sun decided there just wasn't enough money in it - or maybe RSA Labs paid them some side money to not put them out of business. I mean, it *is* simply just an issue of being up on the latest "hipster language" being taught in Comp. Sci. courses, isn't it? "All these algorithmic problems go away if you just define the right class, overload a few operators, and deploy a functor in the right spot...and don't forget to keep your mutexes current..." In C++, I think one just needs to invoke the STL's built-in NFS utility like so: Code: string input_number = "[insert your number in decimal form here]"; bool nfs_special = [set true to use SNFS, otherwise default to GNFS]; string list_of_prime_factors = string.run_nfs(nfs_special); Or something like that.
2008-03-20, 15:52   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

29×229 Posts

Quote:
 Originally Posted by ewmayer Code: string input_number = "[insert your number in decimal form here]"; bool nfs_special = [set true to use SNFS, otherwise default to GNFS]; string list_of_prime_factors = string.run_nfs(nfs_special);
Why do you want to complicate the process. If the programmer has to make a decision then, of course, it will be the wrong choice. The code should know what to do.
Code:
string input_number = "[insert your number in decimal form here]";
string list_of_prime_factors = input_number.factors();

 2008-03-20, 16:01 #5 ewmayer ∂2ω=0     Sep 2002 República de California 2·32·653 Posts Even better - just overload the "" so that it triggers the snfs-or-gnfs preprocessing parser, and overload the assignment operator so the = ... initialization triggers the factorization. I'd code it and take all of the RSA prize money, but I'm too lazy. Last fiddled with by ewmayer on 2008-03-20 at 16:02
2008-03-20, 16:06   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

29×229 Posts

Quote:
 Originally Posted by ewmayer I'd code it and take all of the RSA prize money, but I'm too lazy.
What prize money? That was many moons ago that they had prize money.

2008-03-20, 16:07   #7
ewmayer
2ω=0

Sep 2002
República de California

2·32·653 Posts

Quote:
 Originally Posted by retina What prize money? That was many moons ago that they had prize money.
Guess it's a good thing I didn't invest a lot time writing the code then, isn't it?

2008-03-20, 16:17   #8
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

147618 Posts

Quote:
 Originally Posted by ewmayer Guess it's a good thing I didn't invest a lot time writing the code then, isn't it?
Do it for the glory, the recognition, the screaming teenage girls. Who needs money when you have all that?!

2008-03-20, 16:26   #9
jasonp
Tribal Bullet

Oct 2004

2·52·71 Posts

Quote:
 Originally Posted by ShridharRasal We are working for Factoring Challenge of RSA .. We are using Grid Infrastructure with the help of Alchemi Middleware .. Alchemi Middleware uses C# Language .We have developed Class in c# which works for numbers less than 1024 bits.. We have to factorize n (of RSA) into p and q .. can anybody help me to start with project .. The class which we developed works for any number less than 1024 bits for any kind of simple arithmetic operations .. As we are using Grid Computing We need to create threads(Parallelize).. Which algorithm can i use for project .. Please give me links giving source codes of algorithms which works under windows platform ..
People have been wanting to use grids to factor numbers for a long time. A google search yields this. Given that you seem to know more about C# than about factoring, you would probably have better luck implementing the quadratic sieve on your grid. Note that a large number library took me about a month to implement, but a complete number field sieve implementation took 2.5 years.

Last fiddled with by jasonp on 2008-03-20 at 16:30 Reason: change link to avoid registration and 404 from ibm.com

2008-03-20, 16:36   #10
ewmayer
2ω=0

Sep 2002
República de California

2·32·653 Posts

Quote:
 Originally Posted by retina Do it for the glory, the recognition, the screaming teenage girls. Who needs money when you have all that?!
The screaming teenage girls will burn a hole in your wallet - all that screaming burns a lot of calories.

BTW, is that crowd substantively different than the "teaming screen-age girls"? I used to chat online a lot with the latter until one of them turned out to be a hairy-knuckled middle-aged FBI agent ... but enough about my adventures in online dating...

2008-03-20, 17:17   #11
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

749610 Posts

Quote:
 Originally Posted by jasonp People have been wanting to use grids to factor numbers for a long time. A google search yields this. Given that you seem to know more about C# than about factoring, you would probably have better luck implementing the quadratic sieve on your grid. Note that a large number library took me about a month to implement, but a complete number field sieve implementation took 2.5 years.

The "RSA Factoring challenge"...................

..................was withdrawn some time ago. It no
longer exists.

 Similar Threads Thread Thread Starter Forum Replies Last Post arbooker Factoring 219 2022-10-28 13:48 paulunderwood Miscellaneous Math 18 2017-08-27 14:56 siegert81 Factoring 12 2011-02-03 13:55 jasong Factoring 27 2006-03-21 02:47 Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 23:23.

Fri Dec 2 23:23:03 UTC 2022 up 106 days, 20:51, 0 users, load averages: 0.78, 0.85, 0.88