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

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

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

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

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

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

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

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

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

การถอดรหัส

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

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

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

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

A₅₀* B₅₀= C₁₀₀

(ตัวห้อยแทนจำนวนหลักของตัวเลขครับ)

คราวนี้ผมก็ให้เลข 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

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

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

แล้วเราจะถอดรหัสยังไง เราก็ใช้ Fermat ที่เราพูดถึงเมื่อตอนที่แล้วไงครับ ที่ Fermat บอกว่า

a^p-1 mod p =1

แล้ว p เป็นจำนวนเฉพาะ

ลองปรับรูปลักษณ์นิดหน่อย

a^p/a mod p =1

ถ้าเอา a คูณทั้งสองข้างของสมการ ได้อะไรครับ

a^p mod p =a

อ้าวตกใจล่ะสิ

นั่นหมายความว่า เราเอาตัวเลขอะไรก็ได้ a=>(ส่งเข้าไปในกล่องหนึ่งกล่องดำลึกลับ ทำให้มันเป็น) a^p =>(ใช้เวทมนตร์นิดหน่อย โดยการ mod p) แล้วเราก็ได้ a กลับออกมาเหมือนเดิม!!!!!

โหหห น่าตกใจไหมครับ อยู่ๆก็ทำได้ด้วย

ดังนั้นปัญหาของเราก็คือการหาตัวจำนวนเฉพาะ p มาแกะรหัสลับใช่ไหมครับ

แต่วิธีการของ Fermat นั้นมันไม่สามารถออกแบบรหัสลับได้ลับเท่าไร วิธีการที่ดีกว่าคือของออยเลอร์ครับ

Euler's method

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

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

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

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

(m^e)^d mod n = m

คราวนี้หมายความว่ายังไงครับ หมายความว่า ถ้าผมมีตัวเลขหนึ่งตัว คือ m เอาใส่กล่องดำสองอัน (อันแรก ได้ (m^e) อันที่สองก็จะได้ (m^e)^dจากนั้น ใช้เวทมนตร์ด้วยการหาร n ซึ่งเป็นผลคุณของจำนวนเฉพาะสองตัว (p และ q) เราก็จะได้ m ออกมาเหมือนเดิม

ยกตัวอย่างนะครับ ให้ 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,

2³³ หารด้วย n(15) ก็จะเหลือเศษ 2 ตามที่ออยเลอร์บอกออกมาเลย (ตัวอย่างนี้เอามาจาก classwork ของ MIT ครับ)

แล้ววิธีของออยเลอร์ดียังไง

ก็ยุ่งยากกว่ายังไงครับ ในเมื่อยุ่งยากกว่า ก็จะถอดรหัสได้ยากกว่า สำหรับคนที่เราไม่ต้องการให้รู้ แต่สำหรับคนที่เราต้องการให้รู้แล้วนั้น ไม่ยุ่งยากเลยครับ

วิิธีการของออยเลอร์นั้น จำเป็นต้องรู้ d เพื่อที่จะถอดรหัสออกมาได้ ถ้าไม่รู้ค่า d เราก็ทำอะไรไม่ได้ สมมตินะครับ ผมส่งตัวเลข n กับ e ไปให้คุณผู้อ่าน ให้คุณผู้อ่านส่งเลขบัตรเครดิตมา คุณผู้อ่านก็แค่จัดการ เอาเลขบัตรเครดิต ยกกำลัง e ซะ แล้วก็หารด้วย n พอเหลือเศษเท่าไร ก็ส่งมาให้ผม

พอมาถึงผม ผมก็เอา d ที่ผมซ่อนไว้ มายกกำลังของเศษที่คุณผู้อ่านส่งมาซะ แล้วก็ จัดการใช้ Euler’s theorem ที่พูดไ้ว้ข้างต้น ผมก็จะได้เบอร์บัตรเครดิตคุณผู้อ่านแล้วครับ แต่ถ้าคนอื่นไม่มีตัวเลข d ก็คงหากันตาเหลือกอ่ะครับ

แต่สำหรับวิธีการของ Fermat นั้น ถ้าไม่มีรหัสลับที่เราซ่อนไว้กับตัวได้ไงครับ ดังนั้นก็เลยแย่กว่าวิธีการของออยเลอร์ครับ

เสาร์หน้าเราจะมาพูดกันถึงปัญหาเงินล้านของจำนวนเฉพาะครับ ที่มีมาสี่ร้อยกว่าปีแล้ว แต่ยังไม่มีใครแก้ได้เลย ถ้าแก้ได้นี่เอาไปเลยล้านเหรียญนะครับ

ที่มา 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