هناك أكثر من 15 اختبارا لمعرفة هل عدد معين أولي أم لا و من بينها:
اختبار ليكاس - ليهمر
طريقة اريتاسثونيس
اختبار فيرما المتربط بمبرهنة فيرما الصغرى
[عدل] طريقة اريتاسثونيس
تستعمل طريقة اريتاسثونيس لإيجاد الأرقام الأولية أقل من رقم معين. تقتضي هذه الطريقة بكتابة كل الأرقام الأقل من الرقم المعين (ص)، ومن ثم تعين رقم ط، ونبدأ بجعل ط=2، حاذفين كل مضاعفات ط حتى الرقم ص، ثم نجعل ط=3، ثم 4، 5، 6، الخ. نكمل هذه العملية حتى يصبح طxط أكبر من ص. كل الأرقام الباقية بعد الخذوفات هي ارقام أولية.
طريقة اريتاسثونيس
[عدل] اختبار فيرما
مبرهنة فيرما الصغرى تبين أنه إذا كان p عدد أولي و a عدد أولي مع p, إذن :
عكس المبرهنة خاطئ, مثلا 561=3×11×17 ليس عدد أولي و مع ذلك بالنسبة لعدد a أولي مع 561, لدينا
لكن يمكن مع ذلك كتابة:
إذا كان p غير أولي فإن ap − 1 متوافق مع 1 بترديد p لقيمة ما a
الشيء الذي يمثل عكس احتمالي للمبرهنة.
برمجة التشفير PGP, تستعمل هذه الخاصية لمعرفة إذا كانت الأعداد العشوائية التي يختارها أعداد أولية. إذا كان: , فهذا يعني أن x عدد أولي احتمالي.
إذا أعطت إحدى المعادلات قيمة مخالفة ل1, في هذه الحالة x عدد غير أولي قطعيا.
اختبار ليكاس - ليهمر
طريقة اريتاسثونيس
اختبار فيرما المتربط بمبرهنة فيرما الصغرى
[عدل] طريقة اريتاسثونيس
تستعمل طريقة اريتاسثونيس لإيجاد الأرقام الأولية أقل من رقم معين. تقتضي هذه الطريقة بكتابة كل الأرقام الأقل من الرقم المعين (ص)، ومن ثم تعين رقم ط، ونبدأ بجعل ط=2، حاذفين كل مضاعفات ط حتى الرقم ص، ثم نجعل ط=3، ثم 4، 5، 6، الخ. نكمل هذه العملية حتى يصبح طxط أكبر من ص. كل الأرقام الباقية بعد الخذوفات هي ارقام أولية.
طريقة اريتاسثونيس
[عدل] اختبار فيرما
مبرهنة فيرما الصغرى تبين أنه إذا كان p عدد أولي و a عدد أولي مع p, إذن :
عكس المبرهنة خاطئ, مثلا 561=3×11×17 ليس عدد أولي و مع ذلك بالنسبة لعدد a أولي مع 561, لدينا
لكن يمكن مع ذلك كتابة:
إذا كان p غير أولي فإن ap − 1 متوافق مع 1 بترديد p لقيمة ما a
الشيء الذي يمثل عكس احتمالي للمبرهنة.
برمجة التشفير PGP, تستعمل هذه الخاصية لمعرفة إذا كانت الأعداد العشوائية التي يختارها أعداد أولية. إذا كان: , فهذا يعني أن x عدد أولي احتمالي.
إذا أعطت إحدى المعادلات قيمة مخالفة ل1, في هذه الحالة x عدد غير أولي قطعيا.