Philip R Brenan >
Math-Modular-SquareRoot >
Math::Modular::SquareRoot

Module Version: 1.001
Math::Modular::SquareRoot - Modular square roots

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

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($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(@_)`

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($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($n)`

finds the product of the integers from 1 to $n. `factorial($n)`

will croak unless $n is a positive integer.

`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()`

.

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

PhilipRBrenan@handybackup.com

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.

syntax highlighting: