จำนวนเฉพาะกับการซื้อของทางอินเตอร์เน็ต ไม่เชื่อล่ะสิ!!!! ว่ามันไปด้วยกันได้

ตอนที่แล้วเราว่ากันด้วย ประวัติเล็กน้อย การหาจำนวนเฉพาะและการพิสูจน์ว่าตัวไหนนันเป็นจำนวนเฉพาะกันบ้าง

แต่แล้วเราเรียนเรื่องจำนวนเฉพาะกันไปทำไมหรอครับ มันเอาไปใช้อะไรได้บ้าง

จำนวนเฉพาะกับธรรมชาติ 

ในบทความของ Campos et al. ที่่เขียนลงใน Physical Review Letters เดือนสิงหาคม ปี 2004 ได้พบว่าแมลงชนิดหนึ่งที่เรียกว่า cicadas นั้น ซ่อนอยู่ใต้ดินเป็นปีๆ ก่อนที่จะออกมาหากินบนเหนือพื้นดินแค่ 6 อาทิตย์ก่อนจากไป วงจรชีวิตของมันนั้น สอดคล้องกับจำนวนเฉพาะอย่างยิ่ง เหตุผลเพราะว่า มันเลือกที่จะอยู่ใต้ดิน เป็นตัวเลขจำนวนเฉพาะ (13 หรือ 17ปี)ไงครับ และเหตุผลก็เพราะว่า มันจะหลีกเลี่ยงนักล่าของมันครับ

<p style="margin: 0in 0in 0pt" class="MsoNormal"></p>

หรือว่า ในการศึกษาของ Yoshimura ในปี 1997 ก็พบว่าการที่แมลงบางชนิดนั้นเลือกที่จะมีวงจรชีวิตเป็นจำนวนเฉพาะก็เพราะว่าจะทำให้ไม่เกิดสายพันธุ์ประหลาดขึ้นมา

จำนวนเฉพาะกับดนตรี

เรื่องของดนตรี ก็มีนะครับ ในอัลบั้มเพลงคลาสสิคที่ชื่อ Messiaen: Quartet for the end of time. Messiaen นั้นใช้โน้ต 17 ตัวและ 29 ตัว เล่นสอดคล้องกันไปมาในเพลง ทำให้เกิดการผสมผสานของเสียงดนตรีใหม่ๆขึ้นมา

แต่ที่สำคัญที่สุดในการประยุกต์ใช้จำนวนเฉพาะคือ การถอดรหัสครับ หรือที่เรียกกันเป็นภาษาอังกฤษว่า cryptography

การถอดรหัส 

การถอดรหัสนั้นใช้ในการแปลงการส่งข้อมูลลับแต่ช่องทางการส่งนั้นมันไม่ลับครับ เช่้น การจ่ายเงินทางบัตรเครดิตทางอินเตอร์เน็ต การส่งคลื่นวิทยุ (radio transmission) สายโทรศัพท์ เป็นต้น

เออออออ แล้วมันใช้กันยังไง กันเนี่ย

ตัวอย่างอันนี้ดัดแปลงมาจากหนังสือของ Dr. Devlin ครับ

สมมตินะครับว่า ผมเอาจำนวนเฉพาะสองตัวมาคูณกัน แต่เอาแบบตื่นเต้นหน่อย เอาจำนวนเฉพาะที่มีเลขสัก 50 หลัก สองตัวมาคูณกันล่ะกัน เมื่อเอาเลข 50 หลักสองตัวมาคูณกัน เราก็ได้เลขหลายหลักใช่ไหมครับ ให้มากสุดเลข เลขตัวใหม่มี 100 หลัก

</span><p style="margin: 0in 0in 0pt" class="MsoNormal"> </p><p style="margin: 0in 0in 0pt" class="MsoNormal" align="center">A₅₀* B₅₀= C₁₀₀</p><p style="margin: 0in 0in 0pt" class="MsoNormal">(ตัวห้อยแทนจำนวนหลักของตัวเลขครับ)</p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p>

