stanford-oval/wikipedia huggingface dataset:
ขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มของแฟร์มาต์
วิธีการเบื้องต้น > หลักการเบื้องต้น

หลักการคือต้องการแยกตัวประกอบของ N ซึ่ง N ควรเป็นจำนวนคี่ถ้าหากเป็นจำนวนคู่สามารถแยกตัวประกอบ 2 ออกไปก่อน จากนั้นหาตัวประกอบโดยหาค่า a และ b ที่เป็นจำนวนเต็มน้อยที่สุดที่  a-b\leq {\sqrt {N}}\leq a+b โดยที่  a-b=N/(a+b)\  และถ้าแยกตัวประกอบได้ N=N*1 จะได้ว่า N เป็นจำนวนเฉพาะ โดยทดสอบทีละเงื่อนไขและบวกค่า a เพิ่มขึ้นเรื่อย ๆ จนพบคำตอบที่ได้ตัวประกอบลู่เข้ารากของ N มากที่สุด ตัวอย่างเช่น N=5959
วิธีการเบื้องต้น > ขั้นตอนตัวอย่าง

เริ่มต้นโดยหา  a=\lceil {\sqrt {5959}}\rceil =78 จะได้ b2 = 125
ตรวจสอบ b2 ว่าสามารถหารากได้เป็นจำนวนเต็มหรือไม่ เนื่องจาก b2 = 125 หารากได้ประมาณ 11.18 ไม่ใช่จำนวนเต็มจึงเพิ่มค่า a เป็น 79 แล้วหาต่อได้  b2=79^{2}-5959=282 แล้วทำซ้ำขั้นตอนที่ 2 อีกรอบจนกว่าจะสามารถหารากได้เป็นจำนวนเต็มให้ไปทำขั้นตอนที่ 3
เมื่อทำมา 3 ครั้งจะได้ a=80 และ b2 = 441 ซึ่งสามารถหารากได้ 21 ดังนั้นจะได้ว่า  a-b=59, and  a+b=101 ซึ่ง ได้ 59 และ 101 เป็นตัวประกอบของ 5959
ประสิทธิภาพ

