# Can a very efficient RSA factoring algorithm be worth money?

If someone had a very efficient RSA factoring algorithm, would a company or government entity be willing to purchase it? What factoring time would be considered fast, months, days, hours, minutes? After they factor it, what do they do with the 2 primes numbers?

Yes, almost any improvement on state of the art factoring is monitizeable.

Small improvements will probably not be worth a lot of money. But an algorithm which can factor commonly used 2048 bit keys practically would be worth a ton of money. Even if it takes a month using 1 million dollars worth of hardware there will still be those interested in paying.

If the solution is faster and scaleable it is even more valuable. The better solutions are so valuable you need to be careful about your security and keeping it safe while trying to sell. Selling quickly to your country is a safe option. An open bidding war may not be safe.

A working implementation and breaking a public challenge will easily prove credability.

Many would argue the moral thing to do is to publicly publish a broken challenge and let the world know RSA is broken. claiming fame in the process.

• Historically, the Enigma code could usually be cracked within 24 hours, and it had the bonus that cracking the daily code allowed you to decipher all messages sent on that day, not just one. One problem today is that for example there might be 1000 messages be sent every day from A to B, each with its own RSA code, and if you know that one of these 1000 is very valuable but not which one then suddenly the cost is 1000 times higher. Commented Jan 9 at 18:17
• If you break a single message you will want it to be cheap, but there are plenty of RSA keys used for signing, if you could factor those, it could be very significant. Commented Jan 11 at 8:18
• Didn’t think about that. Yes, if I sign one completely irrelevant message with my private key, give you the public key so you can check it, and then you crack my private key then you can send any number of messages that look as if they were signed by me. A clever attacker could create a lot of damage. Commented Jan 11 at 19:44

2. "What do they do with the two prime numbers?": In a typical case, if the primes $$p,q$$ came from an RSA modulus $$N=pq,$$ which is in use as a certificate in a PKI, then that means the attacker can compute the private key, and efficiently impersonate the legitimate entity posessing that RSA certificate. They can sign documents pretending to be the legitimate entity, or break into communications which are performed using that certificate as an authentication mechanism.
• Nothing significant (up to 32 digits) because I'm designing a new algorithm not based on root finding or sieves. Mine is a modified genetic algorithm containing a cost function that allows me to know which direction I'm moving on the real number line. No integers here until I hit the solution. It has the capability to know when it's getting closer or farther away from $P$. The size of $N$ dictates various parameters so it's scalable, as I want the Big-O runtime complexity to be flat and independent of the size of $N$. I want it to run on a single desktop Workstation PC. Commented Jan 9 at 5:17