Ankit Abhishek
Script error: No such module "Draft topics".
Script error: No such module "AfC topic".
Ankit's Primality Test: A New deterministic Primality Test Algorithm[edit]
This article introduces Ankit's Primality Test[1], a novel algorithm for determining whether a number is prime. Ankit's Primality Test is a deterministic[2] algorithm. The algorithm, presented by Ankit Abhishek on his YouTube channel[3], is claimed to be 5-6 times faster than the traditional trial division[4] method. This article analyzes the algorithm, its theoretical underpinnings, and its potential impact on primality testing. Ankit has also claimed on his YouTube channel that he is not able to publish it in journals because he can not bear the costs.
Primality testing[5], the process of determining whether a number is prime (divisible only by 1 and itself), is a fundamental problem in number theory with applications in cryptography, coding theory, and other areas. While efficient algorithms like the Miller-Rabin test[6] exist, the search for even faster and more deterministic methods continues. Ankit's Primality Test emerges as a promising contender in this pursuit.
| Ankit Abhishek | |
|---|---|
| Born | |
| 🏳️ Nationality | Indian |
| 💼 Occupation | |
Ankit's Primality Test relies on a set of numbers called Ankit numbers[7]. These are odd numbers greater than or equal to 9 with a digit other than 5 in the unit's place and leave non-zero remainders when divided by 3 and 7 including 3 and 7 itself to Ankit Number.
formula for checking Ankit Number for odd number a which is grater than equal to 9 and it has digit other than 5 in it's unit place is:
eg. 15 can not be considered for checking for Ankit Number because it has 5 in it's unit place.
(a mod 3 ≠ 0) and (a mod 7 ≠ 0)
where, a is the odd number grater than equal to 9 and it has digit other than 5 in it's unit place.
3 and 7 itself are Ankit Numbers.
eg. Ankit Numbers up to 40 are:
3,7,11,13,17,19,23,29,31,37
Ankit Number have following properties:
- Around 50 percent Ankit Numbers are prime numbers[8]
- and around 50 percent Ankit Numbers are non prime odd numbers whose ones place is not held by 5 (pseudoprimes[9])
The algorithm's implementation is relatively straightforward. Here's the code for key steps:
Checking for Ankit Numbers:
JavaScript[10] code
For a number n:
let n = 11; // Put the number here to check for Ankit number.
if(n >= 9){
let nString = n+"";
if(nString[nString.length - 1] != 5){
if(n % 2 != 0){
if(n % 3 != 0 && n % 7 != 0){
console.log(n + " is an Ankit number.");
}else{
console.log(n + " is not an Ankit number.");
}
}else{
console.log(n+ " is not an Ankit number.");
}
}else{
console.log(n+ " is not an Ankit number.");
}
}else{
let msg = n+ " is not an Ankit number.";
(n == 3 || n == 7) ? msg = n +" is an Ankit number." : null;
console.log(msg);
}
Generating Ankit Numbers up to a Certain Range: JavaScript code
let range = 12; // Put the number here for max generation range.
for (let i = 0; i <= range; i++) {
if(isAnkitNumber(i)){
console.log(i);
}
}
function isAnkitNumber(n){
let isTrue = false;
if(n >= 9){
let nString = n+"";
if(nString[nString.length - 1] != 5){
if(n % 2 != 0){
if(n % 3 != 0 && n % 7 != 0){
isTrue = true;
}
}
}
}else{
(n == 3 || n == 7) ? isTrue = true : null;
}
return isTrue;
}
Ankit's Primality Test To test if a number p is prime, the algorithm finds all Ankit numbers a up to the square root of p and checks if p modulo each Ankit number is not equal to 0. If this condition holds for all Ankit numbers, then with 100 percent accuracy p is prime.
p is prime if:
p mod a ≠ 0
here, p is the odd number greater than equal to whose ones place is not held by 5.
and a is all the Ankit Numbers up to √p.
that means p modulo each Ankit number(a)should not equal to 0
JavaScript code for Ankit's Primality Test
let p = 881; // Put the number here to test for primality.
var ankitNumbers = [];
if(p >= 9){
let range = Math.floor(Math.sqrt(p));
for (let i = 0; i <= range; i++) {
if(isAnkitNumber(i)){
ankitNumbers.push(i);
}
if(i == range){
console.log(checkPrime(ankitNumbers) ? p + " is a Prime number!" : p + " is not a Prime number.");
}
}
}else{
(p == 2 || p == 3 || p == 7) ? console.log(p + " is a Prime number!") : console.log(p + " is not a Prime number.");
}
function isAnkitNumber(n){
let isTrue = false;
if(n >= 9){
let nString = n+"";
if(nString[nString.length - 1] != 5){
if(n % 2 != 0){
if(n % 3 != 0 && n % 7 != 0){
isTrue = true;
}
}
}
}else{
(n == 3 || n == 7) ? isTrue = true : null;
}
return isTrue;
}
function checkPrime(){
isPrime = true;
for (let i = 0; i < ankitNumbers.length; i++) {
const a = ankitNumbers[i];
if(isAnkitNumber(p)){
if(p % a == 0){
isPrime = false;
}
if(i == ankitNumbers.length - 1){
return isPrime;
}
}else{
isPrime = false;
return isPrime;
}
}
}
if you will use static list of pre-generated Ankit Numbers then execution of Ankit's Primality Test will be faster.
The key advantage of Ankit's Primality Test lies in its reduced number of divisions compared to trial division. By utilizing the properties of Ankit numbers, the algorithm avoids unnecessary checks on composite numbers, leading to faster execution. However, the algorithm's complexity is not yet fully characterized. While it is not a provably polynomial-time algorithm.[11], empirical evidence suggests its runtime is significantly lower than trial division for large numbers.
If further research validates the efficiency of Ankit's Primality Test, it could have significant implications[12] for various fields. Faster primality testing can lead to improved performance in cryptography, where prime numbers play a crucial role in secure communication protocols[13]. Additionally, the algorithm's potential for parallelization could further accelerate primality testing for large-scale computations[14]
Ankit's Primality Test presents a promising new approach to primality testing with the potential to outperform existing methods[15]. While further theoretical analysis and empirical testing are necessary to fully assess its capabilities, the initial findings are encouraging. Continued research on this algorithm and its optimization could pave the way for significant advancements in primality testing and its related applications.
Several avenues remain open for future exploration regarding Ankit's Primality Test. One direction involves a rigorous complexity analysis to determine the algorithm's theoretical runtime. Additionally, investigating the distribution of Ankit numbers and their impact on the algorithm's performance for different types of numbers is crucial. Furthermore, exploring parallelization techniques and hardware optimization strategies could further enhance the algorithm's speed and efficiency.
References[edit]
- ↑ "Acknowledgment to Reviewers of Cryptography in 2020". Cryptography. 5 (1): 5. 2021-01-30. doi:10.3390/cryptography5010005. ISSN 2410-387X.
- ↑ "The deterministic AKS primality test", The Life of Primes in 37 Episodes, Providence, Rhode Island: American Mathematical Society, pp. 169–173, 2021-05-20, doi:10.1090/mbk/139/28, ISBN 978-1-4704-6537-7 Unknown parameter
|s2cid=ignored (help) - ↑ I created deterministic primality test, Ankit's Primality Test 5-6 times faster than trial division., 24 December 2023, retrieved 2023-12-25
- ↑ "Mitchell, Hon. Charles Richmond, (20 Nov. 1872–16 Aug. 1942), a Justice of the Supreme Court of Alberta, Appellate Division, 1926; Chief Justice Trial Division since 1936", Who Was Who, Oxford University Press, 2007-12-01, doi:10.1093/ww/9780199540884.013.u229337
- ↑ Stiglic, Anton (2011), "Primality Test", Encyclopedia of Cryptography and Security, pp. 958–959, doi:10.1007/978-1-4419-5906-5_469, ISBN 978-1-4419-5905-8
- ↑ Liskov, Moses (2011), "Miller–Rabin Probabilistic Primality Test", Encyclopedia of Cryptography and Security, pp. 784–785, doi:10.1007/978-1-4419-5906-5_461, ISBN 978-1-4419-5905-8
- ↑ Wilson, Robin (2020-05-28), "1. What is number theory?", Number Theory: A Very Short Introduction, Oxford University Press, pp. 1–13, doi:10.1093/actrade/9780198798095.003.0001, ISBN 978-0-19-879809-5
- ↑ "An "elementary" proof of the prime number theorem" (PDF), The Prime Number Theorem, Cambridge University Press, pp. 206–222, 2003-04-17, doi:10.1017/cbo9781139164986.007, ISBN 978-0-521-81411-9
- ↑ Stiglic, Anton (2011), "Pseudoprime", Encyclopedia of Cryptography and Security, pp. 994–995, doi:10.1007/978-1-4419-5906-5_473, ISBN 978-1-4419-5905-8
- ↑ Pair, C. (1990), "Programming, Programming Languages and Programming Methods", Psychology of Programming, Elsevier, pp. 9–19, doi:10.1016/b978-0-12-350772-3.50006-9, ISBN 978-0-12-350772-3
- ↑ Kaliski, Burt (2011), "Polynomial Time", Encyclopedia of Cryptography and Security, pp. 948–949, doi:10.1007/978-1-4419-5906-5_425, ISBN 978-1-4419-5905-8 Unknown parameter
|s2cid=ignored (help) - ↑ Kaliski, Burt (2011), "RSA Factoring Challenge", Encyclopedia of Cryptography and Security, pp. 1064–1065, doi:10.1007/978-1-4419-5906-5_433, ISBN 978-1-4419-5905-8 Unknown parameter
|s2cid=ignored (help) - ↑ "Netzwerkprogrammierung mit SSL", Unix-Netzwerkprogramminerung mit Threads, Sockets und SSL, X.systems.press, Springer Berlin Heidelberg, pp. 301–356, 2006, doi:10.1007/3-540-38302-6_6, ISBN 978-3-540-00299-4
- ↑ Solinas, Jerome A. (2011), "Mersenne Prime", Encyclopedia of Cryptography and Security, pp. 774–775, doi:10.1007/978-1-4419-5906-5_37, ISBN 978-1-4419-5905-8
- ↑ "The deterministic AKS primality test", The Life of Primes in 37 Episodes, Providence, Rhode Island: American Mathematical Society, pp. 169–173, 2021-05-20, doi:10.1090/mbk/139/28, ISBN 978-1-4704-6537-7 Unknown parameter
|s2cid=ignored (help)
This article "Ankit's Primality Test: A New deterministic Primality Test Algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Ankit's Primality Test: A New deterministic Primality Test Algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
