Name
    Math::Modular::SquareRoot - Modular square roots

Synopsis
    Find the integer square roots of $S modulo $a, where $S,$a are integers:

     use Math::Modular::SquareRoot qw(:msqrt);

     msqrt1(3,11);

     # 5 6

    Find the integer square roots of $S modulo $a*$b when $S,$a,$b are
    integers:

     use Math::Modular::SquareRoot qw(:msqrt);

     msqrt2((243243 **2, 1_000_037, 1_000_039);

     # 243243 243252243227 756823758219 1000075758200

    Find the greatest common divisor of a list of numbers:

     use Math::Modular::SquareRoot qw(gcd);

     gcd 10,12,6;

     # 2

    Find the greatest common divisor of two numbers, optimized for speed
    with no parameter checking:

     use Math::Modular::SquareRoot qw(gcd2);

     gcd2 9,24;

     # 3

    Solve $a*$m+$b*$n == 1 for integers $m,$n, given integers $a,$b where
    gcd($a,$b) == 1

     use Math::Modular::SquareRoot qw(dgcd);

     dgcd(12, 41); 

     # 24 -7
     # 24*12-7*41 == 1

    Factorial of a number:

     use Math::Modular::SquareRoot qw(factorial);

     factorial(6);

     # 720

    Check whether an integer is a prime:

     use Math::Modular::SquareRoot qw(prime);

     prime(9);

     # 0

    or possibly prime by trying to factor a specified number of times:

     use Math::Modular::SquareRoot qw(prime);

     prime(2**31-1, 7);

     # 1

Description
    The routines

      msqrt1 ($S,$a*$b)> 
      msqrt2 ($S,$a,$b)>

    demonstrate the difference in time required to find the modular square
    root of a number $S modulo $p when the factorization of $p is
    respectively unknown and known. To see this difference, compare the time
    required to process test: "t/1.t" with line 11 uncommented with that of
    "test/2.t". The time required to find the modular square root of $S
    modulo $p grows exponentially with the length $l in characters of the
    number $p. For well chosen:

      $p=$a*$b

    the difference in times required to recover the square root can be made
    very large for small $l. The difference can be made so large that the
    unfactored version takes more than a year's effort by all the computers
    on planet Earth to solve, whilst the factored version can be solved in a
    few seconds on one personal computer.

    Ideally $a,$b and should be prime. This prevents alternate
    factorizarizations of $p being present which would lower the difference
    in time to find the modular square root.

  msqrt1() msqrt2()
    "msqrt1($S,$a)" finds the square roots of $S modulo $a where $S,$a are
    integers. There are normally either zero or two roots for a given pair
    of numbers if gcd($S,$a) == 1 although in the case that $S==0 and $a is
    prime, zero will have just one square root: zero. If gcd($S,$a) != 1
    there will be more pairs of square roots. The square roots are returned
    as a list. "msqrt1($a,$S)" will croak if its arguments are not integers,
    or if $a is zero.

    "msqrt2($a,$b,$S)" finds the square roots of $S modulo $a*$b where
    $S,$a,$b are integers. There are normally either zero or four roots for
    a given triple of numbers if gcd($S,$a) == 1 and gcd($S,$b) == 1. If
    this is not so there will be more pairs of square roots. The square
    roots are returned as a list. "msqrt2($a,$b,$S)" will croak if its
    arguments are not integers, or if $a or $b are zero.

  gcd() gcd2()
    "gcd(@_)" finds the greatest common divisor of a list of numbers @_,
    with error checks to validate the parameter list. "gcd(@_)" will croak
    unless all of its arguments are integers. At least one of these integers
    must be non zero.

    "gcd2($a,$b)" finds the greatest common divisor of two integers $a,$b as
    quickly as possible with no error checks to validate the parameter list.
    "gcd2(@_)" can always be used as a plug in replacement for "gcd($a,$b)"
    but not vice versa.

    "dgcd($a,$b)" solves the equation:

     $a*$m+$b*$n == 1

    for $m,$n given $a,$b where $a,$b,$m,$n are integers and

     gcd($a,$b) == 1

    The returned value is the list:

     ($m, $n)

    A check is made that the solution does solve the above equation, a croak
    is issued if this test fails. "dgcd($a,$b)" will also croak unless
    supplied with two non zero integers as parameters.

  prime()
    "prime($p)" checks that $p is prime, returning 1 if it is, 0 if it is
    not. "prime($p)" will croak unless it is supplied with one integer
    parameter greater than zero.

    "prime($p,$n)" checks that $p is prime by trying the first $N = 10**$n
    integers as divisors, while at the same time, finding the greatest
    common divisor of $p and a number at chosen at random between $N and the
    square root of $p $N times. If neither of these techniques finds a
    divisor, it is possible that $p is prime and the function retuerns 1,
    else 0.

  factorial()
    "factorial($n)" finds the product of the integers from 1 to $n.
    "factorial($n)" will croak unless $n is a positive integer.

Export
    "dgcd() factorial() gcd() gcd2() msqrt1() msqrt2() prime()" are exported
    upon request. Alternatively the tag :all exports all these functions,
    while the tag :sqrt exports just "msqrt1() msqrt2()".

Installation
    Standard Module::Build process for building and installing modules:

      perl Build.PL
      ./Build
      ./Build test
      ./Build install

    Or, if you're on a platform (like DOS or Windows) that doesn't require
    the "./" notation, you can do this:

      perl Build.PL
      Build
      Build test
      Build install

Author
    PhilipRBrenan@handybackup.com

    http://www.handybackup.com

See Also
Copyright
    Copyright (c) 2009 Philip R Brenan.

    This module is free software. It may be used, redistributed and/or
    modified under the same terms as Perl itself.