Content deleted Content added
m Reverted edits by 171.78.187.90 (talk) to last version by 109.64.51.240 |
Miscellaneous clean-up. |
||
Line 1:
{{maths rating|class=Start|priority=Low|field=number theory}}
== Unclear paragraph ==
The 1st paragraph under sieve imrovements is very unclear. I assume some of these restrictions come about because of the value of N mod 20 etc? This should be explained. This paragraph needs to be expanded with a better step-by-step explanation. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/210.84.56.174|210.84.56.174]] ([[User talk:210.84.56.174|talk]]) 02:52, 21 November 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:The whole article is unclear... [[Special:Contributions/
== Fermat's Factorization Running Time ==
Line 17 ⟶ 15:
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 28 ⟶ 25:
== 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 55 ⟶ 51:
√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.
▲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)'''.
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)'''.▼
▲: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)'''.
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.▼
▲: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.
▲[[Special:Contributions/62.253.20.134|62.253.20.134]] ([[User talk:62.253.20.134|talk]]) 03:09, 16 July 2012 (UTC)
:[[Special:Contributions/62.253.20.134|62.253.20.134]] ([[User talk:62.253.20.134|talk]]) 03:09, 16 July 2012 (UTC)
:::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>
:::"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)
| |||