Let *s = sqrt(pq)*. Assume *p ≤ q*.

Starting from *s*, find the smallest prime *k ≥ s*.

Since *q – p* is small, *q – s* is small also. So *pk* is close to *pq*, i.e. *pq – pk* is small.

Starting from *pq*, since *k* is prime, exactly one *n* ∈ *{a, a + 1, a + 2, …, a + k – 1 = pq}* is not coprime with *k*. Using the method found here, * n = a + (-a mod k) *.

Let *d = gcd(n, pq)*. If *d > 1* then *d = p*. Otherwise choose the next *k* consecutive numbers less than *a* and repeat.

Runnable code in the Frink language:

p = 96436875510168134260978951531720215975911176926194651907111357743104310827706384687021784900521146900897417521181 q = 96436875510168134260978951531720215975911176926194651907111357743104310827706384687021784900521146900897417697981 if isPrime[p] println["p is prime"] if isPrime[q] println["q is prime"] println["prime difference:"] println[q - p] mysqrt[n] := { b = bitLength[n] m = 0 i = ceil[b/2] - 1 while i >= 0 { if (m+2^i)^2 <= n m = m + 2^i i = i - 1 } return m } pq = p * q s = mysqrt[pq] if s^2 <= pq && (s+1)^2 > pq println["sqrt function works"] else println["wtf"] k = nextPrime[s - 1] println["prime between q and s:"] println[k] println["prime, sqrt difference:"] println[k - s] i = pq - k + 1 do { n = i + (-i % k) d = gcd[n,pq] if d > 1 { println["good"] break } i = i - k } while i >= s

Advertisements