What is the efficiency of the new Crown Sterling semiprime factoring method?

Question

In their press release a company called Crown Sterling describes they are working a paper that

includes four different geometric and arithmetic methods for public key (semiprime) factorization and one of the methods titled, “The Reciprocal Factoring Method” includes an analysis of reciprocal values of public keys and their embedded private keys (prime factors) found within their period decimal extensions.

According to the CEO's Instagram, the factoring method is quite simple: search for the primes in the decimal expansion of the reciprocal of the semi prime. It doesn't hold true for all primes, and I get that its not even remotely efficient enough, but while the controversy is ongoing, it would be helpful to know just how inefficient their method is.

Answer 1

The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works. For a semiprime $n$ chosen by modern RSA key generation methods, there are approximately $\sqrt n$ candidate solutions to check, which is also the expected cost of this method. For instance, with RSA-2048, it will cost approximately $2^{1024}$ trial boogers.

---

The technical term for everything about these clowns is ‘uncastrated male bovine stool’.^* There is no more merit to the technical claims of Crown Sterling than there is to Treadwell Stanton DuPont. The company's method is quite simple: the CEO Robert Grant is a scam artist who presumably uses technobabble like this to defraud unwary investors, and who sank some of the money into buying the prestige of a BlackHat talk slot (which is something that BlackHat really shouldn't offer) in order to drum up more hype around their scam.

And then they act the victim in a bogus narrative of persecution by the dominant establishment when subjected to universal derision by any competent cryptographers who bother to look at the nonsense.

---

So, what did these scam artists claim?

