ECE Technical Seminar Report for Schonhage Stassen Algorithm Seminar Topic

Introduction to Schonhage Stassen Algorithm Seminar Topic:

This algorithm is used multiply the large integers quickly. The developers are Arnold Schönhage and Volker Stassen in 1971.This algorithm uses recursive Fast Fourier transforms in rings with 2²ⁿ + 1 element. There are several notations in this Big O notation. This algorithm was in use up to furers algorithm. But this algorithm achieves only astronomical large values. The method of schonhage-stassen is based on Crandall and Pomerance in their Prime Numbers.

Convolutions:

For example take numbers 123 and 456 and multiply with the base digit B without carry. The output is.

		1	2	3
	×	4	5	6
		6	12	18
	5	10	15
4	8	12
4	13	28	27	18

The sequence 4, 13, 28, 27, 18 is called linear convolution. They are original sequences of 1, 2, 3 and 4, 5, 6.

Convolution theorem:

The Stassen-schonhage algorithm depends on the convolution theorem. By the use of this algorithm two sequences can be easily calculated. Cyclic convolutions of two vectors are calculated by DFT discrete Fourier transform. Elements are multiplied vector by vector.

CyclicConvolution(X, Y) = IDFT (DFT(X) · DFT(Y)).

For the multiplication of algorithm and to invoke recursively if we use DFT and IDFT for the vectors DFT(x) and IDFT(y) this results in a best algorithm for cyclic convolutions.

Nega cyclic convolution is very useful if use in this algorithm it’s a update of convolution theorem. It can be stated as

A = (a^j), 0 ≤ j<n

A⁻¹ = (a^−j), 0 ≤ j < n

Now, we can state:

NegacyclicConvolution(X, Y) = A⁻¹ · IDFT (DFT (A · X) · DFT (A · Y)). 

The multiplications of recursive vectors element-by-element can easily calculated by nega cyclic convolution. It also faster than cyclic convolution theorem because it has slight modification mod 2ⁿ + 1.

Download  ECE Technical Seminar Report for Schonhage Stassen Algorithm Seminar Topic.