How to resolve the algorithm Jacobi symbol step by step in the PL/M programming language

Published on 12 May 2024 09:40 PM
#Pl/m

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

Source code in the pl/m programming language

100H: /* JACOBI SYMBOL                                                       */

   /* CP/M BDOS SYSTEM CALLS AND I/O ROUTINES                                */
   BDOS:   PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
   PR$CHAR:   PROCEDURE( C ); DECLARE C BYTE;    CALL BDOS( 2, C );    END;
   PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S );    END;
   PR$NL:     PROCEDURE; CALL PR$STRING( .( 0DH, 0AH, '$' ) );         END;
   PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH  */
      DECLARE N ADDRESS;
      DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
      V = N;
      W = LAST( N$STR );
      N$STR( W ) = '$';
      N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      DO WHILE( ( V := V / 10 ) > 0 );
         N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      END;
      CALL PR$STRING( .N$STR( W ) );
   END PR$NUMBER;

   /* TASK                                                                   */

   JACOBI: PROCEDURE( A$IN, N$IN )BYTE;
      DECLARE ( A$IN, N$IN ) ADDRESS;
      IF N$IN MOD 2 <> 1 THEN DO;
         CALL PR$STRING( .'JACOBI PARAMETER NOT ODD$' );
         RETURN 0;
         END;
      ELSE DO;
         DECLARE ( A, N, NM8, T ) ADDRESS;
         DECLARE JS BYTE;
         A = A$IN MOD N$IN; N = N$IN; JS = 1;
         DO WHILE A <> 0;
            DO WHILE A MOD 2 = 0;
               A = A / 2;
               NM8 = N MOD 8;
               IF NM8 = 3 OR NM8 = 5 THEN JS = - JS;
            END;
            T = A; A = N; N = T;
            IF A MOD 4 = 3 AND N MOD 4 = 3 THEN JS = - JS;
            A = A MOD N;
         END;
         IF N = 1 THEN RETURN JS;
                  ELSE RETURN 0;
      END;
   END JACOBI ;

   DECLARE ( A, N )ADDRESS;
   DECLARE JS BYTE;

   CALL PR$STRING( .'TABLE OF JACOBI(A, N):$' );CALL PR$NL;
   CALL PR$STRING( .'N/A   1   2   3   4   5   6   7$' );
   CALL PR$STRING( .'   8   9  10  11  12  13  14  15$' );CALL PR$NL;
   CALL PR$STRING( .'-------------------------------$' );
   CALL PR$STRING( .'--------------------------------$' );CALL PR$NL;
   DO N = 1 TO 29 BY 2;
      CALL PR$CHAR( ' ' );
      IF N < 10 THEN CALL PR$CHAR( ' ' );
      CALL PR$NUMBER( N );
      DO A = 1 TO 15;
         JS = JACOBI( A, N );
         IF      JS = 0 THEN CALL PR$STRING( .'   0$' );
         ELSE IF JS = 1 THEN CALL PR$STRING( .'   1$' );
         ELSE                CALL PR$STRING( .'  -1$' );
      END;
      CALL PR$NL;
   END;

EOF

You may also check:How to resolve the algorithm Range expansion step by step in the AWK programming language
You may also check:How to resolve the algorithm Draw a clock step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Loops/Foreach step by step in the REBOL programming language
You may also check:How to resolve the algorithm Arrays step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm RSA code step by step in the Seed7 programming language