คราวนี้ผมก็ให้เลข C ที่มี 100 หลัก เนี่ยกับคุณผู้อ่าน แล้วบอกให้คุณผู้อ่านหามาว่า เลขตัวนี้ตัวประกอบอะไรบ้าง ตัวประกอบของ C มีแต่ 3 ตัวถูกไหมครับ คือ 1*A₅₀* B₅₀แต่เราไม่สนใจ 1 นี่ครับ ก็ใครๆก็รู้อยู่แล้ว

ที่มี 3 ตัว เพราะว่า A₅₀ , B₅₀ นั้นเป็นจำนวนเฉพาะ

เพราะฉะนั้นหน้าที่ของคุณผู้อ่านก็แค่หา A₅₀  กับ B₅₀ ถูกไหมครับ

ตรงนี้แหละครับปัญหา ในขณะที่เราสามารถหาว่า C นั้นเป็นจำนวนเฉพาะหรือเปล่าอย่างง่ายดาย

แต่เราไม่สามารถหาตัวประกอบของ C ได้ง่ายๆครับ โดยเฉพาะอย่าง

ยิ่งเลขที่มีหลายหลัก

แล้วก็ความแตกต่างตรงนี้แหละครับ ที่นักคณิตศาสตร์หัวใสเอามาใช้ในการถอดรหัส

                       KEY                                                                                KEY

                         ||                                                                                    ||

                         V                                                                                     V

ข้อความ => Encrypting program => ข้อความที่ไปตามสาย => Decrypting program =>ข้อความ

 

วิธีการทำงานของเครื่องถอดรหัส ก็จะมีตามรูปนี้แหละครับ แล้วถ้าเราใช้ความรู้เรื่องจำนวนเฉพาะ แค่ถ้าเรามี KEY (ซึ่งส่วนมากก็จะเป็นตัวเลขเป็นร้อยหลักขึ้นไป) เราก็สามารถถอดรหัสได้แล้วใช่ไหมครับ ก็ในเมื่อข้อความนั้น เป็นตัวประกอบของ KEY เอา KEY มาหาร ตัวเลขหรือข้อความที่ส่งมาตามสาย เราก็จะได้ตัวประกอบอีกตัว ซึ่งก็คือข้อความทั้งหมดที่เราส่งมาตั้งแต่แรกแล้ว

ดังนั้นวิธีนี้นั้นสิ่งที่สำคัญและจำเป็นที่สุดก็คือการรักษาความลับของ KEY เพราะฉะนั้นเพื่อความปลอดภัย มันก็จะมีการเปลี่ยน KEY กันบ่อยๆ เช่นทุกๆชั่วโมง (เหมือนในหนังพวกปล้นเซฟ ปล้นธนาคารไหมครับ)

Fermat's theorem 

คราวนี้มาดูอีกวิธีหนึ่งครับ

วิธีนี้นั้นใช้หลักการของการ modular ครับ modular คือว่า เราเอาแต่เลขเศษครับ เช่น 10 mod 2 =0 เพราะ 2 หาร 10 ได้ลงตัว หรือ 78 mod 20 = 18 หรือว่าถ้ายังคิดไม่ออกอีก หลักการของ modular ก็คือเวลาครับ ไม่ว่าจะเป็นชั่วโมงหรือนาที เช่น เกินเที่ยงเราก็เรียก บ่ายโมง บ่ายสอง บ่ายสาม ไปเรื่อย จนถึงเที่ยงคืน แล้วก็วนมาที่ ตีหนึ่ง ตีสอง ตีสาม ไปเรื่อยๆ ใช่ไหมครับ หรือว่า 150 นาที ก็คือ 2 ชั่วโมง 30 นาที ไอ้ 30 นาที เนี่ยแหละ ที่เราเรียกว่า mod

