Rating: 4.3

In this we had to factorize

n = 2462649746477364143454082050368305440553491900304388646893610847386194301369924385009730987303651345060031438478297733694036327257723431468649220444397635127530301992505638291521092898714917678389314956983918603221732358628680256253537449204312287724750669208856634711056863315465220853759428826555838536733


Admins released the hint that the primes are close by, so I tried fermat factorization.
Since standard implementations are pretty slow, I found that yafu has a pretty optimized version with sieve improvement. But yafu was returning 1 as the primes, so I compiled it again and debugged to see the problem.
Yafu was crashing after found: in trialdiv.c
Code:


found:

if ((mpz_size(b2) > 0) && mpz_perfect_square_p(b2))
{
printf("found square at count = %d: a = %s, b2 = %s",count,
z2decstr(&a,&gstr1),z2decstr(&b2,&gstr2));


So instead of finding the problem I basically copied the value of count using gdb and used the below py script to get the factors:


count = 26365624027328
a = gmpy.sqrt(self.n) + count
max = a + self.limit
b2 = a*a - self.n
b = gmpy.sqrt(b2)
p = a+b
q = a-b
print p, q

Finally the primes

1569283195117237003369661884198411787798228566690474267312882038063658385761773122348822031628496668092176832507661463177730984959212118435829588059735623L
1569283195117237003369661884198411787798228566690474267312882038063657810434869771811957721834374075850363708418225687871888930709588875800968904667752571L


grocidSept. 15, 2017, 11:15 p.m.

Whoa, I was quite surprised to see a factoring solution of the challenge. Nice job :-) Anyways, intended solution is here https://grocid.net/2017/09/16/finding-close-prime-factorizations/