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.