Prime Numbers
A Computational Perspective
by Richard E. Crandall, Carl Pomerance, Richard Crandall · first published 2001
3mentions
1recommended by
3HN commenters
2016–2020first – last mentioned
33% recommend67% neutral
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
…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
on “Integer multiplication in time O(n log n) [pdf]” ↗…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. :)
on “Fast Fibonacci Algorithms (2015)” ↗…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…
on “All Mersenne prime exponents below 100m tested at least once” ↗