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

Published on 12 May 2024 09:40 PM
#Erlang

How to resolve the algorithm Jacobi symbol step by step in the Erlang 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 Erlang programming language

Source code in the erlang programming language

jacobi(_, N) when N =< 0 -> jacobi_domain_error;
jacobi(_, N) when (N band 1) =:= 0 -> jacobi_domain_error;
jacobi(A, N) when A < 0 ->
    J2 = ja(-A, N),
    case N band 3 of
        1 -> J2;
        3 -> -J2
    end;
jacobi(A, N) -> ja(A, N).

ja(0, _) -> 0;
ja(1, _) -> 1;
ja(A, N) when A >= N -> ja(A rem N, N);
ja(A, N) when (A band 1) =:= 0 -> % A is even
    J2 = ja(A bsr 1, N),
    case N band 7 of
        1 -> J2;
        3 -> -J2;
        5 -> -J2;
        7 -> J2
    end;
ja(A, N) ->    % if we get here, A is odd, so we can flip it.
    J2 = ja(N, A),
    case (A band 3 =:= 3) and (N band 3 =:= 3) of
        true  -> -J2;
        false -> J2
    end.

You may also check:How to resolve the algorithm Append a record to the end of a text file step by step in the MATLAB / Octave programming language
You may also check:How to resolve the algorithm Pick random element step by step in the Falcon programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the ABAP programming language
You may also check:How to resolve the algorithm Input loop step by step in the Rust programming language
You may also check:How to resolve the algorithm Loops/Nested step by step in the ALGOL 68 programming language