How to resolve the algorithm Jacobi symbol step by step in the ALGOL W programming language

Published on 12 May 2024 09:40 PM
#Algol w

How to resolve the algorithm Jacobi symbol step by step in the ALGOL W programming language

Table of Contents

Problem Statement

The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)p_2^(k_2)...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p) If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n). Calculate the Jacobi symbol (a | n).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Jacobi symbol step by step in the ALGOL W programming language

Source code in the algol programming language

begin % Jacobi symbol %

    integer procedure jacobi( integer value aIn, nIn ) ;
        if nIn <= 0 or not odd( nIn ) then begin
            write( "The 'n' parameter of jacobi must be an odd positive integer." );
            0
            end
        else begin
            integer a, n, js;
            a := aIn rem nIn; n := nIn; js := 1;
            while a not = 0 do begin
                while a rem 2 = 0 do begin
                    integer nm8;
                    a := a div 2;
                    nm8 := n rem 8;
                    if nm8 = 3 or nm8 = 5 then js := - js;
                end while_a_rem_2_eq_0 ;
                begin integer t; t := a; a := n; n := t end;
                if a rem 4 = 3 and n rem 4 = 3 then js := - js;
                a := a rem n
            end;
            if n = 1 then js else 0
        end jacobi ;

    write( "Table of jacobi(a, n):" );;
    write( "n/a   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15" );
    write( "---------------------------------------------------------------" );
    for n := 1 step 2 until 29 do begin
        write( i_w := 3, s_w := 0, n );
        for a := 1 until 15 do writeon( i_w := 4, s_w := 0, jacobi( a, n ) );
    end

end.

You may also check:How to resolve the algorithm Leap year step by step in the K programming language
You may also check:How to resolve the algorithm Display a linear combination step by step in the Arturo programming language
You may also check:How to resolve the algorithm The Twelve Days of Christmas step by step in the Janet programming language
You may also check:How to resolve the algorithm Averages/Simple moving average step by step in the Rust programming language
You may also check:How to resolve the algorithm Letter frequency step by step in the Common Lisp programming language