2
$\begingroup$

Let $W$ be a random $200$ bit number. How much work would it take to find a semiprime $n=p_1\cdot p_2$ such that $p_1,p_2 > 2^{50} $ and $|W-n|<2^{12}$?

More generally, let $W_b$ be a random integer with $b$ bits. How much work would it take to find a semiprime $n=p_1\cdot p_2$ such that $p_1,p_2 > \sqrt[4]{W_b} $ and $|W_b-n|<\sqrt[8]{W_b}$?

$\endgroup$
4
  • $\begingroup$ With numbers I always have to question if it is in the range $\big[0, 2^n\big)$ or $\big[2^{n-1}, 2^n\big)$ $\endgroup$
    – Maarten Bodewes
    Dec 27 '21 at 22:10
  • 1
    $\begingroup$ @MaartenBodewes, a $200$ bit integer implies that the bit at position $200$ is set to $1$; indexing the first bit at $1$, not $0$. So, the latter. $\endgroup$
    – factorn
    Dec 27 '21 at 22:22
  • $\begingroup$ At the end I presume that $|W_b-n|<\root 8\of n$ is meant as $2^{\root 8\of n}$ is much, much larger than $n$ as $n$ grows. $\endgroup$
    – Daniel S
    Dec 28 '21 at 10:32
  • $\begingroup$ @DanielS Yes, thank you! $\endgroup$
    – factorn
    Dec 28 '21 at 14:02
1
$\begingroup$

The best method to find such numbers that I know of would be Algorithm 3 from Marc Joye's paper RSA Moduli with a Predetermined Portion: Techniques and Applications. In this case, taking $n=200$, $n_0=150$ and $\kappa'=188$. The initial problem requirements are aggressive and it is very possible that there are 200-bit values of $W$ for which no suitable semi-prime exists in that interval. Joye's investigation examined the complexity of the method only in an experimental manner. I will read up and try to come up with an heuristic.

It is straightforward to describe and heuristically analyse the "folklore" method of choosing a 50-bit $p$, setting $q_0=\lceil W/p\rceil$ and testing $q_0$ for primality. It should take about 105 different choices of $p$ to find a prime $q$ of 150-bits. For this pair the top 150 bits will match $W$ and with probability around $2^{-38}$ the top 188 bits will match. This gives an overall work budget of 44-45 bits of primality tests. Joye's method will certainly improve on this, but the analysis will be lengthier.

For the general question with $q\approx\root 4\of n$ and interval length $\root 8\of n$, we would expect around $\frac14\root 8\of n\log n$ primality tests of numbers around $\root 4\of n$ in size for the folklore method, but again Joye should improve on this.

$\endgroup$
1
  • $\begingroup$ Thank you! Very helpful. 1) How do you figure about 1/35 primes on a prime of 50 digits will do it? 2) Where does the $43-44$ bits of work for primality testing come from? 3) Could you parametrize that formula for size of $q$, say bits in $q$, and interval lenght, say $\gamma$? $\endgroup$
    – factorn
    Dec 28 '21 at 16:18
0
$\begingroup$

If you use existing factoring functions this can be solved in minutes for 200 bit random numbers. Factoring functions from Pari/GP for example.

The algorithm below is not just factoring consecutive numbers. See below.

Here is the general algorithm which has been converted into a working program:

Generate W, a random 200 bit number

sievelimit = 250 primelimit = 2000000

precompute pr = product of first primelimit primes

For n1 = W+1 to W+sievelimit

If n1 is of the form 6k+1 or 6k+5

 if  gcd(n1,pr) is 1

   f = factor(n1)

      if number of factors of n1 is 2 and both >2^50   
          print Solution f  

Loop

The line:

if gcd(n1,pr) is 1

is a quick way to skip numbers which have prime factors below the 2 millionth prime.

The precompute pr step is optimized in Pari/GP and only takes 7.785 seconds on slow hardware.

For the worst case 200 bit number the factor function in Pari/GP uses MPQS method and takes less than 30 seconds on old hardware.

Here is a random 200 bit number W: 1567470448908230034126591070540826459978233372650796513704199

The program only factors one number W+10 and finds the solution

p1 = 5346955435967300929
p2 = 293151956787285973328498761492202409914321  

p1 is 63 bits, p2 is 138 bits, n = p1*p2

|W-n| = 10, |W-n|< 2^12

$\endgroup$
2
  • $\begingroup$ I am already aware of this. Also, you have not addressed my question at all. $\endgroup$
    – factorn
    Dec 29 '21 at 9:08
  • $\begingroup$ The first question was answered in general (minutes). It appears that you wanted number of operations(add,subtract, multiply or check primality) or O() notation or L() notation. This can be determined from the algorithm above. Since this appears to be a homework question, maybe next week I'll have time $\endgroup$ Dec 29 '21 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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