Math::NumberTheory

Raku package with Number theory functions.

The function names and features follow the Number theory functions of Wolfram Language.

Installation

From Zef ecosystem:

zef install Math::NumberTheory

From GitHub:

zef install https://github.com/antononcube/Raku-Math-NumberTheory

Usage examples

Factor integers

Gives a list of the prime factors of an integer argument, together with their exponents:

use Math::NumberTheory;
factor-integer(factorial(20))

# [(2 18) (3 8) (5 4) (7 2) (11 1) (13 1) (17 1) (19 1)]

Remark: By default factor-integer uses Pollard's Rho algorithm -- specified with method => 'rho' -- as implemented at RosettaCode, [RC1], with similar implementations provided by "Prime::Factor", [SSp1], and "Math::Sequences", [RCp1].

Do partial factorization, pulling out at most k distinct factors:

factor-integer(factorial(20), 3, method => 'trial')

# [(2 18) (3 8) (5 4)]

Chinese reminders

Data:

my @data = 931074546, 117172357, 482333642, 199386034, 394354985;

# [931074546 117172357 482333642 199386034 394354985]

Keys:

#my @keys = random-prime(10**9 .. 10**12, @data.elems);
my @keys = 274199185649, 786765306443, 970592805341, 293623796783, 238475031661;

# [274199185649 786765306443 970592805341 293623796783 238475031661]

Remark: Using these larger keys is also a performance check.

Encrypted data:

my $encrypted = chinese-reminder(@data, @keys);

# 6681669841357504673192908619871066558177944924838942629020

Decrypted:

my @decrypted = @keys.map($encrypted mod *);

# [931074546 117172357 482333642 199386034 394354985]

References

[RC1] Rosetta Code, Prime decomposition, Section "Pure Raku".

[RCp1] Raku Community, Math::Sequences Raku package, (2016-2024), GitHub/raku-community-modules.

[SSp1] Stephen Schulze, Prime::Factor Raku package, (2016-2023), GitHub/thundergnat.