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.