Function Repository Resource:

FactorSemiprime

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]:=
 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]:=
 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]:=
 Out[4]=
 In[5]:=
 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]:=
 Out[8]=
 In[9]:=
 Out[9]=
 In[10]:=
 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]:=
 Out[11]=
 Out[12]=
 Out[13]=
 Out[14]=
 In[15]:=
 Out[15]=
 Out[16]=
 Out[17]=
 Out[18]=

Options (1)

FactorSemiprimeMessages

 In[19]:=

InitialBase

 In[20]:=
 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]:=
 Out[21]=

Possible Issues (2)

Unlike FactorInteger, FactorSemiprime returns a single integer result:

 In[22]:=
 Out[22]=
 In[23]:=
 Out[23]=

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

 In[24]:=
 Out[24]=
 In[25]:=
 Out[25]=

Neat Examples (1)

Factoring an enormous semiprime:

 In[26]:=
 Out[26]=
 Out[27]=
 Out[28]=

Sam Blake

Version History

• 1.0.0 – 12 September 2022

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.