<p style="margin: 0in 0in 0pt" class="MsoNormal"></p>

และแน่นอนครับ เรื่องหลักของเราก็คือ จำนวนเฉพาะ

สมมติว่าเราต้องการส่งเบอร์บัตรเครดิตให้เพื่อนนะครับ เบอร์บัตรเครดิตคือ C และมีตัว KEY ตัวหนึ่งให้เป็น K ตัวเลขที่เราต้องการส่งก็คือ C^K

</span></span><p style="margin: 0in 0in 0pt" class="MsoNormal"> </p><p style="margin: 0in 0in 0pt" class="MsoNormal">แล้วเราจะถอดรหัสยังไง เราก็ใช้ Fermat ที่เราพูดถึงเมื่อตอนที่แล้วไงครับ ที่ Fermat บอกว่า </p><p align="center">a^p-1 mod p =1</p><p style="margin: 0in 0in 0pt" class="MsoNormal">แล้ว p เป็นจำนวนเฉพาะ </p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal">ลองปรับรูปลักษณ์นิดหน่อย </p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p align="center">a^p/a mod p =1</p><p>ถ้าเอา a คูณทั้งสองข้างของสมการ ได้อะไรครับ </p><p align="center">a^p mod p =a</p><p>อ้าวตกใจล่ะสิ </p><p style="margin: 0in 0in 0pt" class="MsoNormal">นั่นหมายความว่า เราเอาตัวเลขอะไรก็ได้ a=>(ส่งเข้าไปในกล่องหนึ่งกล่องดำลึกลับ ทำให้มันเป็น) a^p =>(ใช้เวทมนตร์นิดหน่อย โดยการ mod p) แล้วเราก็ได้ a กลับออกมาเหมือนเดิม!!!!! </p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal">โหหห น่าตกใจไหมครับ อยู่ๆก็ทำได้ด้วย </p><p style="margin: 0in 0in 0pt" class="MsoNormal">ดังนั้นปัญหาของเราก็คือการหาตัวจำนวนเฉพาะ p มาแกะรหัสลับใช่ไหมครับ </p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal">แต่วิธีการของ Fermat นั้นมันไม่สามารถออกแบบรหัสลับได้ลับเท่าไร วิธีการที่ดีกว่าคือของออยเลอร์ครับ </p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal">Euler’s method</p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p>

ออยเลอร์บอกว่า ถ้าให้ n เป็นผลคูณของจำนวนเฉพาะสองตัว p กับ q แล้วให้ e กับ d เป็นจำนวนนับใด้ โดยที่ ed จะมีเศษหนึ่งหลังจากหารด้วย (p-1)(q-1)  จากนั้น

ถ้าให้ m เป็นจำนวนนับ ที่น้อยกว่าค่า p และ q แล้ว

m^ed=(m^e)^d แล้วหลังจากที่หารด้วย n แล้ว จะเหลือเศษ m

ค่อยๆดูกันดีๆนะครับ ถ้าเอาภาษาข้างบนก็คือ

