0
$\begingroup$

Under which conditions is a large semiprime possible to factor? In particular, is the following 400-digit semiprime actually trivial to factor into primes?

6962155154859963260211100482357357666900094513013513488352858667799199787495340476167566639530574848375895722792291996203873323650274512138128403360943634134259376986501375967452208380337012919869885380406071772232795575963202558402893589313281327208179913789760736615950818685956393838601277519011418885197723428318400763080858914698836058070301404903262955501113318317950597435778777212408626799143

Improve this question
$\endgroup$
6

4 Answers 4

Reset to default
3
$\begingroup$

Yes, this 400 digit semiprime does have a large weakness that enables it to be factored in hours.

I have factored this number, so you could be kind and tell me where this CTF is so that I can get credit.(Said half joking)

Neither Fermat's nor ECM nor SNFS is going to help you in any reasonable amount of time.

The p factor has 41606 in the 15-19th upper digits and q has 89827 in the 15-19th upper digits.

Update (moved here by moderator)

Perhaps this class of methods? No
Or/and using a multiplier? No

Spoiler alert - the factors are given below. . . . .

n= 6962155154859963260211100482357357666900094513013513488352858667799199787495340476167566639530574848375895722792291996203873323650274512138128403360943634134259376986501375967452208380337012919869885380406071772232795575963202558402893589313281327208179913789760736615950818685956393838601277519011418885197723428318400763080858914698836058070301404903262955501113318317950597435778777212408626799143
                                                                                          p= 1055314811678641606424788110765439117222699930257095408671007391029759113842109970448108699505224742945927781061767905202515184760446787611555372203775837301834490832771874109424228620164137709228509254318229660698954763303449460372503950485172061048411036447824270015301213488707
                                                                                          q= 6597230587321689827469274987496974524162638657985346941557775305494810601668451103917887716603988821282535336087463657549
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Indeed, straight Fermat won't cut it. I also tried a fair amount of Pollard's p-1 (ecm -pm1 4e9) and William's p+1 (ecm -pp1 2e9), to no avail, and some ECM. If ECM does not help, then Pollard's Rho won't. Perhaps this class of methods? Or/and using a multiplier? One way to convince people one has factored $n=pq$, without revealing the factorization, is to publish $t=2^{n^{-1}\bmod((p-1)(q-1))}\bmod n$. Then anyone can check that $t^n\bmod n=2$. $\endgroup$
    – fgrieu ♦
    Jul 12, 2021 at 14:20
  • $\begingroup$ Ah, got it. Should have looked at $n$ in hex or binary. Nice. $\endgroup$
    – fgrieu ♦
    Jul 12, 2021 at 15:59
  • $\begingroup$ Nice, @MostlyResults! Did you use the algorithm due to Coppersmith? ("Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities", J. Cryptology (1997) 10: 233–260) $\endgroup$
    – Sam Blake
    Jul 13, 2021 at 0:21
  • 1
    $\begingroup$ @Sam Blake: I guess MostlyResults guessed from the hex form of $n$ that $n=(r\,2^i+s)(t\,2^j+u)$ with small $(r,s,t,u)$. $\endgroup$
    – fgrieu ♦
    Jul 13, 2021 at 11:51
6
$\begingroup$

"Trivial" is almost certainly the wrong word for this. A better question is if it is reasonable to efficiently factor. First, it is worth mentioning that your semi-prime is 400 decimal digits. Multiplying this by $\log_2(10)$, we see that it is $\approx 1300$ bits long. This is vastly larger than the largest claimed factoring (of semiprimes) record of 829 bits. So the answer is "no", unless your semiprime has special structure that makes it "weak".

What special structure might semi-primes have? Let $N = p_1p_2$ be the factorization. There are a few candidates, which work if

  1. One of the $p_i$ is small (say at most $\approx 60$ bits), then the elliptic curve method is reasonable to run.

  2. One of the $p_i$ is such that $p_i+1$ is smooth, e.g. all prime factors of $p_i+1$ are bounded by some reasonably small number $B$. Then William's $p+1$ algorithm is reasonable.

  3. One of the $p_i$ is such that $p_i-1$ is powersmooth, e.g. all prime power factors of $p_i-1$ are bounded by some reasonably small number $B$. Then Pollard's $p-1$ algorithm is reasonable.