• In their arXiv draft (which they proudly claim Cornell University published even though anyone can upload a draft to the arXiv with no peer review), Robert Grant and Talal Ghannam:

  • (§II) made the remarkable observation that every prime above 3 is congruent to $\pm1$ modulo 6 (proof: $2 \mid 6k \pm 2$ and $3 \mid 6k \pm 3$; this is the newest result they recycled, several centuries old—first published no later than 1509 and first proven no later than 1603, according to Dickson pp. 7–9, but quite possibly known earlier because it's so obvious);
  • (§III) reinvented the sieve of Eratosthenes several thousand years late;
  • (§IV) discovered that $x \mapsto x \bmod 9$ is a ring homomorphism (a technique known since antiquity and more commonly called ‘casting out nines’), and figured out that if $x \equiv 3 \pmod 9$, $x \equiv 6 \pmod 9$, or $x \equiv 9 \pmod 9$, then $x$ can't be prime (proof: duh);
  • (§VI) deluded themselves into thinking if $pq \equiv 1 \pmod{10}$ then either $\{p \bmod 10, q \bmod 10\} = \{3,7\}$ or $p \equiv q \equiv 1 \pmod{10}$ (counterexample: $19\cdot 29 = 551$; perhaps they used ‘proof by trying numbers until I got bored’); and
  • (Appendix) proved that $p \equiv \pm 1 \pmod 6$ implies $p^2 \equiv 1 \pmod{24}$, a trivial consequence of the Chinese remainder theorem first stated no later than nearly two millennia ago (proof: $p \equiv \pm1 \pmod 2$ so $p \bmod 8 \in \{1,3,5,7\}$ so $p^2 \equiv 1 \pmod 8$, and $p \equiv \pm1 \pmod 3$ so $p^2 \equiv 1 \pmod 3$; hence by CRT, $p^2 \equiv 1 \pmod{3\cdot 8}$).

  Earthshattering stuff, I'm sure you'll agree.

• In March, they published a press release as Strathspey Crown LLC announcing their findings with no additional technical claims.

• In August, at BlackHat, they spent 115 000 USD for an unreviewed talk slot to debut Time AI, which

  uses five dimensions of encryption, leveraging biometrics, music’s infinite variability and dynamic change to secure your data

  and is sometimes quantum and which was predictably laughed off the stage at considerable cost to BlackHat's reputation as a purveyor of fine corporate stoogery.

  (Crown Sterling have since sued BlackHat because people were mean to them and BlackHat did nothing to stop people from pointing out their idiocy when they presented it at the BlackHat podium they bought.)

• In September, they held a live stunt where they alleged to factor a 256-bit semiprime on a laptop on stage.

  For perspective, this record was surpassed no less than a quarter century ago by Dixon & Lenstra, who reported solving a 110-digit/364-bit factoring challenge. The 129-digit/426-bit factoring challenge announced in Scientific American by Martin Gardner in 1977 with the advent of RSA was solved in 1994 by Atkins, Graff, Lenstra, & Leyland revealing the magic words Squeamish Ossifrage. Today you can factor a 512-bit integer for 100 USD using CADO-NFS and msieve on Amazon EC2.

  Well, actually, Grant walked back the claim that it was a laptop (apologies for Twitter link to screenshot of Instagram; I don't deal in Instagram so I can't link to the page directly). But randos on Twitter showed how you, too, can break this record in the privacy of your own living room on your own laptop in comparable time.

  The fraudsters gave no details about the alleged novel factoring algorithm actually used in the demonstration. A poor soul—pour one out for him!—who actually bothered to watch the video (which I'm not linking because I don't want to give these fraudsters any clicks) noted that some of the output of the alleged program appears to be output from CADO-NFS.

• What about the Instagram post? (Always a highly reputable venue for mathematical and cryptologic publication!) The claim seems to be that you can find the factors of $pq$ in the decimal expansion of $1/pq$.

  First, it doesn't always work. For example, $1/(11\cdot13) = 0.\overline{006993}$ in which neither factor 11 nor 13 appears. But one might wonder whether it probably happens.

  The period of the decimal expansion of $1/pq$ for prime $p$ and $q$ is $\operatorname{lcm}(\operatorname{ord}_p 10, \operatorname{ord}_q 10)$, which is usually not much smaller than $pq$. If we model the expansion as a uniform random digit string $pq$ (not $\log_{10} pq$, but $pq$) digits long, what's the probability of finding particular a $\log_b p$-digit string, namely $p$, in it? The expected number of times that any particular $m$-character needle appears as a substring of a uniform random $h$-character haystack in a $b$-symbol alphabet is $(h - m + 1) b^{-m}$ (proof: exercise for reader). Here $m \approx \log_b p$ and $h \approx pq$, so this is about $$(pq - \log_b p + 1) b^{-\log_b p} \approx q.$$ Cursory random experiments suggest that this is a reasonable model for the substring search, and I know of no theory that would suggest otherwise; it is up to the fraudsters to put up or shut up if they can prove anything better than this.

  In other words, in this model, there's a reasonable probability that the the method works if you're willing to search through about (say) $2^{1024}$ possible candidate factors of the 2048-bit semiprime in question. Which, as it happens, is essentially random trial division. The fraudsters make it look easy by showing a screenshot with the answer already highlighted in a selectively cropped fragment that skipped over thousands of digits—about as many digits as the value of the numbers we're searching for.

In brief, these clowns—who are trumpeting thousand-year-old mathematical results on a preprint host open to the world as publications by Cornell University—appear to have at best caught up to the state of the art in factoring records from a quarter century ago by copying an alleged algorithm into software that looks just like off-the-shelf factoring software…or they're just using the off-the-shelf factoring software to wow an audience of chumps.

---

_{^* Stack Exchange may have a profanity filter that has the unfortunate effect of interfering with using certain precise technical terminology.}

Answer 2

TLDR: the efficiency of what they demo is below state of the art a decade ago. What they describe would be plain abyssal.

---

In the event described in the press release, Crown Sterling made a public demonstration, which can be watched there. The meat of it is a demonstration of the factorization of a 77-digit (256-bit) public modulus of an RSA key, 83473593554391843334619428139045661537976651941410655062632649869770538548577

Numbers of that size were already factorizable in the late 1980s, see Status Report on Factoring (At the Sandia National Laboratories) in proceedings of Eurocrypt 1984. Their factorization lasts 52s with a reported 32 cores, which would have been nice 15 years ago. Googling their number brings well-substantiated assertions that the program used in the demo has output reminiscent of CADO-NFS, and comparable runtime.

If you have a modern browser and one core of your CPU to spare for few minutes, then you can cut-and-paste that number (or any of that size) on this website. A fraction of your own computer will factor the number with ECM, at respectable speed thanks to WebAssembly.

This shows that the technology demonstrated is currently not a threat to modern-size RSA keys, and fuels the suspicions in an other answer.

---

I could not locate the paper "Novel Geometric Methods for Semiprime Factorization" announced in the press release, and thus can only comment two others sources:

A) An earlier paper of the same authors, Robert E. Grant and Talal Ghannam: Accurate and Infinite Prime Prediction from Novel Quasi-Prime Analytical Methodology, posted to arXiv on 2019-03-20. Only section VI discus prime factorization, on about half a page. It does not precisely state an algorithm, nor quantitatively characterize efficiency.

B) The method illustrated by the Instagram post linked in the question. It is based on the premise that (the decimal expression of) one of the factor of a semi-prime to be factored will likely appear in (the decimal expression of) its inverse. The factorization technique seems to be: compute that inverse over a sufficient length, try substrings of the appropriate size (perhaps restricting to those not obviously composite), and check that factor by trial division.

That works. But under the default assumption that a factor has no tendency to appear in the inverse earlier than a random digit sequence of similar size, in order to find a $b$-bit factor of a $2b$-bit semiprime, we are expected to test more than $2^{b-4}$ integers. That ends up with a method comparable to trial division by random numbers, grossly inefficient and not applicable to RSA moduli larger than 100-bit using the hardare and time in the demo (and certainly not for the 256-bit number in the demo).

Note: in the example picture on Instagram, the first factor found (5987) would be about the 1220's one tested, consistent with the above estimation. The picture is cropped, with the effect of showing considerably less digits.