Talk:Fermat's factorization method: Difference between revisions

Revision as of 05:37, 12 August 2019

Revision as of 05:51, 12 August 2019

Line 9:

== Fermat's Factorization Running Time ==

Let N = pq is any odd composite. Let N = a^2 - b^2 is the required Fermat factorization. Let d = 2n be the difference between the two closest factors of 'N'. Let 's' is the floor value of square root of N.

Let N = pq

In order to attain best case scenario a - s <= 2 following are the minimum required factors of N. I call these factors as Best Fermat Factors.

Case1: If 'n' is odd then p should be (n(n-4) + 7)/4 and q should be (n(n+4) + 7)/4

Line 17 ⟶ 18:

Case3: If 'n' is even & m = n/2 is also even then p should be (m - 1)^2 and q should be (m + 1)^2

So that N can be easily factorizable using Fermat Factorization method. i.e., Best Case Scenario.

Example1. let d = 2x9 here n = 9 is odd then case1: p = (9x5 + 7)/4 = 13 & q = (9x13 + 7)/4 = 31 Therefore N = 13x31 = 403 = 22^2 - 9^2 and floor value of sqare root of 403 is 20, here a = 22 & s = 20 and a -s = 2. N Can be easily factorable in just 2 operations. i.e., Best Case Scenario.

Note:

Line 25:

Conclusion:

Hence irrespective of the difference between factors there exist Best Fermat Factors, so that factorization complexity is easy. The logic that odd composite with least difference will be factored easily and large difference would factored hardly is wrong. Hardness is depends upon the how much the factors are deviated from the Best Fermat Factors. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Yourskadhir|Yourskadhir]] ([[User talk:Yourskadhir|talk]] • [[Special:Contributions/Yourskadhir|contribs]]) 01:15, 2 December 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Mod 16 optimization ==