Prime Numbers

What Hacker News says

1. kurlbergMar 2019
   I don't know how far you have gotten, but I think it is a good idea to start with FFT-based fast multiplication and read up on whatever unknowns you encounter. In particular I think some abstract algebra (e.g. Dummit-Foote) would be helpful.

   There are tons of good expositions on the FFT-way, e.g. check out

   "Prime Numbers - A Computational Perspective" by Crandall-Pomerance see ch. 9, Fast algorithms for large-integer arithmetic

   Show morethread
2. schoenDec 2020
   While I wasn't at EFF at the time the donation was made, I find it totally credible that the donor was an individual who wanted to highlight the Internet's ability to let people work together in new ways, and didn't have any hidden motive for encouraging this particular work. I believe primality testing was suggested as a topic for the prize by a panel of scientific advisors, who were mostly mathematicians.

   In that timeframe, the main technical advances that helped GIMPS get more efficient were being made by Richard E. Crandall (https://en.wikipedia.org/wiki/Richard_Crandall), who also wrote Prime Numbers: A Computational Perspective with Carl Pomerance (https://en.wikipedia.org/wiki/Carl_Pomerance). If these folks are trying to help governments keep a monopoly on expertise about number theory and the difficulty of the RSA problem, they seem to be doing a pretty bad job of it.

   Show morethread
3. jherikoNov 2016
   for really big numbers there are the generalisations of karatsuba and toom-cook for higher numbers of splits, and beyond that there are the FFT multiplication methods which i believe are the fastest general case methods for very large numbers.

   also the laddering scheme used for the 'exponentiation' can be in different forms, the left-to-right or right-to-left form or even a Montgomery ladder...

   i seemed to recall there is a 'fastest known' method for generating fibonacci or lucas numbers... but google is not helping me.

   pretty sure i had seen it in this book: https://www.amazon.co.uk/Prime-Numbers-Computational-Carl-Po... i'll have to check when i have access to it next. :)

   Show morethread