Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FactorialMod

Source Notebook

Fast factorial modulo a given number

Contributed by: Aster Ctor

ResourceFunction["FactorialMod"][n,p]

computes a fast version of Mod[Factorial[n],p].

Details and Options

ResourceFunction["FactorialMod"] accelerates its computiation using the Number Theoretic Transform (NTT).

Examples

Basic Examples (2) 

Compute a factorial modulo 53:

In[1]:=
ResourceFunction["FactorialMod"][42, 53]
Out[1]=

Check the result:

In[2]:=
Mod[Factorial[42], 53]
Out[2]=

Scope (4) 

Work with a nonprime modulus:

In[3]:=
p = 2*Prime[10^8]
Out[3]=

The simple algorithm is slow:

In[4]:=
Mod[Factorial[5*^6], p] // AbsoluteTiming
Out[4]=

A native speed up is two times faster:

In[5]:=
native[n_, p_] := Fold[Mod[#1 #2, p] &, Range[n]]; native[5*^6, p] // AbsoluteTiming
Out[5]=

NTT speed up is four times faster:

In[6]:=
ResourceFunction["FactorialMod"][5*^6, p] // AbsoluteTiming
Out[6]=

Publisher

Aster Ctor (MoeNet)

Version History

  • 1.0.0 – 23 October 2019

Related Resources

License Information