Computational number theory is the branch of number theory concerned with finding and implementing efficient computer algorithms for solving various problems in number theory. Much progress has been made in this field in recent years, both in terms of improved computer speed and in terms of finding more efficient algorithms. Two important applications of computational number theory are primality testing and prime factorization of large integers.

Primality testing is considered easy in the sense that very large general numbers (currently up to 4000 digits or so) can be tested reliably for primality. In fact, on August 6, 2002, Agrawal, Saxena, and Kayal found a polynomial time algorithm for testing and proving the primality of general numbers. Although this algorithm is still impractical, it was a landmark discovery, since polynomial time algorithms are considered easy. On the other hand, factoring is considered hard in the sense that no polynomial time algorithm is currently known for factoring integers. The largest general integer to be factored was RSA-576, a 174-digit number that is the product of two 87-digit primes. The fact that primality testing is easy but factoring is hard allows for secure encryption, such as RSA encryption.

Other problems in computational number theory include computing the greatest common divisor of large numbers and computing various quantities associated with number fields, i.e., class numbers and class groups.

REFERENCES:

Bressoud, D. M. and Wagon, S. A Course in Computational Number Theory. London: Springer-Verlag, 2000.

Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد