Technology

Prime Number ตัวเลขแปลก ๆ กับการเข้ารหัส

By Arnon Puitrakul - 18 พฤศจิกายน 2022

Prime Number ตัวเลขแปลก ๆ กับการเข้ารหัส

Prime Number หรือ จำนวนเฉพาะ เป็นจำนวนที่มีความพิเศษมาก ๆ เราอาจจะเริ่มได้ยินตอนเราอยู่ประถมแล้วละ ตอนนั้น เราก็ยังสงสัยนะว่า กูเรียนไปทำไมวะ เรียนไปแล้วมันได้บ้าอะไร เพราะตอนนั้นไม่มีใครบอกนะว่า มันเอามาทำอะไรได้ แต่บอกว่า มันคืออะไร แต่พอมาเรียนพวก Cyptographic ทำให้รู้ว่า เชี้ย !! แมร่งเป็น Core เลยนิหว่า วันนี้เรามาเล่ากันแบบสนุก ๆ ละกัน

Prime Number คืออะไร ?

เอาหล่ะ เรามาทบทวน เกี่ยวกับ Prime Number หรือจำนวนเฉพาะกันก่อนดีกว่า ถ้าเราจำได้ คร่าว ๆ จำนวนเฉพาะ ก็คือ จำนวน ที่ ตัวมันเอง และ 1 หารลงตัว หรือพูดอีกนัยคือ ไม่ว่า เราจะเอาจำนวนอะไรไปหาร จะต้องมีเศษ ยกเว้น ตัวมันเอง และ 1 นั่นเอง

ถามแบบ ขำ ๆ เลย คิดว่า 1 เป็น Prime Number มั้ย เพราะ 1 หาร 1 ลงตัว และ 1 ก็หาร 1 ลงตัว ?

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

ดังนั้นจำนวนที่เล็กที่สุดที่เป็น จำนวนเฉพาะ ก็น่าจะเป็น 2 ใช่มั้ยฮะ นั่นง่าย ๆ เลย แต่ถ้าเราถามว่า แล้วจำนวนที่มากที่สุดที่เป็นจำนวนเฉพาะละ อื้มมม น่าสนใจกว่าใช่มะ จริง ๆ แล้ว Euclid เคยพิสูจน์แล้วนะว่า มันไม่มีจำนวนเฉพาะที่มากที่สุด เพราะเรากำลังพูดถึงจำนวนเต็ม ซึ่งมันไปได้เรื่อย ๆ แบบไม่มีที่สิ้นสุด เลยทำให้มันไม่มีจำนวนเฉพาะที่มากที่สุด เพราะเราไม่รู้ว่ามันไปสิ้นสุดที่ไหน

แต่ ๆ ถ้าเราลองไล่จำนวนเฉพาะออกมา แล้วเราลองสังเกตกันดูนะ ตัวแรก ๆ คือ 2 และ 3 แล้วตัวต่อไป 5 ซึ่งความห่างมันไม่เท่าละ หรือ ถ้าเราไปไกล ๆ หน่อย เอาสัก 13 แล้วตัวต่อไปเป็น 17 เราสังเกตอะไรมั้ย เราจะเห็นได้ว่า เมื่อเราหาจำนวนเฉพาะไปไกลมากขึ้นเรื่อย ๆ จำนวนเฉพาะมันจะมีน้อยลงเรื่อย ๆ และ หายากขึ้นเรื่อย ๆ ทำให้การหาจำนวนเฉพาะเป็นอะไรที่ท้าทายมาก ๆ โดยเฉพาะถ้าเราอยากจะหาในจำนวนขนาดใหญ่

Finding Prime Number

อย่างที่เราบอกว่า การหา จำนวนเฉพาะ เป็นเรื่องที่ท้าทายมาก ๆ เราลองมาหามันกันเองดีกว่า

def find_prime_brute_force (max_num : int) -> list[int] :
    prime_numbers = []

    for i in range(2,max_num+1) :
        is_prime = True

    	# Determine whether this number is prime or not
        for j in range(2,i) :
            if i % j == 0 :
                is_prime = False
                break

        if is_prime :
            prime_numbers.append(i)

    return prime_numbers

ถ้าเราคิดตรง ๆ เล่น Brute force ไปเลย เราลองเขียนออกมาเป็น Function สักตัวละกัน เราเริ่มจากการสร้าง List เพื่อเก็บคำตอบชื่อ prime_numbers จากนั้น เรามาที่ส่วนของการคิดของเราง่าย ๆ เลยคือ เรา Loop ตั้งแต่ 2 จนไปถึงจำนวนที่เราตั้งไว้เพื่อหาแล้วบวก 1 เพราะใน Loop มันจะเอาตั้งแต่ 0 ถึงจำนวนที่เราใส่ลบ 1

