ความยากและความซับซ้อน

26 ก.พ.

ถ้าจำนวน b บิตเป็นผลคูณของจำนวนเฉพาะ 2 ตัวที่มีขนาดใกล้เคียงกันแล้ว จะไม่มีขั้นตอนวิธีใดๆ ที่สามารถแยกตัวประกอบมันได้ภายในเวลาแบบพหุนาม (polynomial time) กล่าวคือ ไม่สามารถแยกตัวประกอบได้ภายใน O (bk) เมื่อ k คือค่าคงที่ค่าหนึ่ง ปัจจุบันมีขั้นตอนวิธีหลายขั้นตอนที่เร็วกว่า O ((1+ε) b) เมื่อ ε คือจำนวนบวก กล่าวคือ มีประสิทธิภาพเชิงเวลาแบบใต้เลขชี้กำลัง (sub-exponential)

ขั้นตอนวิธีที่มีเวลาการทำงานเชิงเส้นกำกับที่ดีที่สุดคือ การกรองตัวเลขในขอบเขตแบบธรรมดา (general number field sieve (GNFS)) สำหรับจำนวน b บิตจะมีความซับซ้อนเป็น

O\left (\exp\left (\left (\begin{matrix}\frac{64}{9}\end{matrix} b\right) ^{1\over3} (\log b) ^{2\over3}\right) \right).

สำหรับคอมพิวเตอร์ทั่วไป การกรองตัวเลขในขอบเขตแบบธรรมดา (GNFS) คือขั้นตอนวิธีที่ดีที่สุดสำหรับจำนวนขนาดใหญ่มากๆ (เลข 100 หลักขึ้นไป) แต่สำหรับควอนตัมคอมพิวเตอร์ ปีเตอร์ ชอร์ ได้ค้นพบขั้นตอนวิธีที่สามารถแก้ปัญหาได้ในเวลาแบบพหุนามในปี พ.ศ. 2537 ขั้นตอนวิธีของชอร์ใช้เวลาการทำงานเพียงแค่ O (b3) และใช้ปริภูมิ O (b) สำหรับจำนวน b บิต

การแยกตัวประกอบจำนวนเต็ม

26 ก.พ.

ในทฤษฎีจำนวน การแยกตัวประกอบจำนวนเต็ม (อังกฤษ: integer factorization) หรือ การแยกตัวประกอบเฉพาะ (อังกฤษ: prime factorization) คือการแบ่งย่อยจำนวนประกอบออกเป็นตัวหารไม่ชัด (ตัวหารที่ไม่ใช่ 1 กับ ตัวมันเอง) หลายๆ ตัว ซึ่งเมื่อคูณตัวหารไม่ชัดเหล่านั้นเข้าด้วยกันจะได้ผลลัพธ์ดังเดิม

เมื่อจำนวนมีขนาดใหญ่มาก ไม่มีขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มใดๆ ที่มีประสิทธิภาพเพียงพอ ในปี 2009 ความพยายามในการแยกตัวประกอบของเลข 232 หลัก ได้สำเร็จลง จากการใช้เครื่องจักรมากกว่า 100 เครื่องภายในระยะเวลา 2 ปี ความยากของปัญหาแหละนี้คือหัวใจของขั้นตอนวิธีบางอย่างในวิทยาการเข้ารหัสลับ เช่น RSA

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

การลบจำนวนเต็ม

26 ก.พ.

  ในการลบจำนวนเต็มนั้นเราอาศัยการบวกตามข้อตกลงดังนี้   

              ตัวตั้ง  –  ตัวลบ    =   ตัวตั้ง  +  จำนวนตรงข้ามของตัวลบ
  นั่นคือ  เมื่อ   a  และ  ิb  แทนจำนวนเต็มใด ๆ
 a  – b  =   a  +  จำนวนตางข้ามของ  ิb
หรือ  a  –  b    =  a  +  ( – b )

