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

Published on 12 May 2024 09:40 PM
#Raku

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

Source code in the raku programming language

# Jacobi function
sub infix: (Int $k is copy, Int $n is copy where * % 2) {
    $k %= $n;
    my $jacobi = 1;
    while $k {
        while $k %% 2 {
            $k div= 2;
            $jacobi *= -1 if $n % 8 == 3 | 5;
        }
        ($k, $n) = $n, $k;
        $jacobi *= -1 if 3 == $n%4 & $k%4;
        $k %= $n;
    }
    $n == 1 ?? $jacobi !! 0
}

# Testing

my $maxa = 30;
my $maxn = 29;

say 'n\k ', (1..$maxa).fmt: '%3d';
say '   ', '-' x 4 * $maxa;
for 1,*+2 … $maxn -> $n {
    print $n.fmt: '%3d';
    for 1..$maxa -> $k {
        print ($k J $n).fmt: '%4d';
    }
    print "\n";
}

You may also check:How to resolve the algorithm Luhn test of credit card numbers step by step in the OCaml programming language
You may also check:How to resolve the algorithm Luhn test of credit card numbers step by step in the K programming language
You may also check:How to resolve the algorithm String append step by step in the Scala programming language
You may also check:How to resolve the algorithm Morse code step by step in the Pascal programming language
You may also check:How to resolve the algorithm MD5/Implementation step by step in the Common Lisp programming language