อะไรไม่รู้ เราก็บอกไว้ก่อนเลยว่า จำนวนนี้เป็น จำนวนเฉพาะนะ ผ่าน Flag ตอนนี้เราต้องย้อนกลับไปที่นิยามของจำนวนเฉพาะแล้วคือ เป็นจำนวนที่ 1 และ ตัวของมันเอง หารลงตัวเท่านั้น ดังนั้น เราจะต้องพิสูจน์ให้ได้ว่า ไม่มีจำนวนไหนเลย นอกจาก 1 และตัวมันเองหารลงตัว ทำให้เราจะต้อง Loop ในนั้นอีก แล้วก็เอามา Modulo หรือหารเอาเศษกัน ถ้ามันหารลงตัว คือการหารแล้วไม่มีเศษ ถ้าเกิดแบบนั้นจริง เราก็จะตั้ง Flag เป็น False ไป กับ เรา Break ออกจากการหาได้เลย เพราะ เพียงแค่จำนวนใดจำนวนหนึ่ง นอกจาก 1 และตัวมันเองหารลงตัว ก็คือจบเลย สุดท้าย ถ้ามัน Loop ผ่านมาได้หมด Flag จะยังไม่เปลี่ยน เราก็ดัก Guard ไว้ เพื่อเพิ่มจำนวนนั้น ลงไปใน List คำตอบของเรา แล้วเมื่อ Loop เสร็จ เราก็ Return มันกลับไป

เรามาลองวิเคราะห์ Algorithm นี้กันหน่อย ถ้าเราดูคร่าว ๆ เลย เราจะเห็นว่า มันมี O(n^2) เลยทีเดียว จาก Loop ทั้งหมด 2 ชั้น ชั้นแรกคือ เรา Loop เพื่อวนจำนวนที่เราต้องการหา และอีกชั้นที่ลึกลงไปคือส่วนที่เราเอามาลองหารไปเรื่อย ๆ ถ้าเราเอามาหาจำนวนไม่กี่ตัว มันก็ไม่น่ามีปัญหา แต่ถ้าเราเอามาหาจำนวนขนาดใหญ่ ๆ แบบนี้เริ่มไม่น่ารักแล้วใช่มั้ย งั้นเรามีวิธีที่ดีกว่านี้มั้ย

def find_prime_a_bit_better (max_num : int) -> list[int] :
    prime_numbers = []
    
    for i in range(2, max_num+1) :
        is_prime = True

        for j in prime_numbers :
            if i % j == 0 :
                is_prime = False
                break

        if is_prime :
            prime_numbers.append(i) 
               
    return prime_numbers

เราลองปรับปรุงอีกหน่อย ถ้าเราลองสังเกตจำนวนที่ไม่ได้เป็นจำนวนเฉพาะสักหน่อย เช่น 4 ไม่ได้เป็นจำนวนเฉพาะ เพราะว่า มันเกิดจาก 2 x 2 หรือ ถ้าเราเอา 6 บ้าง มันก็เกิดจาก 3 x 2 เราจะสังเกตว่า จำนวนอะไรสักอย่างที่ไม่ได้เป็นจำนวนเฉพาะ ถ้าเราเอามา Decompose เราจะเห็นว่า ไม่ว่ายังไง มันก็จะเกิดจากผลคูณของจำนวนเฉพาะอย่างน้อย 2 ตัวเข้าด้วยกัน

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

Algorithm ดูดีนะ เราลงรันออกมา เอาจำนวนที่มันน่าจะพอเห็นชัด ๆ หน่อย ที่สัก 10,000 ตัวไปเลย วิธีแรกที่เรา Brute Force ออกมา เราใช้ 0.1833 วินาที และ วิธีที่เราปรับ เราใช้ 0.0198 วินาที ตีขำ ๆ ก็ 9 เท่ากว่า ๆ ได้ แค่เราพยายาม Scope จำนวนที่หา ก็ทำให้ความเร็วมันได้มากขึ้น จริง ๆ วิธีนี้ เราก็เอามาใช้กับพวกงาน AI เหมือนกันไว้มาเล่าวันหลัง

เราลองมาดู Big-O กันหน่อยดีกว่า เราลอง Plot เทียบขำ ๆ มาดูกัน เพื่อให้เทียบแล้วเข้าใจได้ง่ายขึ้น เราเอา O(n), O(nlogn) และ O(n^2) ใส่เข้ามาด้วย เราจะเห็นว่า ไม่ว่าจะวิธีไหนก็ตาม มันก็จะยังน้อยกว่า n^2 แหละ แต่ ๆๆๆ ถ้าเราเอาทั้ง 2 วิธีนี้มาเทียบจริง ๆ เห็นได้เลยว่า วิธีการที่เราจำกัดตัวเลข มันช่วยได้เยอะมาก ๆ มันเกือบจะลงไปเท่ากับ O(nlogn) อยู่แล้ว มันก็จะไปตรงกับเวลาที่เราได้มานั่นเอง

ถ้าใครที่เรียนมา อ่านวิธีที่ 2 ของเรา อาจจะเอ๊ะ ๆ ว่า เห้ย มันคล้าย ๆ กับ Sieve of Eratosthenes เลย มันเป็น Algorithm ที่โคตรเก่าแก่มาก ๆ วิธีนั้นมีแนวคิดคล้าย ๆ กันคือ เรารู้ว่า อะไรที่คูณด้วยจำนวนเฉพาะลงตัว จะไม่ได้เป็นจำนวนเฉพาะ เราก็แค่ค่อย ๆ ขีดฆ่าออกไปเรื่อย ๆ เมื่อเราทำแบบนี้ไปเรื่อย ๆ จำนวนที่ไม่ได้โดนขีดฆ่า นั่นแหละคือจำนวนเฉพาะ ถ้าเราหา จำนวนเฉพาะในจำนวนที่ไม่ใหญ่มาก วิธีนี้ก็เป็นวิธีที่ดีเลยละ

แต่วิธีที่ใหม่ ๆ หน่อยพวก Sieve of Atkin พวกนี้ก็จะเร็วขึ้นอีก ลองไปหาอ่านดูได้ วิธีมันคือแบบ ซับซ้อน และ พีค ๆ เข้าใจยากกว่าเดิมหน่อย แต่ก็เร็วกว่าเดิมมาก ๆ ลองไปหาอ่านดูได้ เราไม่ขอเล่าละกัน รู้สึกว่าเริ่มจะยาวขึ้นเรื่อย ๆ แล้ว

The Largest Prime Number So Far.....

เราบอกไปว่า การหาจำนวนเฉพาะยิ่งจำนวนเยอะ ยิ่งหายากขึ้นเรื่อย ๆ ถามว่า แล้วตอนนี้ โลกของเรา เรารู้จำนวนเฉพาะที่ใหญ่ที่สุดอยู่ที่เท่าไหร่ ใช่ฮะ มันมีคนมานั่งหา และเก็บพวกสถิติของการหาจำนวนเฉพาะด้วยนะ คือ Great Internet Mersenne Prime Search (GIMPS) เราชอบเรียกขำ ๆ ว่า กิ๊มส์

ถ้าเราเคยดูพวกการ Benchmark พวก CPU ต่าง ๆ หนึ่งในเครื่องมือในการ Benchmark ก็น่าจะเคยได้ยินโปรแกรมที่ชื่อว่า Prime95 โปรแกรมนี้แหละ เขาใช้ในการเอามาหาค่าจำนวนเฉพาะกันจริง ๆ ในคอมพิวเตอร์นะ ไม่ได้เป็นแค่โปรแกรมในการ Benchmark เท่านั้น พวกจำนวนเฉพาะที่หาได้ใหม่ ๆ ที่ GIMPS เก็บไว้ หลัง ๆ ก็มาจากโปรแกรม Prime95 ทั้งนั้น

ณ วันที่เขียนตอนนี้ จำนวนเฉพาะที่เราหาได้ล่าสุด เจอในวันที่ 7 Dec 2018 นี่แหละ ห่างจากตอนนี้ 4 ปีแล้ว จำนวนของมันอยู่ที่ 2 ยกกำลัง 82,589,933 ลบอีก 1 พวกนี้เราเรียกว่า Mersenne Primes ลองไปหาอ่านเพิ่มดูได้ ๆ

สรุปแล้ว Prime Number เกี่ยวอะไรกับ Encryption

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

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

ความท้าทายมันอยู่ที่ ในการเข้ารหัส วิธีการเป็นอะไรที่ไม่ได้เป็นความลับอะไร แต่สิ่งที่เป็นความลับคือ Key หรือกุญแจในการเข้าและถอดรหัส เหมือนกับ ทุก ๆ วันที่เราใช้กุญแจ ทุกคนรู้นะว่า กุญแจทำงานยังไง มันไขแล้วปลดล๊อคได้ยังไง แต่ความยากอยู่ที่ เขี้ยวมันดอกกุญแจ

ในแง่ของการเข้ารหัสในคอมพิวเตอร์ มันเป็นเรื่องของคณิตศาสตร์เลย ถ้าใครที่มาเรียนจะเห็นเลยว่า คณิตศาสตร์เป็นอะไรที่โคตรเจ๋ง มันสวย มัน Sexy มาก ๆ โอเคนอกเรื่องไปไกลละ กลับมา ถามว่า จำนวนเฉพาะเกี่ยวอะไร

