PROGRAM PRIMES; VAR PRIME : BOOLEAN; I,J,K,N,MAX : INTEGER; L, SQU : INTEGER; P : ARRAY[1..1296] OF INTEGER; U : ARRAY[1..36] OF INTEGER; BEGIN WRITELN('PROGRAM TO DETERMINE THE FIRST N PRIME INTEGERS'); WRITELN; WRITELN('ENTER N, THE DESIRED NUMBER OF PRIME INTEGERS: MAX = 3512'); READLN(N); P[1] := 2; L := 1; SQU := 4; MAX := 1; FOR I := 2 TO N + 10 - (N MOD 10) DO BEGIN REPEAT L := L+2; IF SQU <= L THEN BEGIN U[MAX] := SQU; MAX := MAX+1; SQU := P[MAX]*P[MAX] END; K := 2; PRIME := TRUE; WHILE PRIME AND (K U[K]); K := K+1 END; UNTIL PRIME; P[I] := L; IF (I MOD 10 = 0) THEN BEGIN IF I > N THEN BEGIN WRITELN; FOR J := I-9 TO N DO WRITE(P[J], ' '); END ELSE BEGIN WRITELN; FOR J := I-9 TO I DO WRITE(P[J], ' '); END; END; END; END. (* Listing 1 Prime Number Program *) PROGRAM RANDOM; VAR A,X,M,R : INTEGER[36]; N : INTEGER; BEGIN WRITELN('PROGRAM TO GENERATE A SEQUENCE OF PSUEDO RANDOM NUMBERS'); WRITELN; WRITELN('ENTER NUMBER OF INTEGERS DESIRED'); READLN(N); WRITELN; A := 4294967299; M := 184467440737095516; WRITELN('ENTER SEED INTEGER: SHOULD BE PRIME FOR MAXIMUM PERIOD'); READLN(X); WRITELN; WHILE N>0 DO BEGIN X := A*X; R := X DIV M; X := X-R*M; WRITELN(X); N := N-1; END END. (* Listing 2 Random Integer Generator *) PROGRAM RAND16; VAR A,X,M,R : INTEGER[36]; N : INTEGER; BEGIN WRITELN('PROGRAM TO GENERATE A SEQUENCE OF PSUEDO RANDOM NUMBERS'); WRITELN; WRITELN('ENTER NUMBER OF INTEGERS DESIRED'); READLN(N); WRITELN; WRITELN('ENTER ODD SEED INTEGER < 32767'); READLN(X); WRITELN; WHILE N>0 DO BEGIN X := 181*X; IF X<0 THEN X := X+32767+1; WRITELN(X); N := N-1 END END. (* Listing 3 16-bit Random Integer Generator *) PROGRAM EXP1; VAR A,A1,AMOD,B,P,P1,PROD,R: INTEGER[36]; BEGIN WRITELN('PROGRAM FOR FINDING (A EXP (B-1)/2) MOD B'); WRITELN; WRITELN('ENTER B, THE MODULUS'); READLN(B); WRITELN('ENTER A SUCCESSION OF TEST INTEGERS: '); WRITELN('ENTER ZERO TO TERMINATE'); WRITELN; READLN(A); A1 := A; WHILE A>0 DO BEGIN WRITELN; PROD := 1; P := (B-1) DIV 2; AMOD := A; WHILE P>0 DO BEGIN P1 := P; P := P DIV 2; IF (2*P) <> P1 THEN BEGIN PROD := PROD*AMOD; R := PROD DIV B; PROD := PROD-B*R END; AMOD := AMOD*AMOD; R := AMOD DIV B; AMOD := AMOD-B*R END; IF PROD = 1 THEN WRITELN('THE MODULAR EXPONENTIAL IS +1') ELSE IF (B-PROD)=1 THEN WRITELN('THE MODULAR EXPONENTIAL IS -1') ELSE WRITELN('THE MODULAR EXPONENTIAL IS ', PROD); WRITELN; WRITELN('========================================'); READLN(A); A1 := A END END. (* Listing 4 Modular Exponentiation Program *) PROGRAM PRIMTEST; VAR A,B,B1,R : INTEGER[36]; SGN,N,N1 : INTEGER; BEGIN WRITELN('PROGRAM FOR TESTING ODD INTEGERS FOR PRIMALITY'); WRITELN; WRITELN('ENTER B, THE NUMBER TO BE TESTED'); READLN(B1); WRITELN('ENTER NUMBER OF TEST INTEGERS'); READLN(N1); N := N1; WHILE N>0 DO BEGIN B := B1; WRITELN('NUMBER TO BE TESTED IS ', B); WRITELN('ENTER TEST INTEGER A1 DO BEGIN IF ((A DIV 2)*2) <> A THEN BEGIN R := B DIV A; R := B-R*A; IF (((A-1) DIV 4)*2)<>((A-1) DIV 2) THEN IF (((B-1) DIV 4)*2) <> ((B-1) DIV 2) THEN SGN := -SGN; B := A; A := R END ELSE BEGIN A := A DIV 2; IF (((B-1) DIV 4)*2) = ((B-1) DIV 2) THEN IF (((B-1) DIV 8)*2) <> ((B-1) DIV 4) THEN SGN := -SGN ELSE SGN := SGN ELSE IF (((B+1) DIV 8)*2) <> ((B+1) DIV 4) THEN SGN := -SGN ELSE SGN := SGN END END; IF A = 1 THEN BEGIN WRITELN('GCD = 1; J = ', SGN); WRITELN('======================================'); WRITELN END; IF A=0 THEN BEGIN WRITELN('GCD = ', B); WRITELN(' NUMBER IS NOT PRIME'); WRITELN('++++++++++++++++++++++++++++++++++++++') END; N := N-1 END END. (* Listing 5 Primality Test *) PROGRAM EUCLID; VAR A,B,B1,R : INTEGER[36]; BEGIN WRITELN('PROGRAM TO FIND GREATEST COMMON DENOMINATOR GCD(A,B)'); WRITELN; WRITELN('ENTER VALUE OF B'); READLN(B1); WRITELN; WRITELN('ENTER A VALUES IN SUCCESION'); WRITELN('ENTER ZERO TO TERMINATE'); WRITELN; READLN(A); WHILE A>0 DO BEGIN WHILE A>0 DO BEGIN B := B1; R := B DIV A; R := B-R*A; B := A; A := R; END; WRITELN(' ', B); WRITELN('---------------------------------------------------'); READLN(A) END END. (* Listing 6 Euclid's Algorithm *) PROGRAM MULINV; VAR M,M1,N,Q,U,V,Y,Z : INTEGER[36]; BEGIN WRITELN('PROGRAM FOR FINDING U SUCH THAT, FOR GIVEN V, V*U MOD M=1'); WRITELN; WRITELN('ENTER V'); READLN(V); WRITELN('ENTER M'); READLN(M); M1 := M; U := 1; Y:= 0; WHILE M>0 DO BEGIN Q := V DIV M; Z := Y; N := M; Y := U-Q*Y; U := Z; M := V-Q*M; V := N; END; IF U<0 THEN U := M1+U; IF V<>1 THEN WRITELN('V AND M ARE NOT RELATIVELY PRIME') ELSE WRITELN('V AND M ARE RELATIVELY PRIME: VALUE OF U IS ',U); END. (* Listing 7 Modular Multiplicative Inverse Program *) PROGRAM ENCRYPT; VAR E,E1,E2,N,P,PMOD,PROD,R : INTEGER[36]; BEGIN WRITELN('THIS PROGRAM IMPLEMENTS THE RSA ALGORITHM'); WRITELN('FOR ENCRYPTING OR DECRYPTING'); WRITELN; WRITELN('ENTER THE MODULUS N'); READLN(N); WRITELN; WRITELN('ENTER KEY FOR ENCRYPTING OR DECRYPTING'); READLN(E); WRITELN; WRITELN('ENTER INTEGERS TO BE ENCODED IN SUCCESSION'); WRITELN('ENTER ZERO TO TERMINATE'); READLN(P); E2 := E; WHILE P>0 DO BEGIN E := E2; PROD := 1; PMOD := P; WHILE E>0 DO BEGIN E1 := E; E := E DIV 2; IF (2*E) <> E1 THEN BEGIN PROD := PROD*PMOD; R := PROD DIV N; PROD := PROD-R*N; END; PMOD := PMOD*PMOD; R := PMOD DIV N; PMOD := PMOD-R*N END; WRITELN(' ', PROD); WRITELN('========================================'); READLN(P) END END. (* Listing 8 RSA Encryption-Decryption Program *)