h a l f b a k e r yLike gliding backwards through porridge.
add, search, annotate, link, view, overview, recent, by name, best, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
Whenever I'd like to waste my time and get involved in something needlessly complex while dreaming of big money, nothing beats the RSA challenges.
To use this recipe, all you'll need is a simple programming language - Java, Javascript or C# will do. First of all, write yourself a large number class
capable of multiplying 2 extremely large numbers together. Next choose your RSA prize, but for the purposes of this demonstration we'll go with "1242745657".
Now for the schoolboy maths. To multiply a number you multiply each digit by the other digits thus -
53 * 49 =
3 * 9 + 3 * 40 + 50 * 9 + 50 * 40 =
27 + 120 + 450 + 2000 = 2597
Note the zero's in the last line. Only the first bit gives you the '7'. So we now know that any number ending in 3 multiplied by any number ending in 9 gives us a product ending in 7. Of course, ----1 * ----7 also gives a product ending in 7, but in general this reduces the numbers to look through by the square root of the digit size. Once you have your digit candidate for the least significant digit, repeat the process with the next significant digit multiplying the numbers out to get a match etc.
So if your RSA prize is ~2^512, you're old search space of 2^256 is now 2^128 !
End of the Challenge
http://www.rsa.com/...bs/node.asp?id=2094
Sorry, waste all the time you want, but it won't win a prize (well, maybe the Fields Medal, if you're young enough). [Vernon, Jan 15 2009]
[link]
|
| |
Why couldn't you have been my math teacher!? |
|
| |
I just read a math thing that made me think |
|
| |
The journal article said that minkowskian space time could be represented with cartesian coordinates plus time was: Big CHI = x,y,z,t |
|
| |
Big CHI "interval" derivatve = dx^2 +dy^2 +dz^2 - dt^2 |
|
| |
the minus is the wrong part My reading of a popular book with a relativity description notes that two relativistic areas of reference are equivalenced with trigonometry thus Id think the articles math would read |
|
| |
Big CHI "interval" = dx^2 +dy^2 +dz^2 Trigonometry function with operator like Cosh(variable) - dt^2 |
|
| |
as an integer subtractable from physical spatiality like y-t lacks the numeric depth |
|
| |
Im super ignorant about these things but subtracting time from one spactial dimension when two or three are required to do relativistic equivalence seemed wrong |
|
| |
I'm guessing the time bit was intended to be imaginary i.e. the weird part of a complex number. What's it got to do with the idea ? |
|
| |
[beanangel] minkowskian(sic) space has a signature (-,+,+,+). It is quite possible that the author/s placed the negative at the end for aesthetic porpoises. Not really anything to do with complex numbers. |
|
| |
[bigsleep] //Once you have your digit candidate for the least significant digit, repeat the process with the next significant digit multiplying the numbers out to get a match etc.// This is not a new way of multiplication, nor does it reduce the factoring problem below its current complexity. Which is a weird thing to say seeing as we don't formally know the complexity category for factoring. But your method can be generalised thusly: |
|
| |
Assume p and q are of the same order of magnitude (i). i.e. the representation of p and q are of the same magnitude in whatever base. |
|
| |
Then the representatation of pq will be a sum of the products (p1,q1) + (p1,q2)+....(p1,qi) + (p2,q1) + .... (p2,qi) + ....(pi,qi). |
|
| |
It follows that the sum involves i^2 terms (products) to compute. After this computation we have, further, a set of |i| (cardinality i) to compute. This does not beat the GNFS. |
|
| |
Factoring numbers is basically a trivial exercise. It is the efficiencies that become important. Although trivial it has yet to be proved if factoring sits in P or NP, or even if we can decided that. You have to beat the most efficient to get noticed... |
|
| |
//This does not beat the GNFS// Way to crush a dream. It was much more fun when I didn't know what I was doing. |
|
| |
//P or NP// clearly equivalent, but for the visually minded NP is just a bit smoother. |
|
| |
////P or NP// clearly equivalent, but for the visually minded NP is just a bit smoother.// |
|
| |
Please submit your proof to the Clay Institute and collect a cheque for $1 million. |
|
| |
[bigsleep], I found out a couple years ago that it is somewhat less messy to do this in Base Two, instead of Base Ten. But not any faster, overall, alas (more digits to handle), even if you might be able to work from both ends of the number-to-factor, towards the middle, and not just from the low end. |
|
| |
BTW, the RSA Challenge prizes are no longer being offered. Alas, I spent about 3 years of my spare time on that problem.... |
|
| |
[Vernon] as I pointed out in my previous anno, any base would apply. |
|
| |
RSA no longer offer monetary prizes, however they are still interested in methods of factoring ( i refuse to use factorisation or factorization). There is a link on the RSA site. |
|
| |
Also there is the oppurtunity of a polynomial algorithm providing a case for P v NP. Although we don't know which class factoring sits in we do know if it is P then P = NP. |
|
| |
Also, If you could factor large primes at will, you could perpetrate the perfect fraud. Hacking codes for transactions, whilst the large body of expert testimony will concur that it is not possible. RSA prizes would have been small change... |
|
| |
Also, it is funny that everyone concentrated on the PKI part (presumably because of the money) and not so much on the LFSR, or the hashing (where there was a calculable weakness). Now both LFSR, and, at least MD5, are laid bare... |
|
| |
Well we have the SHA family, but what happens when they crack? There is no point in having a secure key, if you don't have a significantly secure hashing (block cyphering) algorithm, or is there? |
|
| |
//Please submit your proof // I was joking, in the same respect that I am fully aware this idea is totally amateurish. |
|
| |
//it is somewhat less messy to do this in Base Two, instead of Base Ten.// |
|
| |
I tried base 30030 (2x3x5x7x11x13) to discount 9 out of 10 candidates for the lower end (2^4 saved). Now I'm wondering whether the zero crossing analysis combined with this approach could bear fruit. |
|
| |
//I was joking, in the same respect that I am fully aware this idea is totally amateurish.// |
|
| |
Of course you were. Your annotations on other posts show this. Hopefully I was being equally jovial. |
|
| |
Well as regards maths you seem to know what you're talking about. Do you think that its possible for a complete amateur to stumble upon a fast factoring solution that beats GNFS ? |
|
| |
Where's your proof ? Surely P = PM' is not an empty set (where M' stands for 'not a mathematician'). |
|
| |
No, but it is possible to crash into a method that will eventually result in a possible use as a factoring algorithm. |
|
| |
Unlike "less rigorous" disciplines, mathematics seldom succumbs to the whims of amateur propectors. |
|
| |
Having said that there have been numerous prodigies (e.g S Ramanujan), with no formal background, that have contributed immense amounts that are still being explored today. |
|
| |
There are even the cases of some afflicted savants (I don't like the term idiot savants), who have been able to describe *how* they do their calculations. This led to the discovery of prime "binary trees", (and the associated "correlation co-efficients") which you will have, or will see, in so-called recommendation engines. Basically people with a functional IQ of less than average have shown how you can make two distinct numbers correlate. |
|
| |
//Basically people with a functional IQ of less than average have shown// |
|
| |
I alluded to this in the midst of a recent and very long ranty idea discussion. Savants 'see' numbers basically through a process of immersion in the mathematical domain. The fact that their explanations are ignorant of many theories and notations is an easily solveable problem. Thus the domain of maths is one example area of human knowledge where truth exists without exemplars. Or more to the point, mathematics and savants see the same things but in different languages. |
|
| |
And for the rest of us; Don't look at the finger, or you will miss all the heavenly glory! |
|
| |
You carry on [bigsleep] and so will I, maybe, just maybe, we can contribute. It might not be number theory, but it's sure rock and roll to me! |
|
| |
//Don't look at the finger, or you will miss all the heavenly glory!// |
|
| |
Well its a good way of justifying ignorance until god gives you the finger. I think I might have experienced that, we are not on the best of terms now. |
|
| |