mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

Reply
 
Thread Tools
Old 2008-03-20, 06:22   #1
ShridharRasal
 

2·17·73 Posts
Smile 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 ..
  Reply With Quote
Old 2008-03-20, 09:41   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2008-03-20, 15:34   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×32×653 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2008-03-20, 15:52   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

29×229 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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();
retina is online now   Reply With Quote
Old 2008-03-20, 16:01   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·32·653 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2008-03-20, 16:06   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

29×229 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
retina is online now   Reply With Quote
Old 2008-03-20, 16:07   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·32·653 Posts
Default

Quote:
Originally Posted by retina View Post
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?
ewmayer is offline   Reply With Quote
Old 2008-03-20, 16:17   #8
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

147618 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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?!
retina is online now   Reply With Quote
Old 2008-03-20, 16:26   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·52·71 Posts
Default

Quote:
Originally Posted by ShridharRasal View Post
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
jasonp is offline   Reply With Quote
Old 2008-03-20, 16:36   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·32·653 Posts
Default

Quote:
Originally Posted by retina View Post
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...
ewmayer is offline   Reply With Quote
Old 2008-03-20, 17:17   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

749610 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
Let me add:

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


..................was withdrawn some time ago. It no
longer exists.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some code for factoring numbers up to 2^63 arbooker Factoring 219 2022-10-28 13:48
Factoring Mersenne numbers paulunderwood Miscellaneous Math 18 2017-08-27 14:56
Factoring Fermat numbers siegert81 Factoring 12 2011-02-03 13:55
Need help factoring Cunningham numbers jasong Factoring 27 2006-03-21 02:47
Factoring Fermat Numbers 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