Lenstra's elliptic curve factorization method
HTML-код
- Опубликовано: 6 авг 2024
- "Lenstra's elliptic curve factorization method," given by Leo Lai on 27th January 2016 as a guest speaker in the Churchill Computer Science Talks Series (talks.cam.ac.uk/show/index/63165).
Leo's talk addresses something incredibly important to computer science: computational number theory. Computational number theory has deep links to cryptography and security, and one of the most fundamental problems is the factorization of huge numbers, the subject of this talk.
Abstract:
Integer factorization is an important problem in computational number theory with many applications in cryptography. Elliptic curves, on the other hands, are mathematical objects whose study predates the notion of computation by more than a century. In 1987, Lenstra described a new factoring algorithm using elliptic curves, which is still one of the fastest special purpose factorization algorithms invented so far. Conversely, the desire to rigorously analyze this algorithm has produced new results in number theory. This talk will describe his algorithm. No knowledge beyond basic number theory is required. 
Наука
Very helpful talk.
Ok, if the group order has a large prime factor, it does not work. But we can try many different curves simultaneously. But with other algorithms like the quadratic sieve we also have to be lucky to find smooth numbers. The difference is, that with ECM we have to find only one smooth number in the order of the square root of N and we don't need much memory for millions of primes and giant matrices. Clearly ECM is much better.
The Lenstra's elliptic curve factorization method allows to factor much larger numbers as you might think.
Hmmmmm - special numbers? Is not every number special? What I mean is. For every number N we can allways find some properties special to this number and may try to find factoring methods which uses these properties.
Ir's so simple, just multiply a point on the curve by numbers like 2, 3, 4, 5, 6 ... . That's it. If you divide by zero (modulo p) the RSA-module is factored.
It seems to easy, but it's true.
Only one smooth number is required and not much memory. The algorithm is obviously more efficient than the sieve methods.
There is something clearly wrong. It seems we are fooled. 2^{2^10} + 1 are more than 1000 bits. It proves, Lenstra's elliptic curve algorithm is really much faster than the sieve mehtods. The NFS is not the fastest known algorithm.
nice burp 18:20
All these methods are actually pretty crap, including the so-called best. I've been working on the integer factorization problem for the last ten years, since I was about 22 (I have a real job also), and I can tell you that if you study the problem seriously, and think long and hard searching out every single nuance and exploit every avenue of opportunity to crack the problem; then it is very possible to produce what is called a polynomial-time solution. Intelligence isn't really the issue, what is needed is original and creative thinking, coupled with extremely dogged persistence and stubbornness. You don't need to know logarithms, or anything other than three things: arithmetic, algebra and modular arithmetic. Then you exploit the structure that every integer possesses, and certain properties of the primes, plus incontrovertible facts around number properties for example squares, all relating back to a consistent and coherent structure of the integers and prime numbers. For example, to give you a taste, take the sum of two square numbers modulo 7. If you rule out the case that either number is 0 modulo 7, then that leaves you with three other options, from the set of integers 1,2, and 4 for each square number. Therefore when you add the result of the two squares together modulo 7, there is no combination in which addition of any pair of numbers from this can equal zero modulo 7. This creates a condition or criteria against which things can be tested, and things determined from this information. Conversely, the sum of the same, any two square numbers modulo 13 can in fact equal zero, even if we rule out both squares being zero, because for example 4 + 9 = 0 mod 13, among other combinations. These are extremely rudimentary examples, but you get the gist of it. I don't think I need to say this, but I'll say it anyway. At least the first two or possibly three years of my odyssey for a polynomial-time factoring algorithm were very futile. Finding a workable solution is as much about ruling out what won't work and familiarising yourself with the problem, as it is about finding what will work and developing and refining that, something which comes later. So unless you're prepared to put in the groundwork, which is probably equivalent to at least a 3-year undergraduate degree's worth of material, then forget it. I don't care how intelligent you think you are; if you aren't conscientious, diligent, passionate, stubborn, and probably obsessed over this problem (or equivalently any other deep mathematical problem worth solving also), then you're going nowhere. I'm not particularly intelligent; I'd say on a good day I might have an IQ of 120; but these other qualities I've just mentioned I have in abundance, possibly to the detriment of other things. If you've ever scratched your head over a crossword clue for example, and then had that 'aha' moment when looking up the answer, just multiply that by about a million or so, and you'll have some appreciation of how I feel and have felt scratching my head on thousands of occasions over the past decade, as I encountered and traversed many, many obstacles and roadblocks along the way. But once you reach the destination, then you forget all the travails, and remember each small win as hard-fought for, and just another stepping stone to success at the end of the journey; on it's own each step may not seem like much, but when you aggregate 100s of these steps, then the result is magnificent and magical. Sorry if this comes across as slightly pompous and dismissive of other's efforts; I'm not trying to denigrate anyone's work in any way or rubbish it, I'm just politely suggesting that the reason their efforts have failed so miserably, is simply because they lack both the curiosity and devotion in applying the scientific method repeatedly, day-in, day-out, consistently over a long period of time, in order to solve the problem satisfactorily. So if you are reading this, and thinking of attacking the integer factorisation problem; my sincere advice is don't. It may be possible you'll solve the problem in the same way I did, but like I said, you're probably looking at minimum 15,000 hours worth of effort, and I have much more confidence in your intelligence and intellectual capacity than I have my own; however, I have much more confidence in my own tenacity and resolve. If you don't believe me, that's fine. I just need to write up my method, which won't take long; I can guarantee you this, by 2020 there will be a published polynomial-time algorithm for factoring ANY integer (semi-prime composed of two large, random primes or otherwise) of up to 10,000 decimal digits in a matter of seconds and minutes. So if you are looking for a problem to solve, my advice would be, pick the Travelling Salesman Problem. As soon as I've written up my IFP work (or at least published verifiable results for ALL the RSA numbers at a minimum), then I'm going to be migrating onto the TSP problem. If I don't solve this second challenge before I'm 40, then I'll be very disappointed.
Is your method based on continued fractions? Because if we can solve Pell's equation x^2 - n*y^2 = 1 in polynomial time O(log(n)^k), which I think it must be possible, then for any given non-square n, gcd(x-1, n) and gcd(x+1, n) are factors of n. For this to work, we may need to fully understand the continued-fraction expansion of sqrt(n), which should allow us to jump in the expansion as far as we want, without computing the full expansion. Then, using an exponentiation by squaring algorithm, we may be able to compute a solution to Pell's equation in O(log(n)^k) steps.
Interesting comments! From what you've said you're pretty smart person to me.
I'm sorry. TL;DR. But how long will it take to factorise your comment - i hope it has a smooth factor. Btw, thanks go to the talk.
Any news on this?
Any news?