There may be a few other "special structures" that I am missing (I seem to remember one if $p_1\approx p_2$, but can't recall the name now). Your only real chance of factoring the number is for it to be improperly generated though, which all of the above would be examples of, so unless you have a specific reason to think they are improperly generated (say this is a CTF challenge) I wouldn't bother trying to break it.

If you have a reason to think this should be improperly generated, implementations of these exist. For example, Sage has an implementation of the ECM (via GMP-ECM). In the GMP-ECM page itself, I also see references to $p-1$ and $p+1$, but I don't know if sage directly tries these as well (as they are only really useful if you suspect the semiprimes have been improperly generated).

But without hitting one of these cases of "weak semiprimes" (which are exceedingly unlikely to occur if the semiprime is properly generated --- so unless you have reason to think this is a weak RSA semiprime it is probably not even worth checking).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ For whatever it's worth, Magma online calculator could not factor this. You are allowed 120 CPU seconds but I don't know what processor they use but their approach is described here: magma.maths.usyd.edu.au/magma/handbook/text/182 calculator: magma.maths.usyd.edu.au/calc $\endgroup$
    – kodlu
    Jul 11, 2021 at 4:30
  • $\begingroup$ Thank you, @Mark. I'm presently trying to factor p+1, p-1, q+1, q-1 to see if these primes satisfy any of these conditions. $\endgroup$
    – Sam Blake
    Jul 11, 2021 at 4:30
  • 2
    $\begingroup$ Actually, Elliptic Curve Method is fairly effective at finding primes smaller than 128 bits, and has a decent probability at finding primes somewhat larger than that... $\endgroup$
    – poncho
    Jul 11, 2021 at 11:36
  • $\begingroup$ And, for $p_1 \approx p_2$, Fermat's method finds the factors quickly... $\endgroup$
    – poncho
    Jul 12, 2021 at 12:46
2
$\begingroup$

The technique used was to reduce N to a special form that was easily factored.

Displayed N in binary and noticed hundreds of 0's in between 4 numbers.

This was reduced to the following:

N = a2^1228+b2^875+c*2^353+d

where a= 1506291488774150974626762365373 b= 322571915263178581 c= 576377099039115423 d= 123431

Treating this as a polynomial in x, with x=2:

N = ax^1228+bx^875+c*x^353+d

This factors very quickly to:

(359561509069941x^353+77)(4189245652768553*x^875 + 1603)

Improve this answer
$\endgroup$
2
  • $\begingroup$ To answer your question (that was edited out). I put the example together myself as a test for some integer factorisation experiments I have been doing. Here's a slightly more challenging one: 7215955072690155355400859323297730634528493510676300043022948136348249037517276095868127042993906604904230826475281383188764473510881994780947137238252071087749294743150564851420395422525735221770067605216401023 $\endgroup$
    – Sam Blake
    Jul 13, 2021 at 13:42
  • $\begingroup$ Many years ago I encountered a 124 bit key (yes, many years ago) of the form 2^123 + a x 2^60 + b for small an and b. Factored it by hand. The primes were apparently taken from a table in TAOCP. $\endgroup$
    – gnasher729
    Oct 15, 2022 at 10:53
2
$\begingroup$

In a comment @Sam Blake asked a follow up question about an integer to factor:

7215955072690155355400859323297730634528493510676300043022948136348249037517276095868127042993906604904230826475281383188764473510881994780947137238252071087749294743150564851420395422525735221770067605216401023

The question is this 2nd semiprime actually trivial to factor into primes?

This semiprime is not weak because it does not give up its' special form very easily.

It is weak for an adversary with nation state capability because it is only 701 bits. A 2048 bit or higher modulus with equal bitlength p and q are recommended.

Also it doesn't appear to have weakness using Fermat's, p-1, it's ratio is not near a small fraction, ECM is not helpful.

This integer does not appear to match a special form that is easy to factor. Even though once the special form is recognized the number can be factored with much less effort, detecting which special form can be very time consuming as there are many forms.

What hints are you willing to give? That this is a semiprime? That the factors are of unequal length? That the factors are polynomials with terms: a0 x 2^(k0) + a1 x 2^(k1) + a2 x 2^(k2)...

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hey @MostlyResults, it is a semiprime with a 293-bit prime factor. $\endgroup$
    – Sam Blake
    Aug 7, 2021 at 2:00
  • $\begingroup$ Here's an algorithm that factors the examples quickly: github.com/stblake/factor_rational_base $\endgroup$
    – Sam Blake
    Sep 16, 2022 at 4:08
  • 1
    $\begingroup$ @SamBlake This was an interesting problem at first. Wrote a Pari/GP program to find the special form of the semiprime 72159...01023 It only took 23 seconds on one core to find the special form: round((49/9)^167)+2857 The two factors followed: 80213...08313 and 89959...71671 $\endgroup$
    – MostlyResults
    Dec 17, 2022 at 14:23
  • $\begingroup$ Nice work @MostlyResults! Now it would be nice if there was a clever way to (simultaneously) eliminate many candidate rational bases. And/or some sort of gradient descent-based way to converge on 49/9, perhaps through analysis of the base a/b representation of N? If I had a clever way to do it I wouldn't be posting here though... $\endgroup$
    – Sam Blake
    Dec 19, 2022 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.