Thread: module 2^p - 1
View Single Post
Old 2020-08-05, 13:30   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
Hi,


I understand the iteration sequence of the Lucas-Lehmer test involves using
module (2^p-1) arithmetic. How do computers running these such a test cope with numbers with 20+ million digits?
You need a data structure to hold the numbers. The simplest would be a one dimensional array and a byte or two indicating the most significant bit of the number.

For multiplication you use Fast Fourier Transforms (FFT).

Some of the operations can be parallelized across available cores.

Then there is making things cache-friendly.

Last fiddled with by paulunderwood on 2020-08-05 at 13:54
paulunderwood is offline   Reply With Quote