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.

cpanm Math::Modular::SquareRoot

perl -MCPAN -e shell
install Math::Modular::SquareRoot