1
$\begingroup$

We got a probabilistic integer factorization algorithm and experimental evidence with large integers given bounds for one factor.

Let $D \ge 2$ be real number and let $p,q$ be primes and $N=pq$. Assume $\log{q} \sim D\log{p}$.

Let $B_1,B_2$ be real numbers such that $B_1 < q < B_2$ and $B_2 - B_1 < C q^\frac{D-1}{D}$ for an absolute constant $C$.

Given $N,D,B_1,B_2$ our algorithm experimentally finds the factor $q$ efficiently with complexity $O(\log N)$.

The algorithm may fail, but according to our tests it fails rarely.

Q1 Is this result known?

Q2 Given $N,D$ what is the best complexity to find $B_1,B_2$, possibly assuming some properties of $q$?

Since there is only one partial answer, me and Stefcho Guninski released a preprint and sagemath source code that may run in a browser

For real $x$ and natural $N$, define $J(x,N)=\sin{\frac{\pi N}{x}}$.

The real zeros of $J$ are $\frac{N}{a}$ for integer $a$.

The integer zeros of $J$ are the divisors of $N$.

For small $x$, the real zeros are very dense, but in some cases we can find interval which contains only one zero, which is integer.

To illustrate, take $N=5*37$ and examine the plot $x \in (1,N)$:

enter image description here

To illustrate a good interval, take $N=5*37$ and examine the plot $x \in (37-\sqrt{37},37+\sqrt{37})$ and observe that it contains only one real zero, which is the integer factor $37$.

enter image description here

For real constant $D \ge 2$ and $N=pq$ with $\log{q} \approx D \log{p}$ and given bounds $B_1 < q < B_2$ and $ 0 < q-B_1,B_2-q < q^{\frac{D-1}{D}}$ we find the factor $q$ in time polynomial in $\log{N}$ using real root finding of the function $J(x,N)=\sin{\frac{\pi N}{x}}$

To find the unique zero, we use mpmath's function |mpmath.findroot(J,B_1,B_2)| Experimentally it finds the zero efficiently using real root

To our surprise, for $p \sim 2^{400},D=4$, generating the primes $p,q$ in $5.6$ seconds and the root finding took only $27$ms.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Please expand on the word, "efficiently". $\endgroup$
    – Gerry Myerson
    Commented Dec 7 at 22:50
  • $\begingroup$ May I send you a challenge factorisation? $\endgroup$
    – Aurel
    Commented Dec 8 at 13:21
  • 1
    $\begingroup$ Doesn't the Elliptic Curve Method scale with the size of the smaller factor? It would still be super-polynomial but might make a good practical point of comparison. $\endgroup$
    – Bill Bradley
    Commented Dec 8 at 13:21
  • $\begingroup$ @Aurel Sure, send me a few challenges, my email is on my profile page. $\endgroup$
    – joro
    Commented Dec 8 at 13:37
  • $\begingroup$ @BillBradley I don't see the relation with elliptic curves and my bound is different than the Hasse bound. $\endgroup$
    – joro
    Commented Dec 8 at 13:39

1 Answer 1

Reset to default
4
$\begingroup$

If $D\le 3$, it is known how to do this in polynomial time by Coppersmith's algorithm [Cop96]: note that $q \approx N^{\frac{D}{D+1}}$ and therefore $B_2-B_1 \approx q^{\frac{D-1}{D}} \approx N^{\frac{D-1}{D+1}}$, so you known $\approx \frac{1}{D+1}\log_2 N$ bits of $q$.

[Cop96] D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, EUROCRYPT 96. ZbMath

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. I don't understand your answer. Set D=3, L=q^(2/3). If you multiply integer by irrational, you are losing bits. How do you find the bits given B_1=q - sqrt(2)*L, B_2=q+sqrt(3)*L? What if you are given other similar pairs of B_1,B_2?In addition you can get L smaller, say L=q^(1/3), and you don't have equality but inequality. $\endgroup$
    – joro
    Commented 2 days ago
  • $\begingroup$ @joro Having an interval containing an integer is equivalent to knowing its highest bits. The interval being non-rational does not matter, you can round it to a narrower interval with integer endpoints. $\endgroup$
    – Aurel
    Commented 2 days ago
  • $\begingroup$ Thanks. Sorry but I still fail to understand how many highest bits a range of M integers defines. If you accept challenges and I give you different pairs of B_1,B_2 will you still get the same highest bits? $\endgroup$
    – joro
    Commented 2 days ago
  • $\begingroup$ @joro Think about what the set of integers with $a$ fixed bits followed by $b$ unspecified bits is. That's the integer interval $[A2^b,A2^b+2^b-1]$, were $A$ is a number with $a$ bits. So knowing the highest $a$ bits of an $a+b$ bits number is equivalent to locating it in an interval of this form. In any case, you should read Coppersmith's article: the number of bits is simply the motto, but you will see that the proofs are in terms of knowing an interval containing the the factor to be found. $\endgroup$
    – Aurel
    Commented 2 days ago
  • $\begingroup$ Thanks. I edited adding a preprint, sagemath code and experimental data. Hope you improve the algorithm. $\endgroup$
    – joro
    Commented yesterday

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .