2026-09-20T01:20:46.310595900Zhttps://opus.uleth.ca/server/oai/request
oai:opus.uleth.ca:10133/69522024-11-16T06:04:34Zcom_10133_3346com_10133_1com_10133_296col_10133_3347col_10133_298
ULethbridge OPUS Repository supervisor Fiori, Andrew supervisor Kadiri, Habiba author Gheisari, Hiva author University of Lethbridge. Faculty of Arts and Science 2024-11-15T19:26:21Z 2024-11-15T19:26:21Z 2024 https://hdl.handle.net/10133/6952 In mathematics, especially number theory, prime numbers are essential concepts. Prime numbers are used in cryptography as one application. Finding large prime numbers is crucial for cryptographic protocols; to do this, we must be able to tell whether a given number is prime or not. To test whether a number is a prime number, we require a computationally efficient primality testing algorithm. The primary objective of my research is to evaluate how well the tests work. Especially, in my research our main focus is on Grantham’s primality test. Grantham’s test is probabilistic and fast, but it comes with the risk of false positives. To determine how ‘good’ a test is, one must be aware of the possibility of false positives because in our development, deterministic tests are slower than false positive ones. In this thesis, we will explain the definitions of ‘probable prime numbers’, such as ‘Frobenius pseudoprime’, as given by Jon Grantham. Our research goal is to find upper and lower bounds for the number of probable prime numbers by generalizing the work of Paul Erdös and Carl Pomerance on Fermat pseudoprimes, and Jon Grantham on Frobenius pseudoprimes. en Prime numbers Probable prime numbers Primality test Pseudoprimes Grantham Frobenius Fermat Studying the efficiency of the Frobenius primality test Thesis PGI+VGhlIEdvdmVybm9ycyBvZiB0aGUgVW5pdmVyc2l0eSBvZiBMZXRoYnJpZGdlICjigJxVbml2ZXJzaXR5IG9mIExldGhicmlkZ2XigJ0pIHwgTm9uLUV4Y2x1c2l2ZSBUaGVzaXMgTGljZW5zZSBBZ3JlZW1lbnQ8L2I+CjxwPkluIGNvbnNpZGVyYXRpb24gb2YgdGhlIFVuaXZlcnNpdHkgb2YgTGV0aGJyaWRnZSBhZ3JlZWluZyB0byBtYWtlIHlvdXIgdGhlc2lzL2Rpc3NlcnRhdGlvbiAodGhlICJUaGVzaXMiKSBhdmFpbGFibGUgdG8gaW50ZXJlc3RlZCBwZXJzb25zLCB5b3UgYWdyZWUgYXMgZm9sbG93czogPC9wPgo8b2w+CjxsaT5Zb3UgaGVyZWJ5IGdyYW50IHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgYSBub24tZXhjbHVzaXZlLCB3b3JsZHdpZGUsIGlycmV2b2NhYmxlLCByb3lhbHR5LWZyZWUgbGljZW5zZSB0byBhcmNoaXZlLCBwcmVzZXJ2ZSwgcHJvZHVjZSwgcmVwcm9kdWNlLCBwdWJsaXNoLCBjb21tdW5pY2F0ZSwgY29udmVydCBpbnRvIGFueSBmb3JtYXQsIGNvbW11bmljYXRlIGFuZCBkaXN0cmlidXRlIHRoZSBUaGVzaXMsIGluY2x1ZGluZyB0aGUgVGhlc2lzIGFic3RyYWN0LCBpbiBhbnkgZm9ybWF0IGFuZCBpbiBhbnkgbWVkaXVtIGZvciBub24tY29tbWVyY2lhbCBwdXJwb3NlcyBmb3IgdGhlIGZ1bGwgdGVybSBvZiB0aGUgY29weXJpZ2h0LCBpbmNsdWRpbmcgYnV0IG5vdCBsaW1pdGVkIHRvIHRoZSByaWdodCB0bzoKPG9sIHR5cGU9ImEiPjxsaT5tYWtlIHRoZSBUaGVzaXMgYXZhaWxhYmxlIGluIHByaW50IG9yIG9ubGluZSBieSB0ZWxlY29tbXVuaWNhdGlvbiB0byB0aGUgcHVibGljLCBpbmNsdWRpbmcgdmlhIHRoZSBpbnRlcm5ldCBhbmQgZmFjc2ltaWxlIHRyYW5zbWlzc2lvbiwgZm9yIG5vbi1jb21tZXJjaWFsIHB1cnBvc2VzOzwvbGk+CjxsaT5kaXN0cmlidXRlIHRoZSBUaGVzaXMgdGhyb3VnaCB0aGUgbGlicmFyeSwgaW50ZXJsaWJyYXJ5IGFuZCBwdWJsaWMgbG9hbjs8L2xpPgo8bGk+ZGlnaXRpemUsIHBob3RvY29weSBhbmQgbWljcm9maWNoZSB0aGUgVGhlc2lzOzwvbGk+CjxsaT5zdWItbGljZW5jZSB0byBMaWJyYXJ5IGFuZCBBcmNoaXZlcyBDYW5hZGEgYW55IG9mIHRoZSBhY3Rpb25zIG1lbnRpb25lZCBhYm92ZTsgYW5kIDwvbGk+CjxsaT5zdWItbGljZW5jZSB0byBQcm9RdWVzdCBEaXNzZXJ0YXRpb25zIGFuZCBUaGVzZXMgR2xvYmFsIGFueSBvZiB0aGUgYWN0aW9ucyBtZW50aW9uZWQgYWJvdmUuICA8L2xpPjwvPC9vbD48L2xpPgo8bGk+WW91IGNvbmZpcm0gdGhlIGZvbGxvd2luZyBzdGF0ZW1lbnRzIHRvIGJlIHRydWUgYW5kIGFjY3VyYXRlOgo8b2wgdHlwZT0iYSI+PGxpPnlvdSBoYXZlIHRoZSByaWdodCBhbmQgYXV0aG9yaXR5IHRvIGdyYW50IHRoZSByaWdodHMgc2V0IG91dCBpbiB0aGlzIGxpY2Vuc2U7IDwvbGk+CjxsaT50aGUgVGhlc2lzIGlzIHlvdXIgb3JpZ2luYWwgd29yayBhbmQgaXMgYW4gdW4tYW1lbmRlZCBjb3B5IG9mIHRoZSBmaW5hbCB2ZXJzaW9uIGFwcHJvdmVkIGJ5IHRoZSBEZWFuIG9mIHRoZSBTY2hvb2wgb2YgR3JhZHVhdGUgU3R1ZGllczsgPC9saT4KPGxpPnRoZSBUaGVzaXMgZG9lcyBub3QgaW5mcmluZ2UgdGhlIGNvcHlyaWdodCBvciBpbnRlbGxlY3R1YWwgcHJvcGVydHkgcmlnaHRzIG9mIGFueSBvdGhlciBwZXJzb247IDwvbGk+CjxsaT5pZiB0aGUgVGhlc2lzIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCwgdW5kZXIgdGhlIHRlcm1zIG9mIHRoZSBDb3B5cmlnaHQgQWN0LCB3cml0dGVuIHBlcm1pc3Npb24gb2YgdGhlIGNvcHlyaWdodCBvd25lcihzKSBpcyByZXF1aXJlZCB0byBpbmNsdWRlIHRoZSB3b3JrIChvciBwYXJ0IHRoZXJlb2YsIGFzIHRoZSBjYXNlIG1heSBiZSkgaW4gdGhlIFRoZXNpcywgdGhlbiBib3RoIG9mIHRoZSBmb2xsb3dpbmcgYXBwbHk6CjxvbCB0eXBlPSJpIj48bGk+dGhlIG1hdGVyaWFsIGhhcyBiZWVuIGNsZWFybHkgYW5kIGFwcHJvcHJpYXRlbHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkOyBhbmQgPC9saT4KPGxpPnlvdSBoYXZlIG9idGFpbmVkIHdyaXR0ZW4gcGVybWlzc2lvbiBvZiB0aGUgY29weXJpZ2h0IG93bmVyKHMpLCBmb3IgdGhlIGZ1bGwgdGVybSBvZiBjb3B5cmlnaHQgcHJvdGVjdGlvbiwgdG8gaW5jbHVkZSB0aGUgd29yayAob3IgcGFydCB0aGVyZW9mLCBhcyB0aGUgY2FzZSBtYXkgYmUpIGluIHRoZSBUaGVzaXMgYW5kIHRvIGdyYW50IHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgdGhlIHJpZ2h0cyBzZXQgb3V0IGluIHRoaXMgbGljZW5zZTsgPC9saT48L29sPiA8L2xpPgo8bGk+IHRoZSBUaGVzaXMgZG9lcyBub3QgY29udGFpbiBhbnkgY29uZmlkZW50aWFsIG9yIHByb3ByaWV0YXJ5IGluZm9ybWF0aW9uIGJlbG9uZ2luZyB0byBvdGhlcnMsIG90aGVyIHRoYW4gaW5mb3JtYXRpb24gaW5jbHVkZWQgdW5kZXIgU2VjdGlvbiAyIGQpIGFib3ZlOyA8L2xpPgo8bGk+dGhlIFRoZXNpcyBkb2VzIG5vdCBjb250YWluIGFueSBsaWJlbG91cyBvciBvdGhlciB1bmxhd2Z1bCBtYXR0ZXIgYW5kIGRvZXMgbm90IGludmFkZSB0aGUgcHJpdmFjeSBvZiBhbnkgcGVyc29uczsgYW5kIDwvbGk+CjxsaT50aGVyZSBhcmUgbm8gdW5leHBpcmVkIHB1YmxpY2F0aW9uIGRlbGF5cyBvbiB0aGUgZGlzdHJpYnV0aW9uIG9mIHRoZSBUaGVzaXMuIDwvbGk+PC9vbD4gPC9saT4KPGxpPllvdSBhcmUgYXdhcmUgdGhhdCB5b3UgcmV0YWluIHlvdXIgY29weXJpZ2h0IG93bmVyc2hpcCBhbmQgbW9yYWwgcmlnaHRzIGluIHRoZSBUaGVzaXMgYW5kIG1heSBkZWFsIHdpdGggdGhlIFRoZXNpcyBpbiBhbnkgd2F5IGNvbnNpc3RlbnQgd2l0aCB0aGUgcmlnaHRzIGdyYW50ZWQgdG8gdGhlIFVuaXZlcnNpdHkgb2YgTGV0aGJyaWRnZSBpbiB0aGlzIGxpY2Vuc2UuIFlvdSB1bmRlcnRha2UgdG8gc3VibWl0IHlvdXIgVGhlc2lzLCBpbmNsdWRpbmcgdGhlIFRoZXNpcyBhYnN0cmFjdCwgdGhyb3VnaCB0aGUgVW5pdmVyc2l0eSBvZiBMZXRoYnJpZGdlIHRvIExpYnJhcnkgYW5kIEFyY2hpdmVzIENhbmFkYS4gWW91IHByb21pc2UgdG8gaW5mb3JtIGFueSBwZXJzb24gdG8gd2hvbSB5b3UgbWF5IGhlcmVhZnRlciBhc3NpZ24gb3IgbGljZW5zZSB5b3VyIGNvcHlyaWdodCBpbiB5b3VyIFRoZXNpcyBvZiB0aGUgcmlnaHRzIGdyYW50ZWQgdG8gdGhlIFVuaXZlcnNpdHkgb2YgTGV0aGJyaWRnZSBpbiB0aGlzIGxpY2Vuc2UuIFlvdSBhZ3JlZSB0aGF0IHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgaXMgbm90IHJlc3BvbnNpYmxlIGZvciBhbnkgbWlzdXNlIG9mIHRoZSBUaGVzaXMgYnkgdGhpcmQgcGFydGllcyB3aG8gYWNjZXNzIHRoZSBUaGVzaXMgdGhyb3VnaCB0aGUgVW5pdmVyc2l0eSBvZiBMZXRoYnJpZGdl4oCZcyBmYWNpbGl0aWVzLjwvbGk+PC9vbD4= URL http://localhost:4000/bitstreams/0ef7af49-9bf6-428d-b4d1-28b945d386ce/download File MD5 375a839ef35ad61b5fa6c8ec8551685a 473042 application/pdf GHEISARI_HIVA_MSC_2024.pdf URL http://localhost:4000/bitstreams/16fdfb5f-96cf-4197-82c7-a81bb1beea58/download File MD5 18d94990f0064d601d5d5db4032d5605 104273 text/plain GHEISARI_HIVA_MSC_2024.pdf.txt