Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FactorIntegerHart

Source Notebook

Factor an integer using Hart's one line factoring algorithm

Contributed by: Sam Blake

ResourceFunction["FactorIntegerHart"][n]

returns a pair of factors of the integer n, using Hart’s algorithm.

Details and Options

Hart's algorithm will quickly factor semiprimes of the form n=pq, where p=NextPrime[c1ba1±d1] and q=NextPrime[c2ba2±d2], where a1,a2 are relatively close and c1,c2,d1,d2 are small integers. Within this context, we denote the base to be b and c1,c2 the coefficients of the base.
ResourceFunction["FactorIntegerHart"] accepts the option MaxIterations, which limits how far ResourceFunction["FactorIntegerHart"] searches for a factor of n. The default is 216.

Examples

Basic Examples (1) 

Original example given by Hart:

In[1]:=
n = NextPrime[10^29 + 5342347] NextPrime[10^31 + 2232788]
Out[1]=
In[2]:=
ResourceFunction["FactorIntegerHart"][n]
Out[2]=

Scope (3) 

Hart's algorithm will work when the base is rational, in this case the base is 101/11:

In[3]:=
exampleSemiprime = NextPrime[17 (101/11)^63 + 5678956789] NextPrime[ 117 (101/11)^63 - 12341234]
Out[3]=
In[4]:=
exampleSemiprime // ResourceFunction[ "FactorIntegerHart"] // RepeatedTiming
Out[4]=

The coefficients may also be (distinct) rational numbers:

In[5]:=
exampleSemiprime = NextPrime[17/2 (101/11)^63 + 5678956789] NextPrime[ 117/3 (101/11)^63 - 12341234]
Out[5]=
In[6]:=
exampleSemiprime // ResourceFunction[ "FactorIntegerHart"] // RepeatedTiming
Out[6]=

The exponents of the base can be distinct, providing they are sufficiently close:

In[7]:=
exampleSemiprime = NextPrime[2 7^45 + 38] NextPrime[3 7^48 - 71]
Out[7]=
In[8]:=
exampleSemiprime // ResourceFunction[ "FactorIntegerHart"] // RepeatedTiming
Out[8]=

Options (2) 

MaxIterations (2) 

By default, the maximum number of iterations is 216:

In[9]:=
ResourceFunction["FactorIntegerHart"][ n = 1154689061566522755284577058047319621074553657665364264527802824091235865100064881]
Out[9]=

Increasing MaxIterations allows us to factor this integer:

In[10]:=
ResourceFunction["FactorIntegerHart"][n, MaxIterations -> \[Infinity]]
Out[10]=

Properties and Relations (1) 

For the applicable class of semiprimes, FactorIntegerHart will usually be much faster than FactorInteger:

In[11]:=
ResourceFunction["FactorIntegerHart"][ n = 2550203867524190159813615613569950921929164590015415234947741863729346003965839699] // Timing
Out[11]=
In[12]:=
TimeConstrained[FactorInteger[n] // Timing, 10]
Out[12]=

Possible Issues (1) 

Unlike FactorInteger, the factors returned by FactorIntegerHart may not be prime:

In[13]:=
ResourceFunction["FactorIntegerHart"][(20! + 3) (20! - 3)]
Out[13]=
In[14]:=
PrimeQ /@ %
Out[14]=

Neat Examples (1) 

Factoring an enormous semiprime:

In[15]:=
ResourceFunction["FactorIntegerHart"][ 57628992435296046100825955337251527226862132936443974304301515294012876192216463180602260029274490048428393856106930535011357929624071852468923518803459296855870065748733529070079999076318901385683626480350443936163434243929556611962874569316345247841485993209669521371581538629250149894789380968547962579244903321724835829532138880189028097700172187317894705397515389589363735819944534668717404387811020740441719871018188536066335693126156724440066615075040441315272163356173949742860199974942889072388046870964295728704387185836602422469360467733713158567595067776046029659437182384504689297065227198123485898335851833605553789799703161967675984346463475712764029436369] // RepeatedTiming
Out[15]=

Publisher

Sam Blake

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 17 November 2023

Source Metadata

  • Citation:
    Hart, W. (2012) "One Line Factoring Algorithm". J. Aust. Math. Soc. vol. 92. pp. 61-69.

Related Resources

License Information