Content deleted Content added
Yourskadhir (talk | contribs) No edit summary |
m Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Maths rating}}. Remove 1 deprecated parameter: field. Tag: |
||
| (10 intermediate revisions by 7 users not shown) | |||
Line 1:
{{User:MiszaBot/config
| algo = old(365d)
| archive = Talk:Fermat's factorization method/Archive %(counter)d
| counter = 1
| maxarchivesize = 150K
| archiveheader = {{Automatic archive navigator}}
| minthreadstoarchive = 1
| minthreadsleft = 2
}}
{{WikiProject banner shell|class=Start|
{{WikiProject Mathematics|priority=Low}}
}}
{{Archive box |search=yes |bot=Lowercase sigmabot III |age=12 |units=months |auto=yes }}
== 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.
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
Case2: If 'n' is even & m = n/2 is odd then p should be (m(m -2) + 2) and q should be (m(m + 2) + 2)
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▼
▲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
Example1. let d = 2x9 here n = 9 is odd then 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.
Line 22 ⟶ 29:
Conclusion:
Hence irrespective of the difference 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.
== Mod 16 optimization ==
Need to mention that the optimization section needs some remarks, there are more variants of '''a'''.<br>
For each '''N mod 16''', the '''a mod 16''' must be as follows:<br>
Line 52 ⟶ 58:
√1751<sub>16</sub> = 4E, so we test for '''a''' only 4F, 51, 57 and get result '''a² - N = 57<sub>16</sub><sup>2</sup> - 1751<sub>16</sub>''' as a perfect square. <br><br>
Is this better than in the article? Got it clear now? Should this be in the article page?
--[[User:Neeme Vaino|Neeme Vaino]] ([[User talk:Neeme Vaino|talk]]) 20:20, 2 April 2010 (UTC)
:The sieve section should mention that you can combine the results of the sieve operations using a variant of Euclid's algorithm.▼
:Thus, using the given example '''N = 2345678917''', we have '''N = 5 (mod 16)''' which requires '''a = ±3 (mod 8)''' so as to give '''b^2 = 4 (mod 16)''' which is the only possible value for '''a''' which leaves '''b^2 = a^2 - N''' as a possible square. Similarly '''N = 7 (mod 9)''' forces '''a = ±4 (mod 9)''' in order for '''b^2''' to be a possible square. Combining '''a = ±3 (mod 8)''' with '''a = ±4 (mod 9)''' gives '''a = ±5 or ±13 (mod 72)'''. ▼
▲The sieve section should mention that you can combine the results of the sieve operations using a variant of Euclid's algorithm.
:Now we note that '''N = 2 (mod 5)''' which forces '''a = ±1 (mod 5)''', and we can combine this result with the previous results to leave '''a = ±{59, 131, 139 or 149} (mod 360)'''.▼
▲Thus, using the given example '''N = 2345678917''', we have '''N = 5 (mod 16)''' which requires '''a = ±3 (mod 8)''' so as to give '''b^2 = 4 (mod 16)''' which is the only possible value for '''a''' which leaves '''b^2 = a^2 - N''' as a possible square. Similarly '''N = 7 (mod 9)''' forces '''a = ±4 (mod 9)''' in order for '''b^2''' to be a possible square. Combining '''a = ±3 (mod 8)''' with '''a = ±4 (mod 9)''' gives '''a = ±5 or ±13 (mod 72)'''.
:So, after considering only the primes 2, 3 and 5, we see that there are only 8 possible values for '''a''' in each period of 360 integers. We can add in further conditions, to increase the acceleration further.▼
▲Now we note that '''N = 2 (mod 5)''' which forces '''a = ±1 (mod 5)''', and we can combine this result with the previous results to leave '''a = ±{59, 131, 139 or 149} (mod 360)'''.
:[[Special:Contributions/62.253.20.134|62.253.20.134]] ([[User talk:62.253.20.134|talk]]) 03:09, 16 July 2012 (UTC)▼
▲So, after considering only the primes 2, 3 and 5, we see that there are only 8 possible values for '''a''' in each period of 360 integers. We can add in further conditions, to increase the acceleration further.
:::Not sure how to write stuff in Wikipedia properly, but I noticed a mistake and this is probably where I should point it out: <br>
▲[[Special:Contributions/62.253.20.134|62.253.20.134]] ([[User talk:62.253.20.134|talk]]) 03:09, 16 July 2012 (UTC)
:::"A multiple of four is also a difference of squares: let c and d be even" in the first paragraph is wrong. for example, 8 is a multiple of four (and indeed, a difference of squares), but not a difference of even squares. It is 9-1. The mistake in the argument is that if they are even then you divide the whole equation by 4, and you need to show n/4 is a difference of squares, which it doesn't have to be (8/4=2 isn't a difference of squares) [[Special:Contributions/109.64.51.240|109.64.51.240]] ([[User talk:109.64.51.240|talk]]) 15:58, 9 July 2015 (UTC)
| |||