FA+
Shop
Factoring Idea.
12 years ago
Years ago i can across the RSA factoring challenge( http://en.wikipedia.org/wiki/RSA_numbers ). RSA is a cryptography algorithm and a computer security company. The company put out a challenge to factor a 100 digit long number that was the result of multiplying 2 prime numbers back in 1991.
This operation is part of whats required to break their encryption. Basically when the size of their numbers versus the computational expense of factoring the numbers gets to low they start using longer numbers. I had an idea on how to factor these numbers what I believed to be significantly faster then brute force.
My idea was to reverse doing long hand multiplication. The idea was that the only numbers that effect the one digit in result is the ones digits in the two multiples.
EX: yy? * xx? = xxxxx9
If there where only prime numbers used to come up with the final number it leaves only two possible combinations for its factors ones place. Either 1 and 9 or 7 and 7. Either of those would take care of the ones place.
For the next place you would sweep through the combinations looking for another pair of numbers that would result in a number equal to the first two digits.
I finally sat down and made a program to try this out. It works but its slow. While it does rapidly eliminate large chunks of possible numbers. It doesn't work fast enough. I am thinking it may get a speed boost in working with base 16 versus base 10.
There are parts in how this was programmed that require string conversions. This is to check that the last digits of the result are "0". with working in base 16 this can be done with an AND statement. The down side is the number get larger then the storage types available.
It was worth looking into.
Edit:
Once nice thing with this setup though is it is extremely easy to distribute to other computers. Processing part of it requires no knowledge of any other previous attempts. Give it two possible ends of numbers and off it goes.
Edit2:
If i wrote this out as an actual paper would any one be interested in seeing it?
This operation is part of whats required to break their encryption. Basically when the size of their numbers versus the computational expense of factoring the numbers gets to low they start using longer numbers. I had an idea on how to factor these numbers what I believed to be significantly faster then brute force.
My idea was to reverse doing long hand multiplication. The idea was that the only numbers that effect the one digit in result is the ones digits in the two multiples.
EX: yy? * xx? = xxxxx9
If there where only prime numbers used to come up with the final number it leaves only two possible combinations for its factors ones place. Either 1 and 9 or 7 and 7. Either of those would take care of the ones place.
For the next place you would sweep through the combinations looking for another pair of numbers that would result in a number equal to the first two digits.
I finally sat down and made a program to try this out. It works but its slow. While it does rapidly eliminate large chunks of possible numbers. It doesn't work fast enough. I am thinking it may get a speed boost in working with base 16 versus base 10.
There are parts in how this was programmed that require string conversions. This is to check that the last digits of the result are "0". with working in base 16 this can be done with an AND statement. The down side is the number get larger then the storage types available.
It was worth looking into.
Edit:
Once nice thing with this setup though is it is extremely easy to distribute to other computers. Processing part of it requires no knowledge of any other previous attempts. Give it two possible ends of numbers and off it goes.
Edit2:
If i wrote this out as an actual paper would any one be interested in seeing it?
I'm sure the NSA has forced RSA to put backdoors into their encryption algorithms anyway. The NSA has to be able to decrypt anything they think might be a threat to national security, of course -- for example, conversations about how the NSA has far overstepped its authority and should be sharply disciplined and strictly regulated. Never mind that such backdoors weaken security and make the encryption more vulnerable to hackers. All you have to do is find the backdoors.