A Simple Algorithm for Prime Factorization and Primality Testing
We propose a new simple and faster algorithm to factor numbers based on the nature of the prime numbers contained in such composite numbers. It is well known that every composite number has a unique representation as a product of prime numbers. In this study, we focus mainly on composite numbers tha...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2022/7034529 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552725831745536 |
|---|---|
| author | Kabenge Hamiss |
| author_facet | Kabenge Hamiss |
| author_sort | Kabenge Hamiss |
| collection | DOAJ |
| description | We propose a new simple and faster algorithm to factor numbers based on the nature of the prime numbers contained in such composite numbers. It is well known that every composite number has a unique representation as a product of prime numbers. In this study, we focus mainly on composite numbers that contain a product of prime numbers that are greater than or equal to 5 which are of the form 6k+1 or 6k+5. Therefore, we use the condition that every prime or composite P of primes greater than or equal to 5 satisfies P2≡1 mod24. This algorithm is very fast especially when the difference in the prime components of a composite number (prime gap) is not so large. When the difference between the factors (prime gap) is not so large, it often requires just a single iteration to obtain the factors. |
| format | Article |
| id | doaj-art-9393e440e1a44a218ad4345769a46a4b |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-9393e440e1a44a218ad4345769a46a4b2025-02-03T05:58:04ZengWileyJournal of Mathematics2314-47852022-01-01202210.1155/2022/7034529A Simple Algorithm for Prime Factorization and Primality TestingKabenge Hamiss0Department of Mathematics and StatisticsWe propose a new simple and faster algorithm to factor numbers based on the nature of the prime numbers contained in such composite numbers. It is well known that every composite number has a unique representation as a product of prime numbers. In this study, we focus mainly on composite numbers that contain a product of prime numbers that are greater than or equal to 5 which are of the form 6k+1 or 6k+5. Therefore, we use the condition that every prime or composite P of primes greater than or equal to 5 satisfies P2≡1 mod24. This algorithm is very fast especially when the difference in the prime components of a composite number (prime gap) is not so large. When the difference between the factors (prime gap) is not so large, it often requires just a single iteration to obtain the factors.http://dx.doi.org/10.1155/2022/7034529 |
| spellingShingle | Kabenge Hamiss A Simple Algorithm for Prime Factorization and Primality Testing Journal of Mathematics |
| title | A Simple Algorithm for Prime Factorization and Primality Testing |
| title_full | A Simple Algorithm for Prime Factorization and Primality Testing |
| title_fullStr | A Simple Algorithm for Prime Factorization and Primality Testing |
| title_full_unstemmed | A Simple Algorithm for Prime Factorization and Primality Testing |
| title_short | A Simple Algorithm for Prime Factorization and Primality Testing |
| title_sort | simple algorithm for prime factorization and primality testing |
| url | http://dx.doi.org/10.1155/2022/7034529 |
| work_keys_str_mv | AT kabengehamiss asimplealgorithmforprimefactorizationandprimalitytesting AT kabengehamiss simplealgorithmforprimefactorizationandprimalitytesting |