A Journey Through Discovery:
Exploring Primality in Modular
Arithmetic
By: Nick Anderson
Megan Funk
Robert Messerschmidt
Introduction
We began our quest by looking into
modular arithmetic.
Then, we explored the idea of generators
and what numbers constituted a
generator.
But, we did not explore even numbers as
generators.
Modular Arithmetic
Modular arithmetic, which is also known
as clock arithmetic, is a system of
arithmetic for integers that begins and
ends at the same place.
For example, if you are looking at
numbers mod 5, once you go beyond the
number 5, the numbers start over again.
So 6 is congruent to 1 mod 5.
This system is the basis of our research.
Composite Modulo
We looked at composite modulo and
found that no odd composite modulo that
is not a prime power would allow a
generator.
We focused on the prime modulo and
looked at a few composite, but those
were not of interest.
Generators
We defined a generator through a
process.
First, we choose a prime number, p, to
investigate.
Then, we looked at each number in the
set respectively to find out which
numbers produced all numbers in the set
mod p.
Generators cont…
Then we made sure that the sets
produced ended at the number 1.
We said that these sets are generator
sets and the first number in the sets are
generators.
From here, we looked into grouping these
generator sets.
Grouping Generators
We found that generators can be grouped
based on the number of elements that bring
the set back to the starting point.
For example, if we look at the set Z(13), and
the number 3 within Z(13), the generator
set is 3-9-1, so the order is 3.
Another example in Z(13) is 5, the
generator set is 5-12-8-1, so the order is 4.
With this information we were able to
group sets based on their order.
Information detailing the code used as well as why
this was useful to our cohort
Primal Data
Different Programs
Primes – Sieve of Eratosthenes
Generators – Program which “generated”
generators
Different timings for implementations
Results
Added computational power lead to big
results
This shifted our focus to interpretation
Properties of Generators
8
Smallest Generators for first 100 Primes
7
6
5
4
3
2
1
0
0 10 20 30 40 50 60 70 80 90 100
First 100 Primes
Smallest Generator
25
Smallest Generators for first 1000 Primes
20
15
10
5
0
0 100 200 300 400 500 600 700 800 900 1000
First 1000 Primes
Smallest Generator
35
Smallest Generators for first 10000 Primes
30
25
20
15
10
5
0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
First 10000 Primes
Smallest Generator
50
Smallest Generators for first 100000 Primes
45
40
35
30
25
20
15
10
5
0
0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000
First 100000 Primes
Smallest Generator
Smallest Generators for first 375,000 - ish primes
80
70
60
50
40
30
20
10
0
0 200000 400000 600000 800000 1000000 1200000
First 375000-ish Primes
Smallest Generator
R Charts
Bound on the smallest generator for the first 1,000,000 primes
Or, in general
On to Robert!!
Now What?
Overall goal? Primality testing
Analyze our data and find patterns.
Least generator
◦ Frequency of different least generators
Frequency of Least Generators to 1,000,000( as %)
2
29 40 3
28 35 5
30
26 6
25
20
24 7
15
10
23 5 10
0
22 11
21 12
20 13
19 14
18 15
17
This information may lead us to
◦ Find certain numbers that allow us to find the least
generator without random testing.
◦ What numbers, that have least generators that
approach the upper bound (Large), may have in
common.
◦ How can we exclude larger groups of elements
from testing/improve our algorithms?
Questions? Comments?
Thank you to Siguna Mueller and Mathematics
Nick Anderson nanders5@uwyo.edu
Megan Funk funk@uwyo.edu
Robert Messerschmidt rmessers@uwyo.edu