(**************************************************************************)
(*                                                                        *)
(*  PMOS/2 software library                                               *)
(*  Copyright (C) 2023   Peter Moylan                                     *)
(*                                                                        *)
(*  This program is free software: you can redistribute it and/or modify  *)
(*  it under the terms of the GNU General Public License as published by  *)
(*  the Free Software Foundation, either version 3 of the License, or     *)
(*  (at your option) any later version.                                   *)
(*                                                                        *)
(*  This program is distributed in the hope that it will be useful,       *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *)
(*  GNU General Public License for more details.                          *)
(*                                                                        *)
(*  You should have received a copy of the GNU General Public License     *)
(*  along with this program.  If not, see <http://www.gnu.org/licenses/>. *)
(*                                                                        *)
(*  To contact author:   http://www.pmoylan.org   peter@pmoylan.org       *)
(*                                                                        *)
(**************************************************************************)

DEFINITION MODULE Primes;

        (********************************************************)
        (*                                                      *)
        (*            Generation of prime numbers               *)
        (*                                                      *)
        (*  Programmer:         P. Moylan                       *)
        (*  Started:            15 December 2017                *)
        (*  Last edited:        14 July 2023                    *)
        (*  Status:             OK                              *)
        (*                                                      *)
        (********************************************************)


FROM BigNum IMPORT
    (* type *)  BN;


PROCEDURE RandomPrime (N, mask: CARDINAL;  fast: BOOLEAN): BN;

    (* Returns a random probable prime that is N words long.  This is   *)
    (* just for proof of concept.  I'll probably have to come up with   *)
    (* a better random number generator.                                *)

    (* The mask defines the number of significant bits in the top word, *)
    (* with mask = 0FFFFFFFFH if we use the whole word.                 *)

    (* If fast is FALSE we make the test tougher, but slower.           *)

PROCEDURE IsPerfectSquare (A: BN): BOOLEAN;

    (* Returns TRUE iff A is the square of an integer.  *)

PROCEDURE Jacobi (k, n: BN): INTEGER;

    (* Calculates the Jacobi symbol (k/n).  *)

PROCEDURE RabinMiller (A: BN;  nrounds: CARDINAL): BOOLEAN;

    (* Returns TRUE if A is a probable prime.  The larger nrounds is,   *)
    (* the lower the risk of returning a false positive.  NB: for       *)
    (* trustworthy results use RandomPrime, above, which combines       *)
    (* RabinMiller with other tests.                                    *)

END Primes.

