Talk:Fermat's factorization method: Difference between revisions

Revision as of 01:42, 9 February 2010

Revision as of 20:20, 2 April 2010

Line 7:

The whole article is unclear...

10:55, 6 September 2008 (UTC)

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

{| class="wikitable"

|-

! N mod 16

! variants of a mod 16

|-

| 1 or D

| 8±4±3 = { 1,7,9,F }

|-

| 3 or B

| 8±4±2 = { 2,6,A,E }

|-

| 5 or 9

| 8±4±1 = { 3,5,B,D }

|-

| 7 or F

| 6±4±2 = { 0,4,8,C }

|}

-in order for '''a² - N''' to be square.<br>

As you can notice, all even '''N''' are skipped - Fermat method does not test them.<br>

Example in hexadecimal format: <br>Let '''N''' be 1751₁₆.<br>

The right digit of '''N''' is 1, from table, right digit of '''a''' can only be 1,7,9 or F.<br>

So we test for '''a''' only 4F, 51, 57 and get result '''a² - N = 57₁₆² - 1751₁₆''' as a perfect square.

--[[User:Neeme Vaino|Neeme Vaino]] ([[User talk:Neeme Vaino|talk]]) 20:20, 2 April 2010 (UTC)