Talk:Fermat's factorization method: Difference between revisions

Revision as of 16:54, 7 December 2012

Latest revision as of 19:35, 1 February 2024

(7 intermediate revisions by 5 users not shown)

Line 1:

{{User:MiszaBot/config

{{maths rating|class=Start|priority=Low|field=number theory}}

| algo = old(365d)

| archive = Talk:Fermat's factorization method/Archive %(counter)d

| counter = 1

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-->

| maxarchivesize = 150K

| archiveheader = {{Automatic archive navigator}}

| minthreadstoarchive = 1

The whole article is unclear...

| minthreadsleft = 2

10:55, 6 September 2008 (UTC)

}}

{{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 ==

Line 13 ⟶ 18:

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 26 ⟶ 32:

== 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 53 ⟶ 58:

√1751₁₆ = 4E, so we test for '''a''' only 4F, 51, 57 and get result '''a² - N = 57₁₆² - 1751₁₆''' 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)