Retrochallenge Update (was Re: How many use old browsers (e.g. =< Netscape 4 or IE 6) as their ONLY source of web content?)

[Jerome H. Fine]

 >Terry Stewart wrote:

>>On Fri, Jul 3, 2015 at 10:26 AM, Terry Stewart <terry at webweavers.co.nz>
>wrote:
>
>>Hi,
>>
>>I'm engaged in a Retrochallenge project where I'm recoding my
>>classic-computers.org.nz site to make it suitable for mobile platforms.
>>I want to modernise the code as well, making it as close to HTML5 standard
>>as I can
>>
>Since I did ask about this, some on this list might be interested in my
>progress with this project.
>
>The pages are still a long way from conforming to strict HTML5 standards
>but at least they are now all mobile-friendy.
>http://www.classic-computers.org.nz/blog/2015-06-29-recoding-classic-computers.org.nz.htm#latest
>
>Cheers
>
>Terry (Tez)
>
I would like to add the ability to check for Merseene Prime numbers to
PDP-11 systems.  The Lucas–Lehmer primality test at:
http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
provides an almost trivial algorithm to use.  When the values are small
(less than 65K or when the original prime is less than 15), the
calculation is able to use integers of just 4 bytes.

I have managed to produce multi-precision subroutines for the PDP-11
which handle unsigned integers up to 10^160 which supports the
calculation for integers up to 10^80.  Unfortunately, the largest
original prime which qualifies is 127, or not very large at all.

What I really need is to figure out the calculations needed to perform:
the Schönhage–Strassen algorithm:
https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
Does anyone have any hints how to actually turn the algorithm into
code?  When the values that must be squared are millions of 32-bit
values long (really not too big, just 4 MB after all), the classical method
to multiply 2 values which are each one million elements long takes
one trillion multiplications plus many additions.  The Schönhage–Strassen
algorithm should reduce that to about one billion multiplications.

Can anyone suggest where I can  find something that explains the
Schönhage–Strassen algorithm in a manner without all the FFT
jargon getting in the way?

Jerome Fine