Created
August 10, 2017 02:26
-
-
Save kebman/c77310bc02662b2df884c56211d67fc6 to your computer and use it in GitHub Desktop.
Find All Primitive Root Modulo of a Prime Number
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Equation for finding the Primitive Root Modulo n: | |
* cn^n mod p | |
* for n = 1 to n = p-1 | |
* This program is a little heavy on the counting, though it seems to work with the current set of Prime Numbers... | |
*/ | |
// a few prime numbers for testing: | |
const primeNumbers = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281]; | |
// console.log(primeNumbers.length); // check size | |
// prime number to test (choose from array): | |
const p = primeNumbers[59]; // 59 is currently max | |
// calculate modulus for candidate number | |
function calcModFor(candidate) { | |
let primitives = []; | |
for (let i = 1; i < p; i++) { | |
let primitive = Math.pow(candidate, i) % p; // hopefully we won't catch a Math.pow() infinity problem here :p | |
primitives.push(primitive); | |
} | |
primitives.sort(); | |
return testRoot(primitives); | |
} | |
// if this test finds two equal numbers in the array, then the candidate number is not a Primitive Root Modulo of p | |
function testRoot(pArray) { | |
let isPrimRoot = false; | |
for (let i = 0; i < pArray.length; i++) { | |
if (pArray[i] === pArray[i+1]) { | |
break; | |
} | |
isPrimRoot = true; | |
} | |
return isPrimRoot; | |
} | |
let rString = ""; // for the presentation... | |
// check all numbers from 1 to p-1 and check if it's a Primitive Root Modulo of p | |
let rpNumbers = []; | |
for (let i = 2; i < p; i++) { | |
let isPrimRoot = calcModFor(i); | |
// there are fewer numbers that aren't primitive roots than are, so let's focus on the exceptions | |
if (!isPrimRoot) { | |
rpNumbers.push(i); | |
} | |
} | |
// presentation: | |
console.log("Not a Primitive Root of #"+p+":"); | |
for (let i = 0; i < rpNumbers.length; i++) { | |
if(i < rpNumbers.length-1) { | |
rString = rString + rpNumbers[i] + ", "; | |
} else { | |
rString = rString + rpNumbers[i] + "."; | |
} | |
} | |
console.log(rString); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
...or never.