Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FactorSemiprime

Source Notebook

Fast integer factorization of a certain class of semiprimes

Contributed by: Sam Blake

ResourceFunction["FactorSemiprime"][n]

computes the prime factorisation of the semiprime, n.

Details and Options

Given positive integers a,b such that a>b and a semiprime N, we may compute a factor, q, of N by creating the sequence where Q0=N. The sequence terminates if Qk<2, in which case the method has failed for the a/b-rational base representation. Otherwise, the sequence terminates if , in which case we have found a factor, q, of N.
Similar to Fermat's factorisation algorithm, which factors N=p q quickly when p is close to , ResourceFunction["FactorSemiprime"] will factor N=p q quickly when , with and a,b are exhaustively searchable.
Similar to trial division, which tests successive odd integers for divisibility, ResourceFunction["FactorSemiprime"] exhaustively tests each possible a/b-rational base representation of p in lexicographic order. That is, a/b=2,3,4,3/2,5,6,5/2,4/3,7,5/3,…
However, unlike trial division, for a single a/b, if , then ResourceFunction["FactorSemiprime"] will obtain the factor , for all c∈ℕ and for all Δ∈ℕ such that .
Much like other existing algorithms for integer factorisation, it is exceedingly unlikely that ResourceFunction["FactorSemiprime"] will quickly factor an arbitrary, large semiprime.
ResourceFunction["FactorSemiprime"] cannot quickly factor any semiprimes from the RSA Factoring Challenge.

Examples

Basic Examples (1) 

Factoring a small semiprime:

In[1]:=
ResourceFunction["FactorSemiprime"][ 71182049442858712148942698958093] // RepeatedTiming
Out[1]=

Scope (4) 

Factoring a 1178-bit semiprime. This factorisation is faster than the previous example as the base representation of the larger prime factor is (exhaustively) searched sooner:

In[2]:=
ResourceFunction["FactorSemiprime"][ 4035594397856978730116340001934921254572690987592701065254660135262792660067506541986580659177825246436531145839296242103812804324377528485848154088536008235413752938842227921141307849016281927942876956586098725341320205397768504290230954934143147130959878277148868527735858143934651684443466139855810555747255305233037482909186346108248405004315340601559] // RepeatedTiming
Out[2]=

Here we factor a semiprime, N=p q, where p is a prime close to (5/3)512 and p≫q:

In[3]:=
SeedRandom[123456789]; q = RandomPrime[{2^131, 2^132}] SeedRandom[];
Out[4]=
In[5]:=
p = NextPrime[(5/3)^555] \[ScriptCapitalN] = p q ResourceFunction["FactorSemiprime"][\[ScriptCapitalN]]
Out[5]=
Out[6]=
Out[7]=

Continuing this example, we can factor N=p q when p is close to 10001000100010003(5/3)555, where 10001000100010003 is an arbitrary integer coefficient:

In[8]:=
p = NextPrime[10001000100010003 (5/3)^555]
Out[8]=
In[9]:=
\[ScriptCapitalN] = p q
Out[9]=
In[10]:=
ResourceFunction["FactorSemiprime"][\[ScriptCapitalN]]
Out[10]=

We can still factor N=p q when p is Δ from 10001000100010003(5/3)555. That is p=10001000100010003(5/3)555±Δ, where :

In[11]:=
\[CapitalDelta] = Floor[(5/3)^555/q] p = NextPrime[10001000100010003 (5/3)^555 - \[CapitalDelta]] \[ScriptCapitalN]min = p q ResourceFunction["FactorSemiprime"][\[ScriptCapitalN]min]
Out[11]=
Out[12]=
Out[13]=
Out[14]=
In[15]:=
\[CapitalDelta] = Floor[(5/3)^555/q] p = NextPrime[10001000100010003 (5/3)^555 + \[CapitalDelta]] \[ScriptCapitalN]max = p q ResourceFunction["FactorSemiprime"][\[ScriptCapitalN]max]
Out[15]=
Out[16]=
Out[17]=
Out[18]=

Options (1) 

FactorSemiprimeMessages

In[19]:=
ResourceFunction["FactorSemiprime"][71182049442858712148942698958093, "FactorSemiprimeMessages" -> True] // RepeatedTiming

InitialBase

In[20]:=
ResourceFunction["FactorSemiprime"][ 13070989587597546374716464770975785289589280708760293515652989663172886876841898461676231357599040014559104151905105163940698243537183737604630731215233980419718036692731072871532417578375227977581, "InitialBase" -> 278] // RepeatedTiming
Out[20]=

SpecificBase (1) 

Factoring RSA-250 by specifying the rational base. Unfortunately, we have no direct (non-exhaustive) way to compute or estimate this base without the factors:

In[21]:=
ResourceFunction[ "FactorSemiprime"][2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937, "SpecificBase" -> 913934318098202395814582302506729464949125254254317321565736649/ 186798340046549841436465142394030629044917061492763974301888031]
Out[21]=

Possible Issues (2) 

Unlike FactorInteger, FactorSemiprime returns a single integer result:

In[22]:=
FactorInteger[2^2^6 + 1]
Out[22]=
In[23]:=
ResourceFunction["FactorSemiprime"][2^2^6 + 1]
Out[23]=

If the input to FactorSemiprime is not a semiprime, then the product of one or more factors may be returned:

In[24]:=
ResourceFunction["FactorSemiprime"][2^4 3 373]
Out[24]=
In[25]:=
ResourceFunction["FactorSemiprime"][2 3 373]
Out[25]=

Neat Examples (1) 

Factoring an enormous semiprime:

In[26]:=
NextPrime[100!] NextPrime[334!] % %% // ResourceFunction["FactorSemiprime"] // Timing
Out[26]=
Out[27]=
Out[28]=

Publisher

Sam Blake

Version History

  • 1.0.0 – 12 September 2022

Related Resources

Author Notes

At present we perform an exhaustive search on the a/b, it would be interesting to see if the continued fraction-type approach of Lehman could be adapted to this search.

The upper bound 1+Ceiling[Log[2,ndivs]] is heuristic, but seems to work well.

License Information