เราใช้จำนวนเฉพาะในการเอามาสร้างดอกกุญแจในการเข้าและถอดรหัสนี่แหละ ถามว่าทำไม?? เราก็ต้องย้อนกลับไปในประโยคที่เราบอกว่า การหาจำนวนเฉพาะมันเป็นเรื่องที่ใช้พลังในการประมวลผลสูงมาก ๆ แต่ การเอาจำนวณเฉพาะคูณกัน เป็นเรื่องง่ายมาก ๆ มองกลับกันถ้าเราบอกว่า เรามี 2 ฝั่ง ต่างสุ่มจำนวนเฉพาะ เช่น 23 และ 29 โดยสมมุติว่า กุญแจเกิดจากผลคูณ กลายเป็น 667

ถ้าเราพยายาม Decompose ออกมาให้ได้ เราก็จะทำได้แค่ 23 x 29 เท่านั้นแหละ ไม่สามารถเป็นตัวเลขอื่นได้แล้ว แต่ปัญหาคือ ถ้าเกิดเป็นใครไม่รู้เลย ไม่รู้ตัวเลข แต่พยายามที่จะหากุญแจนี้ให้ได้ เขาก็ต้องนั่งพยายามหา จำนวนเฉพาะอะไรไม่รู้มาคูณกันแล้วให้ได้เป็นกุญแจสักดอกที่ถอดรหัสได้ ในความเป็นจริง เราไม่ได้ใช้ตัวเลขน้อยขนาดนี้ เราใช้ตัวเลขขนาดใหญ่มาก ๆ

ทำให้การหา มันเป็นเรื่องยาก เลยทำให้การใช้จำนวนเฉพาะ ทำให้การเข้ารหัส และ ถอดรหัสมันง่าย แต่การสุ่มกุญแจ มันยากนั่นเองลองไปหาอ่านเพิ่มได้ พวก RSA และ Diffie-Hellman Key Exchange

Read Next...

ใช้ HDD ขนาดใหญ่ หรือ HDD ขนาดเล็กจำนวนมากใน NAS ดี?

ใช้ HDD ขนาดใหญ่ หรือ HDD ขนาดเล็กจำนวนมากใน NAS ดี?

จากเมื่อเดือนก่อน ๆ เราเล่าเรื่องที่เราเปลี่ยน HDD ไปในความจุที่ใหญ่ขึ้น ทำให้เราคิดย้อนตอนที่เรา Design NAS ที่จะใช้ในบ้านครั้งแรกว่า เราควรจะใช้ HDD ขนาดเท่าไหร่ดี จะใช้ HDD ขนาดความจุเล็ก ๆ จำนวนมาก หรือเอาความจุสูง ๆ ไม่กี่ลูกดีกว่า วันนี้เราเอาประสบการณ์มาเล่ากัน...

Dual Stack และ Tunnelling วิธีการเชื่อมโลก IPv4 และ IPv6 เข้าด้วยกัน

Dual Stack และ Tunnelling วิธีการเชื่อมโลก IPv4 และ IPv6 เข้าด้วยกัน

ปัจจุบันนี้เรามีการใช้ IPv6 มากขึ้นเรื่อย ๆ แน่นอนว่ายังไม่เท่ากับอุปกรณ์ที่ทำงานบน IPv4 และทั้งสอง Version นี้ไม่สามารถเชื่อมต่อคุยกันได้โดยตรง ทำให้เราจำเป็นต้องมีเทคนิคบางอย่าง วันนี้เราจะมาเล่าให้อ่านกันว่า เขาทำกันยังไง...

ประหยัดเงินหลักหมื่นค่า Mac ด้วย External SSD

ประหยัดเงินหลักหมื่นค่า Mac ด้วย External SSD

หนึ่งในตัวเลือกที่ Apple ให้เราเลือกตอนจะซื้อเครื่อง Mac คือ Storage หรือขนาดของที่เก็บข้อมูล ปัญหาคือ ยิ่งเยอะ มันทำให้เรามีพื้นที่เก็บข้อมูลมากขึ้น แต่มันมากับราคาที่สูงเหลือเกิน วันนี้เราเอาตัวเลือกในการประหยัดเงินกว่าหมื่นบาท มาใช้ External SSD กัน...

NAS vs DAS ต่างกันอย่างไร ? เราจะใช้อะไรดี ?

NAS vs DAS ต่างกันอย่างไร ? เราจะใช้อะไรดี ?

หลายบทความที่ผ่านมา เราได้แนะนำพวก NAS ไปเยอะมาก ๆ มีทั้งข้อดีและข้อเสีย บางคนอาจจะไม่เหมาะกับ NAS วันนี้เราจะมาแนะนำอีกหนึ่งทางเลือก การใช้ DAS เรามาดูกันดีกว่าว่า มันแตกต่างจาก NAS และ เราจะเหมาะสมกับการใช้งานหรือไม่ในบทความนี้กันเลย...