</span><p align="center">(m^e)^d  mod n = m</p><p>คราวนี้หมายความว่ายังไงครับ หมายความว่า ถ้าผมมีตัวเลขหนึ่งตัว คือ m เอาใส่กล่องดำสองอัน (อันแรก ได้ (m^e) อันที่สองก็จะได้ (m^e)^d  จากนั้น ใช้เวทมนตร์ด้วยการหาร n ซึ่งเป็นผลคุณของจำนวนเฉพาะสองตัว (p และ q) เราก็จะได้ m ออกมาเหมือนเดิม</p><p>ยกตัวอย่างนะครับ ให้ p=3, q=5, n=pq=15 ต่อมาให้ e=11, d=3, ed=33 ทำให้ (p-1)(d-1)=(2*4)=8 เมื่อเอาไปหาร ed (33) ก็จะเหลือเศษ 1 ต่อมาให้ m=2, </p><p style="margin: 0in 0in 0pt" class="MsoNormal">2³³ หารด้วย n(15) ก็จะเหลือเศษ 2 ตามที่ออยเลอร์บอกออกมาเลย (ตัวอย่างนี้เอามาจาก classwork ของ MIT ครับ) </p><p>แล้ววิธีของออยเลอร์ดียังไง </p><p>ก็ยุ่งยากกว่ายังไงครับ ในเมื่อยุ่งยากกว่า ก็จะถอดรหัสได้ยากกว่า สำหรับคนที่เราไม่ต้องการให้รู้ แต่สำหรับคนที่เราต้องการให้รู้แล้วนั้น ไม่ยุ่งยากเลยครับ </p>วิิธีการของออยเลอร์นั้น จำเป็นต้องรู้ d เพื่อที่จะถอดรหัสออกมาได้ ถ้าไม่รู้ค่า d เราก็ทำอะไรไม่ได้  สมมตินะครับ ผมส่งตัวเลข n กับ e ไปให้คุณผู้อ่าน ให้คุณผู้อ่านส่งเลขบัตรเครดิตมา คุณผู้อ่านก็แค่จัดการ เอาเลขบัตรเครดิต ยกกำลัง e ซะ แล้วก็หารด้วย n พอเหลือเศษเท่าไร ก็ส่งมาให้ผม   <p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal">พอมาถึงผม ผมก็เอา d ที่ผมซ่อนไว้ มายกกำลังของเศษที่คุณผู้อ่านส่งมาซะ แล้วก็ จัดการใช้ Euler’s theorem ที่พูดไ้ว้ข้างต้น ผมก็จะได้เบอร์บัตรเครดิตคุณผู้อ่านแล้วครับ แต่ถ้าคนอื่นไม่มีตัวเลข d ก็คงหากันตาเหลือกอ่ะครับ </p>  <p style="margin: 0in 0in 0pt" class="MsoNormal">แต่สำหรับวิธีการของ Fermat นั้น ถ้าไม่มีรหัสลับที่เราซ่อนไว้กับตัวได้ไงครับ ดังนั้นก็เลยแย่กว่าวิธีการของออยเลอร์ครับ</p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p style="margin: 0in 0in 0pt" class="MsoNormal">เสาร์หน้าเราจะมาพูดกันถึงปัญหาเงินล้านของจำนวนเฉพาะครับ ที่มีมาสี่ร้อยกว่าปีแล้ว แต่ยังไม่มีใครแก้ได้เลย ถ้าแก้ได้นี่เอาไปเลยล้านเหรียญนะครับ </p><p style="margin: 0in 0in 0pt" class="MsoNormal"></p><p></p><p>ที่มา du Sautoy, M. The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. HarperCollins 2004 (มีเว็บไซท์ที่http://www.musicoftheprimes.com/)Devlin, K. The language of mathematics, W. H. Freeman and Company, NY. 1998 http://en.wikipedia.org/wiki/Prime_number#There_are_infinitely_many_prime_numbershttp://web.mit.edu/15.566/spring98/syllabus/rsa.txt</p>

[นักลงทุนเงินน้อย]

ผมขอบายเงินล้านเหรียญดีกว่าครับ เพราะไม่มีความสามารถพอครับ

[ขจิต ฝอยทอง]

• สงสัยไม่รอดครับ
• ขออ่านอย่างเดียวดีกว่าครับ
• ขอบคุณครับ

[ไปอ่านหนังสือ]

สวัสดีครับ คุณน้องเดอและอาจารย์ขจิต

ยังไม่ได้เอาโจทย์มาคุย ถอดใจแล้วหรอครับ :D

[ขจิต ฝอยทอง]

• ตามมาขอบคุณ
• ยังอยู่เมืองไทยอยู่เลยครับ
• ถูก สกอ เลื่อนการเดินทางครับผม