mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Best case Fermat Factors (https://www.mersenneforum.org/showthread.php?t=17553)

Best case Fermat Factors

The logic that it is hard to do Fermat factorization for odd composite which is a product of two large prime factors with big difference is wrong. Reason when those primes are best Fermat factors then Fermat factorization will be very easy. For more details please follow the link [URL="http://kadinumberprops.blogspot.in"]http://kadinumberprops.blogspot.in[/URL]

 Batalov 2012-12-11 07:51

Then it would be no problem for you to factor [CODE]4872694181406339617512781250710256288128420426749870494701352170485888238522036701839697408990043865362740060996930806408048841117542674271031589079075642908938171217283398153697602454775549091739003927335892645964656077739143953748851155087308230066486278985637829660170144978240247037951 ?[/CODE]?

 akruppa 2012-12-11 09:45

Straight to Misc. Math.

Please understand i didn't mean it. Please understand i gave the fresh analysis of Fermat factorization and i coined the term Best Fermat factor. Please reply whether you understood the article thoroughly. I said Fermat factorization complexity is easy when the number's factors are Best Fermat factors or Nearer to Best Fermat factors.

 science_man_88 2012-12-11 18:39

[QUOTE=Batalov;321280]Then it would be no problem for you to factor [CODE]4872694181406339617512781250710256288128420426749870494701352170485888238522036701839697408990043865362740060996930806408048841117542674271031589079075642908938171217283398153697602454775549091739003927335892645964656077739143953748851155087308230066486278985637829660170144978240247037951 ?[/CODE]?[/QUOTE]

here's what I got from reading it:

N=a^2-b^2 ~ s^2
d=2n

so say y is the lower factor in a 2 best factor setup y+2n is the other to go along with it y*(y+2n) = y^2+2ny~s^2 this leads to s^2-y^2 ~ 2ny since both y^2 and 2ny have a common factor y, so do ~s^2 and y^2 namely y so in closing the lowest of the 2 has a multiple close to the sqrt of the N to be factored. of course how close depends on the amount of rounding I think.

edit: ~ is for approximately.

 LaurV 2012-12-12 04:18

That is too heavy! :razz:
Next number is a C170, whose two prime factors ratio is very close to "best fermat factor" ratio, the distance to such a split is lower than 1/10^40 (i.e. 0.000(about35zeroes)0001). There should be no problem to factor it, and if this is possible, it should be nice, because there is no other method (beside long taking gnfs) to factor it: both factors are P-1 and ECM "tough" - I did not make them so on pupose, they just come out like that from the first trial of nextprime(random(perfectsplit)), hehe. So, it should resist p-1 and ECM trials. You only have to try the other primes in the ~10^30 interval that remained.

[CODE]54553746256351348704340853049775196132111315873148539674440243786571807634659955885688337948063058916001903005889468533003195598599269527286081791979809069615167325135781
[/CODE]

 All times are UTC. The time now is 09:24.