เมื่อให้  N=cd จะได้ว่าจำนวนครั้งในการวนลูปคือ  (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c ของกรณีที่แย่ที่สุดคือเมื่อ N เป็นจำนวนเฉพาะ ซึ่งจะได้ประสิทธิภาพการทำงานเป็น  O(N) แต่ถ้ากรณีที่ c ต่างกับ รากของ N น้อยกว่า  {\left(4N\right)}^{1/4} ถ้าใช้จำนวนการทำงานแค่ครั้งเดียว หรือถ้าคำตอบจริงยิ่งเข้าไป รากของ N มากเท่าไหร่ประสิทธิภาพในทางปฏิบัติก็จะดีขึ้น ซึ่งจากทั้งหมดแสดงให้เห็นว่าประสิทธิภาพของวิธีแยกตัวประกอบของแฟร์มาต์จะขึ้นอยู่กับค่าของ N
การประยุกต์วิธีของแฟร์มาต์กับการหารเชิงทดลอง

จากวิธีของแฟร์มาต์จะเห็นว่าได้ประสิทธิภาพคือ  O(N) เมื่อเทียบกับ วิธีการหารเชิงทดลองที่ได้ประสิทธิภาพที่ดีกว่าคือ O(√n / log n) ซึ่งจะเห็น ดังนั้น เราสามารถเพิ่มประสิทธิภาพให้กับ วิธีการหาตัวประกอบทั้งสองให้ดีขึ้นได้โดยนำทั้งสองวิธีมารวมกันโดยใช้วิธีการหาตัวประกอบของแฟร์มาต์เป็นหลัก และใช้วิธีการหารเชิงทดลองตัดกรณีที่ใช้พิจารณามาก ๆ ได้ จาก
ทฤษฏีการหารเชิงทดลอง ตัวประกอบที่เป็นจำนวนเฉพาะของจำนวนเต็มใด ๆ จะมีค่าน้อยกว่าหรือเท่ากับรากที่สองของจำนวนเต็มนั้น
จากตัวอย่างให้ N=123456789123 ใช้วิธีการแยกตัวประกอบของแฟร์มาต์ ได้ดังนี้
จริง ๆ แล้วจะเห็นว่าเราทำมาได้ 4 ขั้นตอนแล้วแต่ยังไม่ได้ตัวประกอบเพราะว่า b2=1637.77 ไม่ใช่จำนวนเต็มแต่เมื่อเราคำนวณ a-b2 จะได้ว่า 357368-1638=349730 ถ้าอาศัยทฤษฎีของการหารเชิงทดลองจะได้ว่าการที่จะหาตัวประกอบเฉพาะของ N ทำได้จากการทดลองหาจาก 0 ถึง 351365 (จาก การหารเชิงทดลอง) แต่กรณีนี้หลังจากที่เราทำการแยกตัวประกอบของแฟร์มาต์ยังไม่เสร็จแต่เราจะได้ว่า เราทำหาการหารเชิงทดลองโดยหาแค่จาก 0 ถึง 349730 พอซึ่งสามารถลดจากเดิมได้เป็นพันรอบโดยแค่ทำการหาตัวประกอบแบบแฟร์มาต์แค่ 4 รอบก่อน ซึ่งจากตัวอย่างด้านบนจะเห็นว่าสามารถหาค่าแล้วได้ b2 ออกมาเรื่อย ๆ ทำให้ยิ่งเข้าใกล้ค่าตัวประกอบจริงมากขึ้นและยิ่งทำให้เมื่อนำไปหาการหารเชิงทดลองต่อมีแนวโน้มที่จะได้ประสิทธิภาพที่ดีขึ้น
ดังนั้น จึงสามารถเขียนในรูปของความสัมพันธ์ทั่วไป ถ้าเราให้  d>{\sqrt {N}} จะได้ว่าถ้าเราใช้ การแยกตัวประกอบของแฟร์มาต์ในช่วงระหว่าง  {\sqrt {N}} กับ  d\  จะทำให้ได้ขอบเขตของการหาในวิธีการหารเชิงทดลองคือ  d-{\sqrt {d^{2}-N}} ตัวอย่างเช่นถ้า N=2345678917 โดยให้ d=48436 จะได้ขอบเขตของการหารเชิงทดลองคือ 47830 และถ้ากำหนดให้ d=55000 จะได้ขอบเขตคือ 28937
การปรับปรุงกับตะแกรง

บ้างครั้งเราไม่มีความจำเป็นที่จะต้องหา รากที่สองของ  a^{2}-N หรือแม้แต่ค่าของ a ทุกค่าเราสามารถพิจารณาได้จากค่า มอดุโล ของมันเช่นจากตัวอย่าง
| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| a: | 48433 | 48434 | 48435 | 48436 |
| b2: | 76572 | 173439 | 270308 | 367179 |
| b: | 276.7 | 416.5 | 519.9 | 605.9 |
กรณีดังกล่าวจะเห็นได้ว่าไม่มีค่า b หรือรากที่สองของ b2 เป็นจำนวนเต็ม จากสมการ  a^{2}-N เมื่อพิจารณาค่า  a^{2}เมื่อ a เป็นจำนวนเต็ม จากตัวอย่างดังนี้
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|  n^{2} | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | 121 | 144 | 169 | 196 | 225 | 256 | 289 | 324 | 361 | 400 |
จะเห็นได้ว่ากำลังสองของเลขจำนวนเต็มมักจะลงท้ายด้วย 0, 1, 4, 5, 9, 16 modulo 20 จากตารางด้านบนจะพบว่าค่าที่ a mod 10 มีค่าเดียวกันยกจำลังสองแล้วจะได้เลขลงท้ายค่าเดียวกันเท่ากันด้วย หรือจะเรียกได้ว่าจะซ้ำรอบเดิมเมื่อ a ถูกเพิ่มเป็น 10 จากตัวอย่างดังกล่าวจะได้ว่าถ้าเราเพิ่ม -17 mod 20 (3),  a^{2}-N จะได้เลขลงท้ายดังกล่าวออกมาเป็น 3, 4, 7, 8, 12, 19 modulo 20 จะเห็นว่ามี 4 จากรายการนี้ที่สามารถเป็นกำลังสองได้ (เทียบอันดับกันของ  a^{2} และ  a^{2}-N) ดังนั้น  a^{2} ต้องเป็น 1 mod 20 หรือหมายถึง a คือ 1, 9 mod 10 ซึ่งจะทำให้ b2 ลง ท้ายด้วย 4 mod 20 และ ถ้าเป็นกำลังสองอีก b จะลงท้ายด้วย 2, 8 mod 10
ตัวอย่างของการใช้ มอดุลัส ค่าต่าง ของ N=2345678917
| 0 | 1 | 2 |
| --- | --- | --- |
| มอดุโล 16: | กำลังสองคือ | 0, 1, 4, or 9 |
|  | N mod 16 is | 5 |
|  | ดังนั้น  a^{2} สามารถเป็นได้คือ  | 9 |
|  | และ  a ต้องเป็น  | 3 , 5 modulo 16 |
| มอดุโล 9: | กำลังสองคือ | 0, 1, 4, or 7 |
|  | N mod 9 is | 7 |
|  | ดังนั้น  a^{2}สามารถเป็นได้คือ | 7 |
|  | และ  a ต้องเป็น | 4 , 5 modulo 9 |
โดยทั่วไปจะเลือกค่าที่เป็นกำลังของจำนวนเฉพาะที่แตกต่างกันสำหรับ มอดุลัส
เมื่อให้ลำดับของ a-value(start,end,and step) และค่าค่า modulus ซึ่งจะมีกระบวนการได้ ดังนี้
การปรับปรุงกับตะแกรง > รหัสเทียม

FermatSieve(N, astart, aend, astep, modulus)
  a ← astart
  do modulus times:
  b2 ← a*a - N
  if b2 is a square, modulo modulus:
  FermatSieve(N, a, aend, astep * modulus, NextModulus)
  endif
  a ← a + astep
  enddo
การปรับปรุงตัวคูณ กับวิธีการของเลห์แมน

วิธีการของแฟร์มาต์จะทำงานได้ดีเมื่อตัวประกอบนั้นอยู่ใกล้กับค่า รากที่สองของ N ซึ่งเราอาจจะจัดการให้สิ่งนั้นเกิดขึ้นได้ ถ้ารู้ค่าอัตราส่วนโดยประมาณของ d/c โดยกำหนดให้ N แยกตัวประกอบได้ N = cd แล้ว สามารถเลือกอัตราส่วนจำนวน v/u ที่ใกล้กับค่านั้น แล้วประมาณได้ว่า N*u*v = (c*v)*(d*u) ซึ่งทำให้ใช้เมื่อวิธีของแฟร์มาต์จทำให้สามารถหาในรูป N=N*u*v ได้เร็วกว่า จากนั้นหาตัวหารร่วมมาก ของ factor ที่ได้กับ N เดิม จะได้ gcd(N,vc)= c และ gcd(N,du)=d (เว้น c หาร u หรือ d หาร v ลงตัว)
โดยปกติเราไม่สามารถรู้ค่าอัตราส่วนนั้นได้แต่ถ้าเลือกหนึ่งคือพยายามลอง u/v หลาย ๆ ค่า และพยายาแยกตัวประกอบกับ Nuv ดังกล่าวซึ่งได้มีนักคณิตศาสตร์ท่าหนึ่ง อาร์ เลห์แมน (R. Lehman)ได้คิดค้นระเบียบวิธีการที่เป็นระบบไว้สำหรับแก้ปัญหาด้วยแนวคิดนี้ ซึ่งสามารถเพิ่มประสิทธิภาพให้ การแปลงแบบแฟร์มาต์ที่เพิ่มวิธีการหารเชิงทดลอง ให้สามารถแยกตัวประกอบของ N ได้ในเวลา O(N1 / 3) ในบทความชื่อว่า การแยกตัวประกอบจำนวนเต็มขนาดใหญ่ (R. Lehman, "Factoring Large Integers", Mathematics of Computation)
วิธีการดูเหมือนกับการแยกตัวประกอบของแฟร์มาต์ โดยให้  k\geq 1 และ  x=\lceil 2{\sqrt {kN}}\rceil  ตรวจสอบว่า  (x+m)^{2}-4kN\ คือกำลังสองสำหรับ  m\geq 0 จากนั้นเราแค่จำเป็นต้องตรวจสอบ  k\leq N^{1/3} และ m สำหรับแต่ละ  m^{2}k\leq N^{1/3} เพื่อหาตัวประกอบที่  >N^{1/3}\  จะเห็นว่าวิธีนี้ใช้เวลาเป็น  O(N^{1/3})\  เราสามารถพิสูจน์ขั้นตอนเหล่านี้ได้โดยใช้วิธีการทั่วไปของ การประมาณปกติ(normal approximation)
การปรับปรุงตัวคูณ กับวิธีการของเลห์แมน > รหัสเทียม

Check that N has no divisors <= N^(1/3).     //ตรวจสอบว่าไม่มีตัวหารตามเงื่อนไข
   For 1 <= t <= N^(1/3):
     Let k = ceil (sqrt (4tN))
      For 0 <= m <= sqrt (N^(1/3) / t)
         Check whether (k+m)^2 - 4tN is a square.   //ตรวจสอบว่าเป็นกำลังสอง
        If it is a square -> calculate two factors.  //ถ้าเป็นให้คำนวณตัวประกอบ 2 ตัว
ประสิทธิภาพของรหัสเทียมดังกล่าวคือ  O(N^{1/3})\
สรุปและการประยุกต์อื่น ๆ

การแยกตัวประกอบของแฟร์มาต์เป็นวิธีหนึ่งที่ใช้ในการแยกตัวประกอบของจำนวนเต็มโดยใช้สมบัติของผลต่างกำลังสองที่เป็นจำนวนเต็มวิธีพื้นฐานปกติจะมีประสิทธิภาพที่ไม่ดีนักไม่ต่างกับการค้นหาจำนวนเต็มทุกตัวจาก 1 ถึง N ( O(n)\ ) แต่จะมีประสิทธิภาพสูงถ้าคำตอบเข้าใกล้รากที่สองของ N และสามารถนำคุณสมบัติทางคณิตศาสตร์นี้ไปประยุกต์หรือปรับปรุงกับวิธีอื่น เช่น การหารเชิงทดลอง ทำให้เห็นว่าได้ประสิทธิภาพที่ดีกว่าการใช้ตัวใดตัวหนึ่งโดยอาศัยการแยกตัวประกอบของแฟร์มาต์มาใช้ลดช่วงของการค้น หรือประยุกต์กับวิธีของเลห์แมน ดังที่ได้กล่าวไปที่ทำให้ได้ประสิทธิภาพเป็น  O(N^{1/3})\  โดยอาศัยสมบัติการความมีประสิทธิภาพสูงเมื่อเข้าใกล้รากที่สองของ N นอกจากนั้นยังเป็นรากฐานของเรื่อง ตะแกรงกำลังสอง (quadratic sieve) และ การกรองตัวเลขในขอบเขตแบบธรรมดา (general number field sieve) ซึ่งเป็นระเบียบวิธีการที่รู้จักดีสำหรับการแยกตัวประกอบ "กรณีที่แย่ที่สุด" จำนวนกึ่งเฉพาะขนาดใหญ่ ในขั้นตอน วิธีการของตะแกรงกำลังสอง ที่แตกต่างกับการแยกตัวประกอบของแฟร์มาต์ คือ แทนที่จะหาว่า  a^{2}-n เป็นกำลังสองหรือไม่เป็นลำดับ แต่จะหาเซตย่อยของส่วนประกอบของลำดับดังกล่าวที่คูณกันที่เป็นกำลังสอง ซึ่งสุดท้ายจะได้ผลที่เหมือนกับผลต่างกำลังสอง mod n ถ้าค่าดังกล่าวเป็นผลไม่ชัด (nontrivial) สามารถนำไปใช้แยกตัวประกอบของ N ต่อได้ นอกจากนี้ยังมีการนำไปใช้อีกมากมายที่ยังไม่ได้กล่าวถึงเช่น วิธีแยกตัวประกอบของดิกสัน เป็นต้น
แหล่งข้อมูลอื่น

Java Implementation Of Fermat's method and trial division เก็บถาวร 2011-08-24 ที่ เวย์แบ็กแมชชีน
ไมเคิล โอเวน

| 0 | 1 | 2 | 3 |
| --- | --- | --- | --- |
 
ข้อมูลส่วนตัว
ชื่อเต็ม:  ไมเคิล เจมส์ โอเวน
วันเกิด:  14 ธันวาคม 1979 (43 ปี)
สถานที่เกิด:  เชสเตอร์, อังกฤษ
ส่วนสูง:  5 ft 8 in (1.73 m) 
ตำแหน่ง:  กองหน้า
สโมสรเยาวชน
1991–1996:  ลิเวอร์พูล
สโมสรอาชีพ*
| ปี |  ทีม |  ลงเล่น |  (ประตู) |
| 1996–2004 |  ลิเวอร์พูล |  226 |  (118) |
| 2004–2005 |  เรอัลมาดริด |  36 |  (13) |
| 2005–2009 |  นิวคาสเซิลยูไนเต็ด |  75 |  (26) |
| 2009–2012 |  แมนเชสเตอร์ยูไนเต็ด |  31 |  (5) |
| 2012–2013 |  สโตกซิตี |  7 |  (1) |
| รวม |   |  362 |  (163) |
ทีมชาติ
|  |  อังกฤษ ยู15 |  8 |  (12) |
|  |  อังกฤษ ยู16 |  11 |  (15) |
|  |  อังกฤษ ยู18 |  14 |  (10) |
| 1997 |  อังกฤษ ยู20 |  4 |  (3) |
| 1997 |  อังกฤษ ยู21 |  1 |  (1) |
| 2006–2007 |  อังกฤษ ชุดบี |  2 |  (0) |
| 1998–2008 |  อังกฤษ |  89 |  (40) |
 *นัดที่ลงเล่นและประตูที่ยิงให้แก่สโมสรเฉพาะลีกในประเทศเท่านั้น
ไมเคิล เจมส์ โอเวน (อังกฤษ: Michael James Owen) เกิดวันที่ 14 ธันวาคม ค.ศ.1979 ที่เชสเตอร์ ในเชสเชียร์ ในประเทศอังกฤษ
วงการฟุตบอล

ไมเคิล โอเวน เป็นกองหน้าที่มีชื่อเสียงและเป็นกำลังหลักของลิเวอร์พูลในระหว่างปีที่เล่นให้กับลิเวอร์พูล (ค.ศ. 1996 - ค.ศ. 2004) เป็นผู้เล่นที่มีความโดดเด่นมาก เนื่องจากเป็นผู้เล่นที่อายุยังน้อย มีความว่องไว ยิงประตูได้คมกริบ อีกทั้งยังมีหน้าตาดี โดยมักจะถูกเปรียบเทียบกับ เดวิด เบคแคม ผู้เล่นกองกลาง กัปตันทีมชาติอังกฤษเช่นกัน จนได้รับฉายาจากแฟนฟุตบอลชาวไทยว่า "ไอ้หนูมหัศจรรย์" (Baby Goal)
ปี ค.ศ. 2001 ไมเคิล โอเวน ได้รับรางวัลนักฟุตบอลยอดเยี่ยมแห่งปีของทวีปยุโรป หรือ บัลลงดอร์ (Ballon d'Or) ต่อมา ในเอฟเอคัพ นัดชิงชนะเลิศ โอเวน ช่วยทำ 2 ประตู ช่วยให้ ลิเวอร์พูล เอาชนะ อาร์เซนอล 2-1 และพาทีมคว้าแชมป์เอฟเอคัพ ไปครอง รวมถึง แชมป์ลีกคัพ และ แชมป์ยูฟ่าคัพ ในปีเดียวกันอีกด้วย
ปี ค.ศ. 2003 ไมเคิล โอเวน พา ลิเวอร์พูล เข้ารอบชิงชนะเลิศ ลีกคัพ เจอกับ คู่ปรับตลอดกาล แมนเชสเตอร์ยูไนเต็ด โดย สตีเวน เจอร์ราร์ด ยิงให้ ลิเวอร์พูล ขึ้นนำ 1-0 ในครึ่งแรก แล้วในครึ่งหลัง ไมเคิล โอเวน ก็ยิงประตูปิดท้ายเอาชนะ แมนเชสเตอร์ยูไนเต็ด 2-0 และพาทีมคว้าแชมป์ลีกคัพ สมัยที่ 7 มาครองได้สำเร็จ รวมถึง ไมเคิล โอเวน ทำแฮตทริก โดยยิง 4 ประตูให้ ลิเวอร์พูล ถล่ม เวสต์บรอมมิชอัลเบียน 6-0
ปี ค.ศ. 2004 ไมเคิล โอเวน ได้สร้างความประหลาดใจแก่แฟนบอลและสร้างความเสียใจให้แก่แฟนลิเวอร์พูล โดยได้ย้ายไปอยู่กับ เรอัลมาดริด ในสเปน แต่ว่าไม่ประสบความสำเร็จมากเท่าสมัยอยู่กับลิเวอร์พูล
ปี ค.ศ. 2005 ไมเคิล โอเวน ได้ย้ายกลับมาอังกฤษอีกครั้ง โดยได้ย้ายไปอยู่กับ นิวคาสเซิลยูไนเต็ด แต่ก็ประสบปัญหาอาการบาดเจ็บอยู่เป็นระยะ ทำให้ไม่สามารถลงเล่นได้มากนัก เมื่อหมดสัญญากับสโมสรนิวคาสเซิลแล้ว ในปี 2009 ไมเคิล โอเวน ก็ได้ตัดสินใจย้ายทีมที่สร้างความประหลาดใจให้เหล่าแฟนบอลลิเวอร์พูลด้วยการย้ายไปโดยไม่มีค่าตัวเพื่อเล่นให้กับ แมนเชสเตอร์ยูไนเต็ด
ทีมชาติอังกฤษ

ฟุตบอลโลก 1998 ที่ฝรั่งเศส ไมเคิล โอเวน ได้ติดทีมชาติอังกฤษเป็นครั้งแรก ๆ ได้ลากลูกจากครึ่งสนามผ่านเข้าไปยิงประตูอาร์เจนตินาในการพบกันของทั้งสองทีมในรอบสอง ก่อนที่อังกฤษจะเป็นแพ้ไป แต่ทว่าลูกยิงลูกนั้นเป็นที่ฮือฮาและกล่าวขานเป็นอย่างมาก
ฟุตบอลโลก 2002 โอเวนได้ติดทีมชาติไปเล่นฟุตบอลโลกที่ เกาหลีใต้ และ ญี่ปุ่น โดยพาทีมได้อันดับ 2 ของกลุ่ม F อังกฤษชนะ 1 เสมอ 2 (เสมอ สวีเดน 1-1, ชนะ อาร์เจนตินา 1-0 และ เสมอ ไนจีเรีย 0-0) ในรอบ 16 ทีมสุดท้าย โอเวน ได้ยิงประตูที่ 3 ให้ อังกฤษ เอาชนะ เดนมาร์ก 3-0 ต่อมา อังกฤษ ได้พบกับ บราซิล ในรอบ 8 ทีมสุดท้าย ซึ่งเป็นครั้งแรกด้วยที่ทั้งสองทีมพบกันในการแข่งขันฟุตบอลโลก รอบสุดท้าย ซึ่งนัดนี้เป็นที่จับตามองอย่างมากของแฟนฟุตบอลทั่วโลก โอเวน เป็นผู้ยิงประตูให้ อังกฤษ ขึ้นนำไปก่อน 1-0 แต่ทว่าในเวลาก่อนจะหมดครึ่งแรกไม่นานบราซิลก็สามารถตีเสมอได้จาก รีวัลดู และพลิกกลับมานำในครึ่งหลัง ก่อนจะชนะ 2-1 ไปในที่สุด
ฟุตบอลชิงแชมป์แห่งชาติยุโรป 2004 โอเวนถูกเรียกติดทีมชาติอังกฤษชุดลุยศึกยูโร 2004 ที่โปรตุเกส โดยพาทีมได้อันดับ 2 ของกลุ่ม B อังกฤษชนะ 2 แพ้ 1 (แพ้ ฝรั่งเศส 1-2, ชนะ สวิตเซอร์แลนด์ 3-0 และ ชนะ โครเอเชีย 4-2) พาทีมเข้าถึงรอบ 8 ทีมสุดท้าย ก่อนพ่ายกับโปรตุเกสเจ้าภาพในการดวลจุดโทษ โอเวนยิงได้ 1 ประตู ในนัดที่เจอกับ โปรตุเกส
ฟุตบอลโลก 2006 โอเวนถูกเรียกติดทีมชาติอังกฤษในฟุตบอลโลกที่ ประเทศเยอรมัน ในฟุตบอลโลกครั้งนี้ โอเวน ไม่สามารถทำประตูได้ แต่พาทีมได้อันดับ 1 ของกลุ่ม B อังกฤษชนะ 2 เสมอ 1 (ชนะ ปารากวัย 1-0, ชนะ ตรินิแดดและโตเบโก 2-0 และ เสมอ สวีเดน 2-2) และพาทีมเอาชนะ เอกวาดอร์ 1-0 ในรอบ 16 ทีมสุดท้าย โดยพาอังกฤษเข้ารอบ 8 ทีมสุดท้ายเจอกับ โปรตุเกส แต่พ่ายในการดวลจุดโทษ หลังเสมอ 0-0 ใน 90 นาที ทำให้อังกฤษต้องตกรอบรอบ 8 ทีมสุดท้ายเป็นครั้งที่ 2 ติดต่อกันในฟุตบอลโลกหลังจากเมื่อปี 2002 พ่ายให้กับ บราซิล ในรอบเดียวกัน
สถิติ > สโมสร

| สโมสร | ฤดูกาล | ลีก | ลีก> ลงเล่น | ลีก> ประตู | ฟุตบอลถ้วย> ลงเล่น | ฟุตบอลถ้วย> ประตู | ลีกคัพ> ลงเล่น | ลีกคัพ> ประตู | ยุโรป> ลงเล่น | ยุโรป> ประตู | อื่นๆ> ลงเล่น | อื่นๆ> ประตู | รวม> ลงเล่น | รวม> ประตู |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| ลิเวอร์พูล | 1996–97 | พรีเมียร์ลีก | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 1 |
| ลิเวอร์พูล | 1997–98 | พรีเมียร์ลีก | 36 | 18 | 0 | 0 | 4 | 4 | 4 | 1 | 0 | 0 | 44 | 23 |
| ลิเวอร์พูล | 1998–99 | พรีเมียร์ลีก | 30 | 18 | 2 | 2 | 2 | 1 | 6 | 2 | 0 | 0 | 40 | 23 |
| ลิเวอร์พูล | 1999–2000 | พรีเมียร์ลีก | 27 | 11 | 1 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 30 | 12 |
| ลิเวอร์พูล | 2000–01 | พรีเมียร์ลีก | 28 | 16 | 5 | 3 | 2 | 1 | 11 | 4 | 0 | 0 | 46 | 24 |
| ลิเวอร์พูล | 2001–02 | พรีเมียร์ลีก | 29 | 19 | 2 | 2 | 0 | 0 | 10 | 5 | 2 | 2 | 43 | 28 |
| ลิเวอร์พูล | 2002–03 | พรีเมียร์ลีก | 35 | 19 | 2 | 0 | 4 | 2 | 12 | 7 | 1 | 0 | 54 | 28 |
| ลิเวอร์พูล | 2003–04 | พรีเมียร์ลีก | 29 | 16 | 3 | 1 | 0 | 0 | 6 | 2 | 0 | 0 | 38 | 19 |
| ลิเวอร์พูล | รวม | รวม | 216 | 118 | 15 | 8 | 14 | 9 | 49 | 21 | 3 | 2 | 297 | 158 |
| เรอัลมาดริด | 2004–05 | ลาลิกา | 36 | 13 | 4 | 2 | – | – | 5 | 1 | 0 | 0 | 45 | 16 |
| เรอัลมาดริด | รวม | รวม | 36 | 13 | 4 | 2 | – | – | 5 | 1 | 0 | 0 | 45 | 16 |
| นิวคาสเซิลยูไนเต็ด | 2005–06 | พรีเมียร์ลีก | 11 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 11 | 7 |
| นิวคาสเซิลยูไนเต็ด | 2006–07 | พรีเมียร์ลีก | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 0 |
| นิวคาสเซิลยูไนเต็ด | 2007–08 | พรีเมียร์ลีก | 29 | 11 | 3 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 33 | 13 |
| นิวคาสเซิลยูไนเต็ด | 2008–09 | พรีเมียร์ลีก | 28 | 8 | 2 | 0 | 2 | 2 | 0 | 0 | 0 | 0 | 32 | 10 |
| นิวคาสเซิลยูไนเต็ด | รวม | รวม | 71 | 26 | 5 | 1 | 3 | 3 | 0 | 0 | 0 | 0 | 79 | 30 |
| แมนเชสเตอร์ยูไนเต็ด | 2009–10 | พรีเมียร์ลีก | 19 | 3 | 1 | 0 | 4 | 2 | 6 | 4 | 1 | 0 | 31 | 9 |
| แมนเชสเตอร์ยูไนเต็ด | 2010–11 | พรีเมียร์ลีก | 11 | 2 | 2 | 1 | 1 | 2 | 2 | 0 | 1 | 0 | 16 | 5 |
| แมนเชสเตอร์ยูไนเต็ด | 2011–12 | พรีเมียร์ลีก | 1 | 0 | 0 | 0 | 2 | 3 | 1 | 0 | 0 | 0 | 4 | 3 |
| แมนเชสเตอร์ยูไนเต็ด | รวม | รวม | 31 | 5 | 3 | 1 | 7 | 7 | 8 | 5 | 2 | 0 | 52 | 17 |
| สโตกซิตี | 2012–13 | พรีเมียร์ลีก | 8 | 1 | 1 | 0 | 0 | 0 | – | – | – | – | 9 | 1 |
| สโตกซิตี | รวม | รวม | 8 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 1 |
| รวมทั้งหมด | รวมทั้งหมด | รวมทั้งหมด | 362 | 163 | 28 | 12 | 24 | 19 | 63 | 25 | 5 | 2 | 482 | 222 |
สถิติ > ทีมชาติอังกฤษ

| ทีมชาติอังกฤษ> ปี | ทีมชาติอังกฤษ> ลงเล่น | ทีมชาติอังกฤษ> ประตู |
| --- | --- | --- |

| 1998 | 12 | 4 |
| 1999 | 6 | 1 |
| 2000 | 6 | 3 |
| 2001 | 8 | 6 |
| 2002 | 12 | 5 |
| 2003 | 9 | 5 |
| 2004 | 13 | 4 |
| 2005 | 9 | 7 |
| 2006 | 5 | 1 |
| 2007 | 8 | 4 |
| 2008 | 1 | 0 |
| รวม | 89 | 40 |
เกียรติประวัติ > สโมสร

ลิเวอร์พูล
เอฟเอคัพ ฤดูกาล 2000-01
ลีกคัพ ฤดูกาล 2000-01, 2002-03
เอฟเอคอมมิวนิตีชีลด์ ปี 2001
ยูฟ่าคัพ ฤดูกาล 2000-01
ยูฟ่าซูเปอร์คัพ ปี 2001
เอฟเอยูธคัพ ฤดูกาล 1995-96
แมนเชสเตอร์ยูไนเต็ด
พรีเมียร์ลีก ฤดูกาล 2010-11
ลีกคัพ ฤดูกาล 2009-10
เอฟเอคอมมิวนิตีชีลด์ ปี 2010
เกียรติประวัติ > ทีมชาติอังกฤษ

FA Summer Tournament ปี 2004
เกียรติประวัติ > เกียรติประวัติส่วนตัว

บัลลงดอร์ (1) : 2001
BBC Sports Personality of the Year (1) : 1998
รองเท้าทองคำของพรีเมียร์ลีก (2) : 1997-98, 1998-99
Premier League Player of the Season (1) : 1997-98
ผู้ทำประตูสูงสุดของลิเวอร์พูล (7) : 1997-98, 1998-99, 1999–2000, 2000–01, 2001–02, 2002–03, 2003–04
นักฟุตบอลดาวรุ่งยอดเยี่ยมของพีเอฟเอ (1) : 1997-98
PFA Premier League Team of the Year (1) : 1997-98
นักฟุตบอลยอดเยี่ยมของพรีเมียร์ลีกประจำเดือน (1) : สิงหาคม 1998
FIFA World Cup Best Young Player Award (1) : ฝรั่งเศส 1998
Premier League 10 Seasons Awards (1992-93 ถึง 2001-02) : Domestic Team of the Decade
ฟีฟ่า 100
English Football Hall of Fame: 2014
ตะแกรงกำลังสอง

ขั้นตอนวิธีตะแกรงกำลังสอง (อังกฤษ: quadratic sieve algorithm: QS) เป็นหนึ่งในขั้นตอนวิธีในการแยกตัวประกอบของจำนวนเต็มให้อยู่ในรูปของผลคูณของเลขยกกำลังของจำนวนเฉพาะซึ่งยังเป็นสิ่งที่น่าสนใจเนื่องจากมีการนำไปใช้ในการเข้ารหัส (โดยถ้าใช้บางขั้นตอนวิธีอาจจะต้องใช้เวลามากกว่าอายุของจักรวาลเสียอีก) Carl Pomerance เป็นผู้ค้นพบขั้นตอนวิธีนี้ในปี ค.ศ. 1981 จากการปรับขั้นตอนวิธีตะแกรงเชิงเส้นของชโรโพล (Schroeppel's linear sieve) ซึ่งใช้ในการแก้ปัญหาเดียวกัน โดยเป็นขั้นตอนวิธีที่สามารถแยกตัวประกอบได้เร็วที่สุดสำหรับจำนวนเต็มที่มีจำนวนหลักน้อยกว่าเท่ากับ 100 หลัก แต่ในกรณีถัวเฉลี่ยของจำนวนเต็มใด ๆ นั้นจะพบว่า ขั้นตอนวิธีดังกล่าวเป็นขั้นตอนวิธีที่สามารถแยกตัวประกอบได้เร็วเป็นอันดับสองรองจากตะแกรงของเขตข้อมูลจำนวนเต็มทั่วไป (general number field sieve) ซึ่งจะพบว่าขั้นตอนวิธีแบบตะแกรงกำลังสองนั้นสามารถเข้าใจได้ง่าย เวลาที่ใช้ในการคำนวณนั้นขึ้นอยู่กับขนาดของจำนวนเต็มที่จะนำมาแยกตัวประกอบ โดยไม่ขึ้นกับโครงสร้างและคุณสมบัติของตัวเลขมากนัก
จุดประสงค์

จากดังกล่าวจะพบว่าขั้นตอนวิธีตะแกรงกำลังสองนั้นเป็นขั้นตอนวิธีที่พยายามใช้พื้นฐานของขั้นตอนวิธีในการแก้ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น (congruence of squares mod n) ซึ่งขั้นตอนวิธีดังกล่าวได้ถูกนำไปในใช้ในการแก้ปัญหาการแยกตัวประกอบของจำนวนเต็มหลากหลายขั้นตอนวิธี รวมถึงขั้นตอนวิธีตะแกรงกำลังสองเอง โดยเราจะพิจารณาแบ่งขั้นตอนวิธีนี้ออกเป็นสองส่วนคือ การเก็บสะสมข้อมูล (data collection) ซึ่งจะเก็บข้อมูลที่มีโอกาสทำให้เกิดการคอนกรูเอ็นกำลังสองเพื่อเตรียมไปประมวลผล หลังจากนั้นพิจารณาทำให้ส่วนที่สองที่เป็นการนำข้อมูลมาประมวลผล (data processing) ซึ่งจะนำข้อมูลที่เก็บมาใส่เมทริกซ์แล้วพิจารณาคำนวณค่าเพื่อหาคำตอบ จนกระทั่งพบการเกิดคอนกรูเอ็นกำลังสองจริง ๆ ในส่วนแรกนั้นเราสามารถทำได้โดยใช้ระบบคู่ขนานของระบบประมวลผลของคอมพิวเตอร์ แต่ในส่วนที่สองนั้นจะต้องไปยุ่งเกี่ยวกับหน่วยความจำเนื่องจากต้องจองพื้นที่สำหรับการสร้างเมทริกซ์ ซึ่งอาจจะต้องใช้ ขั้นตอนวิธีกล่องวีดด์แมนน์ (block Wiedemann algorithm) เข้าช่วยในการทำให้การทำงานส่วนที่สองมีประสิทธิภาพมากยิ่งขึ้นในการระบบสามารถที่จะเก็บเมทริกซ์ได้
จะพบว่าขั้นตอนวิธีตะแกรงแบบยกกำลังสองนั้นมีการดัดแปลงมาจากขั้นตอนวิธีการแยกตัวประกอบของดิกสัน
โดยเวลาในการรันสำหรับขั้นตอนวิธีตะแกรงกำลังสองสำหรับการแยกตัวประกอบจำนวนเต็ม n ใด คือ
ในสัญลักษณ์ของ L (L-notation) 
โดย e คือค่าที่นิยมใช้เป็นฐานของลอการิทึม
ขั้นตอนวิธี

จากที่ได้กล่าวไปแล้วในก่อนหน้านี้เราจะสรุปได้เป็นขั้นตอนดังต่อไปนี้
เลือกค่าที่นุ่มนวลที่สุด B (เกี่ยวข้องกับจำนวนนุ่มนวล Smooth Numbers) เพื่อพิจารณานำมาเป็นขอบเขต โดย π (B) หมายถึงจำนวนของจำนวนเฉพาะ (ที่ได้จากการแยกตัวประกอบของจำนวนเต็ม) มีค่าน้อยกว่า B ซึ่งจำนวนดังกล่าวจะส่งผลโดยตรงต่อขนาดและจำนวนของเวกเตอร์ชี้กำลัง
จากนั้นทำการร่อนตะแกรงเพื่อหา ai จำนวนทั้งหมด π (B)  + 1 ตัวเลขซึ่ง bi= (ai2 mod n เป็นจำนวนนุ่มนวลขนาด B (B-smooth)
พิจารณาแยกตัวประกอบสำหรับแต่ละ bi แล้วนำมาทำเป็นเวกเตอร์ชี้กำลัง mod 2
นำพีชคณิตเชิงเส้นมาใช้ในการพิจารณาเกี่ยวกับเซตย่อยของเวกเตอร์ที่ได้มาจากจำนวนที่มาจากการ่อนตะแกรง ว่าเมื่อนำเวกเตอร์เหล่านั้นมาบวกกันแล้วจะเป็นเวกเตอร์ศูนย์หรือไม่ตามที่ได้กล่าวไว้แล้วในก่อนหน้านี้  จากนั้นเมื่อพบเซตย่อยที่ทำให้ได้รับคำตอบในส่วนดังกล่าวก็จะนำ ai มาพิจารณาคูณกันทั้งหมดแล้วนำมาพิจารณาหาค่าเศษที่ได้จากการหารด้วย n โดยให้ค่าดังกล่าวเป็น a และพิจารณาในทำนองเดียวกับ bi ซึ่งจะพบว่าผลคูณยังคงอยู่ในรูปของจำนวนนุ่มนวลขนาด B
จากก่อนหน้านี้เราจะพบว่าเราจะได้สมการคอนกรูเอนซ์ a2=b2 mod n จากนั้นเราจะพิจาณาหาค่าของ a, b
จากสมการคอนกรูเอนซ์ก่อนหน้านี้เราสามารถที่จะแปลงสมการดังกล่าวได้เป็น  (a+b)(a-b)=0{\pmod {n}} นั่นคือเราจะพิจารณาคำนวณค่า หรม. ของผลต่างหรือผลรวมของ a, b กับ n ซึ่งค่า หรม. ดังกล่าวจะเป็นตัวประกอบหนึ่งของ n นั่นเอง ซึ่งอาจจะเกิดปัญหาในกรณีที่ หรม. ที่หามาได้นั้นมีค่าเป็น n หรือ 1 ซึ่งก็จะต้องพิจารณาหาเลือกเซตย่อยเพื่อหาค่า a ค่าอื่นแทน
ซึ่งในส่วนที่เหลือของบทความดังกล่าวจะกล่าวถึงรายละเอียดปลีกย่อยเพิ่มเติมจากขั้นตอนวิธีดังกล่าวก่อนหน้านี้
การใช้ขั้นตอนวิธีตะแกรงกำลังสองในการแก้ปัญหาคอนกรูเอนซ์

ในขั้นตอนวิธีตะแกรงแบบยกกำลังนั้นจะอาศัยการหาคู่ตัวเลขของจำนวนเต็มระหว่าง x และ y (x)  ซึ่ง y (x)  คือฟังก์ชันของ x โดยจะเลือกเซตของจำนวนเฉพาะที่เรียกว่า ฐานตัวประกอบ (factor base) ซึ่งจะหาค่า x ซึ่งคือเศษของน้อยสุดและเป็นบวกที่ทำให้ y (x)  = x2 mod n มีตัวประกอบทั้งหมดมาจากฐานตัวประกอบ ซึ่งจะเรียก x ตัวนั้นว่า นุ่มนวล (smooth) กับ ฐานตัวประกอบเหล่านั้น
โดยจากดังกล่าวขั้นตอนวิธีตะแกรงกำลังสองได้เพิ่มความเร็วโดยอาศัยหลักการที่จะหาความสัมพันธ์โดยการพิจารณาทำให้ x ที่มีค่าเข้าใกล้รากที่สองของ n ซึ่งทำให้มั่นใจได้มากขึ้นว่า y (x)  จะมีค่าเล็กขึ้น และเพิ่มโอกาสที่จะทำให้นุ่มนวลมากขึ้นด้วย
จากดังกล่าวจะเห็นว่าค่า y ว่ามีค่าประมาณ 2x[√n] อย่างไรก็ตามก็แดงให้เห็นว่าอัตราการเติบโตของ y นั้นเป็นเชิงเส้นกับ x เท่าของรากที่สองของ n
นอกจากนี้ยังจะพบว่ายังมีวิธีอื่นที่จะเพิ่มความนุ่มนวลเช่นกัน ซึ่งทำได้ง่ายโดยการเพิ่มขนาดของฐานตัวประกอบนั่นเองแต่ถึงอย่างไรนั้น ก็ยังเป็นสิ่งจำเป็นที่จะต้องหาความสัมพันธ์ที่นุ่มนวลอย่างน้อยมากกว่าจำนวนฐานของตัวประกอบอยู่ดีเพื่อให้มั่นใจได้ว่ายังมีโอกาสที่จะเกิดอิสระเชิงเส้นของเวกเตอร์ชี้กำลัง
การใช้ขั้นตอนวิธีตะแกรงกำลังสองในการแก้ปัญหาคอนกรูเอนซ์ > ความสัมพันธ์เมื่อทำไปแล้วเพียงบางส่วน (Partial relation) และวงวน (Cycles)

จากดังกล่าวเราจะพบว่าบางครั้ง y (x)  นั้นอาจจะไม่นุ่มนวลแต่ก็สามารถจะรวมความสัมพันธ์ที่เป็นส่วนย่อย (partial relations) เหล่านั้นเข้าด้วยกัน เช่น ถ้า y สองค่าเป็นผลคูณของจำนวนเฉพาะสองจำนวนที่เหมือนกันที่อยู่นอกเหนือจากฐานตัวประกอบ (แต่เท่ากับ ฐานตัวประกอบเมื่อถูกขยายแล้ว) ยกตัวอย่างเช่นมี ฐานตัวประกอบเป็น {2, 3, 5, 7} และ n = 91 เราจะได้ความสัมพันธ์ในส่วนย่อยดังนี้
โดยเมื่อพิจารณาการคูณกันจะได้ดังต่อไปนี้
จากนั้นพิจารณาการคูณทั้งสองข้างด้วย (11−1) 2 modulo 91และจาก 11−1 modulo 91 มีค่าเป็น 58 ดังนั้น
โดยในการสร้างความสัมพันธ์แบบเต็มรูปแบบในแต่ความสัมพันธ์ที่เต็มรูปแบบจะถูกเรียกว่าวงวน (cycle)
การใช้ขั้นตอนวิธีตะแกรงกำลังสองในการแก้ปัญหาคอนกรูเอนซ์ > การร่อนตะแกรง

พิจารณากระบวนการต่อไปนี้
ซึ่งจะเห็นได้ว่าได้ว่าเมื่อ y(x) ≡ 0 (mod p) สำหรับ x ใด ๆ ที่ได้คำตอบจะพบว่า y ที่สอดคล้องกับค่าดังกล่าวนั้นจะหารด้วย p ลงตัวและจากดังกล่าวปัญหาที่เราทำคือการหารากที่สองของการมอดุลโลจำนวนเฉพาะ ซึ่งจะพบว่ามีขั้นตอนวิธีที่มีประสิทธิภาพในการกระทำดังกล่าว เช่น ขั้นตอนวิธีของแชงค์และโทเนลลี่ (Shanks– Tonelli algorithm) เป็นต้น
โดยในการร่อนตะแกรงนั้นจะเริ่มด้วยการให้ทุก ๆ สมาชิกในอาเรย์ A[] เป็นค่า 0 และสำหรับในแต่ละ p ของฐานตัวประกอบก็จะถูกนำมาแก้สมการกำลังสองมอดุลโล p ซึ่งจะให้คำตอบสองค่าคือ α และ β จากนั้นก็จะให้ค่าประมาณ log(p) ให้กับสมาชิกที่มี y(x) = 0 mod p ซึ่งก็จะอยู่ในรูปแบบ A[kp + α] และ A[kp + β] นั่นเอง
ตัวอย่าง

จากดังกล่าวเราจะอธิบายตัวอย่างพื้นฐานของการประยุกต์ใช้ขั้นตอนวิธีตะแกรงกำลังสอง ในการแยกตัวประกอบของจำนวนเต็ม ซึ่งเรายกตัวอย่างตัวเลขที่มีขนาดเล็กก่อนกล่าวคือสามารถแก้ปัญหาได้โดยไม่จำเป็นต้องใช้การลดรูปด้วยการลดรูปแบบลอการึทึมหรืออื่น ๆ (logarithm optimization or prime powers) โดยตัวเลขจะนำมาแยกตัวประกอบคือ N = 15347 ซึ่งจะพบว่าค่าจำนวนเต็มที่มากกว่าหรือเท่ากับรากที่สองของจำนวนดังกล่าวคือ 124 และเนื่องจาก N มีค่าเล็กมาก จึงเพียงพอที่ใช้พหุนามในการหาคำตอบ ซึ่งจะใช้สมการกำลังสองดังกล่าวคือ y(x) = (x + 124)2 − 15347