เช่น   4  –  2     =    4  +  ( – 2 )
            2 – 4       =      2  +  ( – 4 ) 
8  – ( -11 )      =     8  +  11  

หลักเกณฑ์การบวก

26 ก.พ.
  • การบวกจำนวนเต็มบวกด้วยจำนวนเต็มบวก ให้นำค่าสัมบูรณ์มาบวกกันแล้วตอบเป็นจำนวนเต็มบวก
  • การบวกจำนวนเต็มลบด้วยจำนวนเต็าลบ  ให้นำค่าสัมบูรณ์มาบวกกันแล้วตอบเป็นจำนวนเต็มลบ
  • การบวกระหว่างจำนวนเต็มบวกกับจำนวนเต็มลบที่มีค่าสัมบูรณ์ไม่เท่ากัน ให้นำค่าสัมบูรณ์ที่มากกว่าลบด้วยค่าสัมบูรณ์ที่น้อยกว่า  แล้วตอบเป็นจำนวนเต็มบวกหรือจำนวนเต็มลบตามจำนวนที่มีค่าสัมบูรณ์มากกว่า
  • การบวกระหว่างจำนวนเต็มบวกกับจำนวนเต็มลบที่มีค่าสัมบูรณ์เท่ากัน ผลบวกเท่ากับ  0

จำนวนตรงข้าม

26 ก.พ.

  ถ้า a เป็นจำนวนเต็มใด ๆ จำนวนตรงข้ามของ a เขียนแทนด้วย – a  และ a+ (-a) = (-a) + a = 0

      ถ้า  a  เป็นจำนวนเต็มใด ๆ จำนวนตรงข้ามของ -a คือ a  ซึ่งเขียนแทนด้วย  – ( – a )  = a

สำหรับ 0 จะมี  0  เป็นจำนวนตรงข้ามของ  0

ในทางคณิตศาสตร์ จำนวนตรงข้ามของจำนวนเต็มแต่ละจำนวนมีเพียงจำนวนเดียวเท่านั้น
สำหรับจำนวนเต็มของ  – 5  จำนวนตรงข้ามของ – 5 คือ  5
และจำนวนตรงข้ามของ – 5 เขียนแทนด้วย – ( – 5 )
เนื่องจากจำนวนตรงข้ามของ – 5  มีเพียงจำนวนเดียว
ดังนั้น – ( – 5)  =  5

การเปรียบเทียบจำนวนเต็ม

26 ก.พ.

   ในการเปรียบเทียบจำนวนเต็มสองจำนวนที่ไม่เท่ากัน  เพื่อดูว่าจำนวนใดน้อยกว่าหรือจำนวนใดมากกว่าเราจะเห็นได้ง่ายโดยใช้เส้นจำนวน บนเส้นจำนวน  จำนวนเต็มที่อยู่ทางขวาจะมากกว่าจำนวนเต็มที่อยู่ทางซ้ายเสมอ  เช่น

           5   มากกว่า  4  ใช้สัญลักษณ์  5 >  4    หรือ  4  น้อยกว่า  4  ใช้สัญลักษณ์  4<    5
           3   มากกว่า  1  ใช้สัญลักษณ์  3   >  1   หรือ   1   น้อยกว่า  3  ใช้สญลักษณ์  1 <  3
           0  มากกว่า  – 1  ใช้สัญลักษณ์ 0  >  – 1  หรือ  – 1  มากกว่า  0  ใช้สัญลักษณ์  -1  <   0

ประเภทจำนวนเต็มบวก

26 ก.พ.

1. จำนวนเต็มบวก  ได้แก่จำนวนที่ใช้แทนจำนวนเนับ เช่น

 1   a_cat_1.gif

3    a_cat_1.gifa_cat_1.gifa_cat_1.gif

2. จำนวนเต็มลบ  ได้แก่  -1 -2 ,-3  

3.  ศูนย์ ได้ แก่  0